qcolor is a greedy graph quasi-coloring algorithm which can be used to calculate a lower bound for the k parameter of the feasible k-colorings of a finite simple graph, furthermore, it also gives an upper bound for the maximum clique of the given graph.
This algorithm is not unique in calculating the two above-mentioned bounds but it holds two really advantageous property, namely, it runs in polynomial time and it is very easily parallelizable.
A more detailed description of the algorithm can be found in the original
article of Szabó and Zaválnij [1] and the doc folder also contains a
commented example run.
This repository contains an Ada implementation using OpenCL kernels for the actual work.
- GNAT compiler + gprbuild
- working OpenCL implementation and a compatible hardware
- OpenCLAda (Ada binding for OpenCL)
These instructions are only tested on Linux but theoretically they should work in any POSIX-compliant shell even on Windows.
First of all you need to specify the project location of the OpenCLAda library.
This can be done by setting the value of GPR_PROJECT_PATH:
export GPR_PROJECT_PATHThe default value of this variable is ./ext/OpenCLAda so the easiest way to
make the compiler recognize the OpenCL binding library is to install it
directly into ./ext/ relative to the project root directory. (Note that you
can add further libraries through this variable by appending more pathnames
with a library separator to it.)
After you are confident the GPR_PROJECT_PATH variable is set correctly simply
run:
./build.shIf everything works well, you will get an executable in the bin directory. To
start fooling around you may want to read the help message first.
./bin/qcolor -hThis software is distributed under the terms and conditions of the GNU GPL v3.0. Copyright © 2019, 0l-l0
- [1] Szabó, Sándor & Zaválnij, Bogdán. (2018). Decomposing clique search problems into smaller instances based on node and edge colorings. Discrete Applied Mathematics. 242. 10.1016/j.dam.2018.01.006.