Using Ant-based Algorithm for Graph Coloring problems
This project uses a heuristic ant-based algorithm for the (classic) Graph Coloring problem and several of its generalizations, namely the Bandwidth Coloring, Multi Coloring, and Bandwidth Multi Coloring problems.
Code is written in C/C++ and released under the BSD license.
Clone the code
hg clone ssh://email@example.com/nguyenthanhvuh/coloring
Classic Graph Coloring
$ cd Classic/src $ g++ main.cc -std=c++11 -o classic $ ./classic ../examples/DSJC125.1.col.b 1 #optional -D DB : turn on debugging and output sol to sol.txt nthreads: 1 colors: 5 vertices: 125 edges: 736 bestCycle: 160 seed: 1
In the above example,
../examples/DSJC125.1.col.b is the input graph in DIMACS binary format, and the [optional] integer
1 is the seed. The result
colors: 5 indicates this graph can be colored using 5 colors.
You might also be interested in
- Converter: convert from Dimacs binary to ascii and vice versa
- Benchmark graphs: http://www.cs.hbg.psu.edu/benchmarks/graphcoloring.html
- Papers: see these papers in my publication section
- Bui, T., T. Nguyen, C. Patel, and K. Phan, "An Ant-Based Algorithm for Coloring Graphs," Journal of Discrete Applied Mathematics, Vol. 156(2), 2008, pp. 190 --- 200.
- T. Nguyen., M.S. Thesis: "On the Graph Coloring Problem and Its Generalizations," Penn State University, 2006
- Bui, T and T. Nguyen, "An Agent-Based Algorithm for Generalized Graph Colorings," Proc. 8th Annual Conference on Genetic and Evolutionary Computation Conference (GECCO), 2006, pp. 19 --- 26