Improvement on graph coloring implementation (Brelaz DFS and more)

[IngerMathilde]

As part of a school project we have been working on several algorithms that can speed up/improve the current brown graph coloring algorithms. This includes a faster version of Brown's original algorithm, Brelaz DSATUR algorithm, and the PASS algorithm. Furthermore, we implemented the ability to precolor the maximum clique. For this, we also have an additional clique finder which will return the maximum clique which has the most edges that connect to vertices outside the clique. Last, we implemented graph preprocessing (removing vertices which will not influence the chromatic number). These removed vertices are added afterward with the correct color.

Thus, the output of these algorithms is a fully colored graph that uses the same amount of colors as the chromatic number.

We have integrated these algorithms in the JGrapht library. Is this something that would be of interest to you?

[d-michail]

It would definitely be of interest.

However, speaking from past experience, it would be best to split the contributions in small parts and submit small, well-documented and self-contained pull-requests instead of one huge pull-request which is impossible to review.

Moreover, we already have some greedy coloring algorithms. For example the heuristic DSATUR algorithm is implemented in class SaturationDegreeColoring.

If by DSATUR you mean the exact branch and bound DSATUR algorithm by Brelaz, then we are missing that and indeed would be great to include in the library. Moreover, improved versions like the PASS algorithm are also very-welcome.

[IngerMathilde]

Hey! Good to hear that there is an interest! I am indeed talking about the branch and bound DSATUR algorithm fo Brelaz. Uploading it into different pull request might be a bit difficult due to the internal dependencies. As all these three backtracking algorithms have a lot of similarities we have decided to have an inheritance structure to limit duplicate code. It is similar to the structure used for the BaseBronKerboschCliqueFinder and its subsequent subclasses. Furthermore, the cliquefinder is used in the backtracking algorithms to precolor the best clique. We could remove this from the backtracking algorithms and use the bronkerbosch clique finder instead if that would be better. The total size of the full pull request would be 5 class files plus (BaseBackTrack, BackTrackColoringBrown, BackTrackColoringDSATUR, BackTrackColoringPass and PattabiramanMaximumCliqueFinder) its respective test cases. What would be your advice regarding the pull request in this instance?

[d-michail]

Could we split into two pull-requests?

• One PR with the clique finder, which could implement the CliqueAlgorithm interface
• One PR with the three coloring algorithms + the base class.

In order to decouple the two parts, the coloring algorithms could expect as a constructor argument, a function which would return the desired clique algorithm. I guess something like a Function<Graph<V,E>, CliqueAlgorithm<V>> could do the trick.

We also use a slightly different naming scheme. We would prefer BaseBacktrackColoring, BrownBacktrackColoring, PassBacktrackColoring, DsaturBacktrackColoring.

[IngerMathilde]

Thank you for your feedback. We will try to put a pull request together as soon as possible. Furthermore, currently, our clique algorithm will only return one maximum clique (namely one with the most combined vertices). We did this as it makes computation faster, and we are only interested in pre coloring of a single clique. However, based upon your clique algorithms it is common to return a set of all maximum cliques. Would you rather that we implement this as well, and then make it part of your MaximalCliqueEnumerationAlgorithm interface?

[d-michail]

The MaximalCliqueEnumerationAlgorithm is the interface for algorithms that enumerate "Maximal" but not necessarily "Maximum" cliques.

If your implementation searches for a maximum clique, then it would be better to implement the CliqueAlgorithm.

After taking a short look at the paper by Pattabiraman et al., it would be better to rename the class to something that does not name the algorithm using only the first author. Maybe something like PPGLCMaximumCliqueFinder. Usually we also include the appropriate references in the Javadoc.