Skip to content

JCOL: A Java package for solving the graph coloring problem (a heuristic)

License

Notifications You must be signed in to change notification settings

shah314/graphcoloring

Repository files navigation

JCOL: A Java package for solving the graph coloring problem

Shalin Shah

status

Three Coloring

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
*latin_square_10 900 - 124 125 307350
le450_15b 450 15 18 18 8169
le450_15c 450 15 25 25 16680
le450_5a 450 5 6 6 5714
le450_5b 450 5 7 7 5734
le450_5c 450 5 7 7 9803
le450_5d 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
school1_nsh 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
queen11_11 121 11 14 14 3960
queen13_13 169 13 16 16 6656
queen5_5 25 5 5 5 160
queen6_6 36 7 7 7 290
queen7_7 49 7 7 7 476
queen8_12 96 12 13 13 1368
queen8_8 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 (DISTANCE_ONE) 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 le450_5d 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
le450_5d 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
queen9_9 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