This project implements different well-known graph coloring algorithms, specifically vertex coloring.
Sequential algorithms:
- Greedy [Wiki]
Parallel algorithms:
- Luby [A simple parallel algorithm for the Maximal Independent Set problem, M. Luby, 1985]
- Jones & Plassmann [A parallel graph coloring heuristic, M. Jones and T. Plassmann, 1992]
- LDF (Largest Degree First) [A Comparison of Parallel Graph Coloring Algorithms, J. R. Allwright, 1995]
This is a short manual. Refer to DOCUMENTATION.md to read the full description of the project, containing all design implementation choices.
Requirements:
- CMake (version >= 3.16)
- Make
- Boost library (dynamic_bitset required)
cd src && mkdir build && cd build
cmake ..
make
cd ../..
cd src/build
./main [--help | -h] [--algo ALGO] [--graph GRAPH] [--threads THREADS] [--out OUT]
All the following arguments are OPTIONAL:
--help Show help menu
--algo ALGO Coloring algorithm. Choices: greedy, luby, jp, LDF (default: all)
--graph GRAPH Name of the graph (default: all graphs in the assets folder)
--threads THREADS Number of threads used in parallel algorithms (default: [2,4,8,12,MAX] if available)
--out OUT Name of the output file (default: benchmarks.csv)