Clone wiki

coloring / Home

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.

Instructions

Clone the code hg clone ssh://hg@bitbucket.org/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.

MISCS

You might also be interested in

  1. 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.
  2. T. Nguyen., M.S. Thesis: "On the Graph Coloring Problem and Its Generalizations," Penn State University, 2006
  3. 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

Updated