Benchmark, compare, and analyze graph colouring algorithms on DIMACS and generated datasets. The suite provides a C++ runner that handles I/O, timing, and CSV logging, plus a Python orchestrator to run all algorithms across many graphs with timeouts and retries.
- Prerequisites
- Installation
- Quick Start
- Algorithms Implemented
- Usage
- Bonus Applications
- Project Structure
- Documentation
Before building and running the project, ensure you have the following installed:
| Dependency | Minimum Version | Purpose |
|---|---|---|
| g++ | 10+ (C++20 support) | Compiling C++ source code |
| make | 4.0+ | Build automation |
| Python | 3.8+ | Orchestration and visualization tools |
| Dependency | Version | Purpose |
|---|---|---|
| matplotlib | 3.5+ | Animation rendering |
| networkx | 2.6+ | Graph generation and layout algorithms |
# Check C++ compiler
g++ --version # Should show version 10 or higher
# Check Python
python3 --version # Should show 3.8 or higher
# Check make
make --versiongit clone https://github.com/Rmehta-sudo/graph-colouring.git
cd graph-colouringRequired only for animation and synthetic graph generation:
# Using pip
pip install matplotlib networkx
# Or using pip3
pip3 install matplotlib networkx
# Or using conda
conda install matplotlib networkx# Compile the benchmark runner
make all
# Verify build succeeded
ls build/benchmark_runner # Should existBuild Output: build/benchmark_runner (main executable)
# Run a quick test
make run-dsatur GRAPH=dimacs/myciel3.col
# Expected output:
# Algorithm dsatur completed in X.XXX ms| Issue | Solution |
|---|---|
g++: command not found |
Install GCC: sudo apt install g++ (Ubuntu/Debian) |
error: 'filesystem' is not a namespace |
Ensure g++ version supports C++20: g++ --version |
make: command not found |
Install make: sudo apt install make |
| Algorithm | Type | Time Complexity | Description |
|---|---|---|---|
| Welsh-Powell | Greedy | O(V log V + E) | Degree-ordered greedy |
| DSatur | Greedy | O(V² + E) | Saturation-based greedy |
| Simulated Annealing | Metaheuristic | Configurable | Temperature-based optimization |
| Genetic Algorithm | Metaheuristic | O(P × G × V) | Evolutionary approach |
| Tabu Search | Metaheuristic | O(I × V × k) | TabuCol with conflict repair |
| Exact Solver | Exact | Exponential | Branch & bound (small graphs) |
# Build
make all
# Run single algorithm
make run-dsatur GRAPH=dimacs/myciel6.col
make run-tabu GRAPH=dimacs/myciel6.col
# Run all benchmarks
make run-all-benchmarking
# Animate algorithm progress
python3 tools/animate_coloring.py --graph myciel6 --algo dsaturRequirements: g++ with C++20, Python 3.8+, matplotlib, networkx (for animation)
make all # Build benchmark_runner
make clean # Clean build artifacts# Via Makefile (recommended)
make run-dsatur GRAPH=dimacs/myciel6.col
make run-tabu GRAPH=generated/tree_275_4.col SNAPSHOTS=1
# Direct CLI
./build/benchmark_runner \
--algorithm tabu_search \
--input data/dimacs/myciel6.col \
--output results/colourings/myciel6_tabu.col \
--results results/results.csv \
--graph-name myciel6 \
--save-snapshotsCLI Options:
| Option | Description |
|---|---|
--algorithm NAME |
welsh_powell, dsatur, simulated_annealing, genetic, tabu_search, exact_solver |
--input FILE |
Path to DIMACS .col graph |
--output FILE |
Where to write the colouring |
--results FILE |
CSV to append metrics |
--graph-name NAME |
Override graph identifier |
--save-snapshots |
Save per-iteration state for animation |
# Run all algorithms on all graphs
make run-all-benchmarking
# Custom run
python3 tools/run_all_benchmarks.py \
--graphs data/dimacs/myciel6.col data/dimacs/queen6_6.col \
--first-timeout 15 \
--second-timeout 30Visualize algorithm progress:
python3 tools/animate_coloring.py --graph myciel6 --algo dsatur
python3 tools/animate_coloring.py --graph myciel6 --algo tabu_search --interval 0.05
python3 tools/animate_coloring.py --graph myciel6 --all-algos # Compare allThis project includes two bonus applications demonstrating real-world uses of graph colouring:
A graphical application for creating conflict-free exam timetables using graph colouring algorithms.
Features:
- Modern Tkinter GUI with checkbox-based course selection
- Builds conflict graph from student course registrations
- Pure Python implementations of DSatur and Exact solver
- Exports schedules to CSV
Usage:
cd bonus/exam_scheduler
python3 exam_scheduler.pyHow it works:
- Load student registrations from CSV (columns: student_id, course1, course2, ...)
- Build conflict graph where courses sharing students become adjacent vertices
- Apply graph colouring to assign time slots (colours = exam slots)
- Display and export the conflict-free timetable
Sample Data:
eg.csv- Small test datasetbig-eg.csv- Larger realistic dataset
Find the maximum clique (largest complete subgraph) using the Bron-Kerbosch algorithm with pivoting.
Relationship to Graph Colouring:
- The chromatic number χ(G) ≥ ω(G), where ω(G) is the clique number
- Maximum clique provides a lower bound for graph colouring
- Useful for validating colouring results
Build & Run:
cd bonus/max_clique
# Compile
g++ -O3 -std=c++17 max_clique.cpp -o max_clique
# Run on a graph
./max_clique ../data/dimacs/myciel6.col
# Run batch experiments
python3 run_dimacs.py
python3 run_generated.pyOutput:
- Maximum clique size (ω)
- Vertices in the maximum clique
- Runtime statistics
Results: See bonus/max_clique/results/ for benchmark outputs.
graph-colouring/
├── README.md
├── Makefile
│
├── src/ # C++ source code
│ ├── benchmark_runner.cpp # Main CLI entry point
│ ├── utils.h # Core types (Graph, BenchmarkResult)
│ ├── algorithms/ # Colouring algorithms
│ │ ├── dsatur.cpp/.h
│ │ ├── welsh_powell.cpp/.h
│ │ ├── genetic.cpp/.h
│ │ ├── simulated_annealing.cpp/.h
│ │ ├── tabu.cpp/.h
│ │ └── exact_solver.cpp/.h
│ └── io/ # File I/O utilities
│ ├── graph_loader.cpp/.h
│ ├── graph_writer.cpp/.h
│ └── results_logger.cpp/.h
│
├── tools/ # Python tools
│ ├── run_all_benchmarks.py # Batch runner with timeouts
│ ├── animate_coloring.py # Algorithm visualization
│ ├── generate_graphs.py # Synthetic graph generator
│ └── analysis/ # Result analysis scripts
│
├── data/ # Graph datasets
│ ├── dimacs/ # DIMACS benchmark graphs
│ ├── generated/ # Synthetic test graphs
│ ├── network-repo/ # Network repository graphs
│ ├── metadata-dimacs.csv
│ └── metadata-generated.csv
│
├── results/ # Benchmark outputs
│ ├── colourings/ # Per-run colouring files
│ ├── results.csv # Single-run metrics
│ └── run_all_results.csv # Batch run aggregate
│
├── output/ # Generated outputs
│ ├── snapshots/ # Algorithm state snapshots
│ └── animations/ # Animation videos
│
├── docs/ # Documentation
│ ├── PROJECT_SUMMARY.md # Detailed project documentation
│ ├── code-spec.md # Code specifications
│ └── references/ # Academic papers
│
├── bonus/ # Bonus applications
│ ├── exam_scheduler/ # University exam scheduling GUI
│ │ ├── exam_scheduler.py # Main application
│ │ ├── eg.csv # Sample student data
│ │ └── exam_scheduler_report.pdf
│ └── max_clique/ # Maximum clique finder
│ ├── max_clique.cpp # Bron-Kerbosch implementation
│ ├── run_dimacs.py # Batch runner for DIMACS
│ ├── results/ # Benchmark results
│ └── max_clique_report.pdf
│
├── legacy/ # Old/utility scripts
│
└── build/ # Compiled binaries (gitignored)
algorithm,graph_name,vertices,edges,colors_used,known_optimal,runtime_ms
dsatur,myciel6,95,755,7,7,0.234
tabu_search,myciel6,95,755,7,7,45.123ok- Completed successfullyok(retry)- Completed on second attempttimeout>45s- Exceeded timeout limitserror- Non-zero exit code
- USAGE.md - Comprehensive usage guide with all commands
- PROJECT_SUMMARY.md - Detailed project documentation
- code-spec.md - Technical specifications
AAD Coursework Project - Semester 3