JCOL: A Java package for solving the graph coloring problem

Shalin Shah

Implementation of the three heuristic algorithms including DSatur[1], Iterated Greedy [2] and min-conflicts local search in a mixed strategy (randomized) for graph coloring in Java. The algorithm is created with tha aim of obtaining the best coloring, irrespective of run time. If you need to speed up the algorithm, consider not using local search. Also, if you need help with this, please open an issue.

The heuristic follows the following steps:

Compute a clique (maximum is good)
Color the clique
Sort the rest of the vertices in non-increasing order of the degree of saturation
Color the vertices in the order given by 3. Also, when a vertex is colored, change the degree of saturation of the neighboring vertices so that the order of coloring changes
Improve the coloring using Iterated Greedy techniques [2]
Improve the coloring using min-conflicts local search
Report the coloring

[1]"New methods to color the vertices of a graph", Brelaz D., CACM 22(4) pp 251--256

[2]"Iterated Greedy graph coloring and the difficulty landscape", Culberson J

Cite this work

@article{shah2020jcol,
  doi = {10.21105/joss.01843},
  url = {https://doi.org/10.21105/joss.01843},
  year = {2020},
  publisher = {The Open Journal},
  volume = {5},
  number = {48},
  pages = {1843},
  author = {Shalin Shah},
  title = {JCOL: A Java package for solving the graph coloring problem},
  journal = {Journal of Open Source Software}
}

Maven is needed to compile and package the code.

For e.g. you might run "brew install maven" on a Mac. Compile the code using Maven:

mvn package

(Please ignore the compilation warnings, it is because the code does not use generics)

Then, run the algorithm using any of the two methods:

Heuristics

java -cp target/graphcoloring-1.7-jar-with-dependencies.jar com.gcol.GraphColoring -f data.col

java -cp target/graphcoloring-1.7-jar-with-dependencies.jar com.gcol.GraphColoring
usage: java -cp graphcoloring-1.7-jar-with-dependencies.jar com.gcol.GraphColoring
 -f <arg>   The DIMACS formatted graph file name
 -h         This help message
 -help      This help message
 -i <arg>   Number of iterated greedy iterations
 -j <arg>   Number of local search iterations
 -l <arg>   Enable local search true/false
 -m <arg>   Number of milliseconds to spend on local search
 -v <arg>   Verbose true/false

Backtracking

java -cp target/graphcoloring-1.7-jar-with-dependencies.jar com.gcol.Backtracking -f data.col

java -cp target/graphcoloring-1.7-jar-with-dependencies.jar com.gcol.Backtracking
usage: java -cp graphcoloring-1.7-jar-with-dependencies.jar com.gcol.Backtracking
 -f <arg>   The DIMACS formatted graph file name
 -h         This help message
 -help      This help message
 -t <arg>   Number of milliseconds to spend on each value of k
 -v <arg>   Verbose true/false

Please remove all comments (lines starting with a 'c') and other extraneous text from the file.

Please run automatedtests.sh in the tests directory to test the code.

Instances are available here and here in DIMACS format. (The use of graphs in binary format is not yet supported).

(If you want to use the DIMACS formatted files on ColPack, please use DimacsToMatrix.java)

Very Large Graphs

If you need to run the algorithm for very large graphs, please consider setting local search to false.

java -cp target/graphcoloring-1.7-jar-with-dependencies.jar com.gcol.GraphColoring -f data.col -l false

If you need help, please open an issue.

If you want to call the code as an API, please see API.

Cited By:

1) Mirarab, Siavash, et al. "Statistical binning enables an accurate coalescent-based estimation of the avian tree." Science 346.6215 (2014): 1250463. 2) https://github.com/smirarab/binning/ 3) Ahmad Muklason, Hyper-heuristics and Fairness in Examination Timetabling Problems

The algorithm was run on a few benchmark instances and the results are shown in the following table. The algorithm was run 10 times and the best and the worst results are shown.

||||||| |--- |--- |--- |--- |--- |--- | |Instance|Vertices|Optimum|Found - Best|Found - Worst|Edges |fpsol2.i.1|496|65|65|65|11654| |fpsol2.i.2|451|30|30|30|8691| |fpsol2.i.3|425|30|30|30|8688| |inithx.i.1|864|54|54|54|18707| |inithx.i.2|645|31|31|31|13979| |inithx.i.3|621|31|31|31|13969| |*latinsquare10|900|-|124|125|307350| |le45015b|450|15|18|18|8169| |le45015c|450|15|25|25|16680| |le4505a|450|5|6|6|5714| |le4505b|450|5|7|7|5734| |le4505c|450|5|7|7|9803| |le4505d|450|5|7|8|9757| |mulsol.i.1|197|49|49|49|3925| |mulsol.i.2|188|31|31|31|3885| |mulsol.i.3|184|31|31|31|3916| |mulsol.i.4|185|31|31|31|3946| |mulsol.i.5|186|31|31|31|3973| |school1|385|-|15|15|19095| |school1nsh|352|-|15|15|14612| |zeroin.i.1|211|49|49|49|4100| |zeroin.i.2|211|30|30|30|3541| |zeroin.i.3|206|30|30|30|3540| |anna|138|11|11|11|493| |david|87|11|11|11|406| |homer|561|13|13|13|1629| |huck|74|11|11|11|301| |jean|80|10|10|10|254| |games120|120|9|9|9|638| |miles1000|128|42|42|42|3216| |miles1500|128|73|73|73|5198| |miles250|128|8|8|8|387| |miles500|128|20|20|20|1170| |miles750|128|31|31|31|2113| |queen1111|121|11|14|14|3960| |queen1313|169|13|16|16|6656| |queen55|25|5|5|5|160| |queen66|36|7|7|7|290| |queen77|49|7|7|7|476| |queen812|96|12|13|13|1368| |queen88|64|9|10|10|728| |queen9_9|81|10|11|11|2112| |myciel3|11|4|4|4|20| |myciel4|23|5|5|5|71| |myciel5|47|6|6|6|236| |myciel6|95|7|7|7|755| |myciel7|191|8|8|8|2360|

• The algorithm was terminated before local search

The algorithm was run on a few more benchmark instances and the results are shown in the following table.

|||||| |--- |--- |--- |--- |--- | |Instance|Vertices|Optimum|Found - Best|Found - Worst| |frb30-15-1|450|30|30|30| |frb30-15-2|450|30|30|30| |frb30-15-3|450|30|30|30| |frb30-15-4|450|30|30|30| |frb30-15-5|450|30|30|30| |frb50-23-1|1150|50|50|50| |frb50-23-2|1150|50|50|50| |frb50-23-3|1150|50|50|50| |frb50-23-4|1150|50|50|50| |frb50-23-5|1150|50|50|50| |frb53-24-1|1272|53|53|53| |frb53-24-2|1272|53|53|53| |frb53-24-3|1272|53|53|53| |frb53-24-4|1272|53|53|53| |frb53-24-5|1272|53|53|53| |frb56-25-1|1400|56|56|56| |frb56-25-2|1400|56|56|56| |frb56-25-3|1400|56|56|56| |frb56-25-4|1400|56|56|56| |frb56-25-5|1400|56|56|56| |frb59-26-1|1534|59|59|59| |frb59-26-2|1534|59|59|59| |frb59-26-3|1534|59|59|59| |frb59-26-4|1534|59|59|59| |frb59-26-5|1534|59|59|59|

ColPack comparison

I ran ColPack (DISTANCEONE) on some of the publicly available data sets for comparison. The results are in the following table. On all of the instances, our algorithm is as good or better than the ColPack implementations. On the le4505d and the queen9_9 instances, our method is able to achieve a better coloring of the graphs.

About execution time, there are several parameters which can be used to control the run time. For instance, one could disable local search, or reduce the number of iterations and get a much better run time. On the inithx.i.3 instance with 621 vertices, this algorithm takes 2 seconds (1000 iterations, without local search) and ColPack takes 45 milliseconds. But if the goal is to get a good enough coloring as fast as possible, the algorithm could be changed. Please open an issue if this is the case.

The following table shows the results and the time it takes for JCOL (100 iterations, no local search) and ColPack on some benchmarks.

|||||||| |--- |--- |--- |--- |--- |--- |--- | |DataSet|LARGEST FIRST|SMALLEST LAST|INCIDENCE DEGREE|This Algorithm|ColPack(ms)|JCOL(ms) |fpsol2.i.3|30|30|30|30|32|430 |inithx.i.3|31|31|32|31|36|457 |le4505d|14|12|14|7|33|361 |mulsol.i.5|31|31|31|31|38|342 |zeroin.i.3|30|30|30|30|30|332 |games120|9|9|9|9|30|229 |miles750|32|31|32|31|31|276 |queen99|15|15|15|11|30|218 |myciel7|8|8|9|8|30|569

References

[1] Brélaz, D. (1979). New methods to color the vertices of a graph. Communications of the ACM, 22(4), 251–256. doi:10.1145/359094.359101

[2] Culberson, J. (1992). Iterated greedy graph coloring and the difficulty landscape. doi:10.7939/R3M32NH6Q

[3] Gebremedhin, A., Nguyen, D., Patwary, M., & Pothen, A. (2010). ColPack: Software for graph coloring and related problems in scientific computing. Submitted to ACM TOMS. doi:10.1145/2513109.2513110

[4] Malaguti, E., & Toth, P. (2010). A survey on vertex coloring problems. International transactions in operational research, 17(1), 1–34. doi:10.1111/j.1475-3995.2009.00696.x