The Graph Coloring problem, also known as Vertex Coloring Problem, aims to color each vertex of a given graph with the minimal number of different colors, given that two adjacent vertex cannot have the same color. See the wikipedia article for more information.
In order to compile this tool one needs cmake and SCIP. This tools has been developed and tested using SCIP 8: it may work with previous versions but I cannot be sure. cmake scripts are configured to work with a system installation of SCIP: you may need to modify the configuration if you want or need to use a static linked SCIP library.
To compile graph-coloring
# Configure build environment
cmake -S . -B build/
# Compile source code
cmake --build build/
# Run unit tests
ctest --test-dir build/
Once the compiling and testing procedures are done you will find inside the build/ directory two executables:
- bnp-graph-coloring : branch and price implementation of the graph coloring problem;
- graph-coloring : arc based implementation of the graph coloring problem.
Note: on your platform you may find similar names but with extensions like .exe.
The two generated executables takes as input, from the command line, a single ASCII DIMACS file. The parser is trivial and assumes that the input file is correctly formatted. The parser does not support binary files.
The two generated executables works in the same way so, for brevity, I will show only the usage of bnp-graph-coloring.
./bnp-graph-coloring your-graph.col
If you do not provide a graph file as argument the tool will get the graph specification from standard input.