Crate heuristic_graph_coloring

GitHub | Crates.io | Docs.rs

This crate provides algorithms for solving the graph vertex coloring problem. These algorithms return a “coloring”, i.e. an assignment of each vertex to a “color” (index) such that no two vertices of the same color are connected by an edge. The algorithms use heuristics to minimize the number of different colors used.

Current status: basic functionality is working, but not very optimized and not extensively tested.

Example of creating a graph with 4 vertices, adding 4 edges and coloring it.

use heuristic_graph_coloring::*;

let mut graph = VecVecGraph::new(4);
graph.add_edge(0, 1);
graph.add_edge(1, 2);
graph.add_edge(0, 2);
graph.add_edge(2, 3);
let coloring = color_greedy_by_degree(&graph);
assert_eq!(coloring, [1, 2, 0, 1]);

Algorithms

Name	Function	Colors used	Time used	Comment
Greedy (naive)	color_greedy_naive	Most	Least	Only use as a baseline.
Greedy (by degree)	color_greedy_by_degree	A bit less	Least	Fast decent results.
DSatur	color_greedy_dsatur	Less	More	Good results but quite slow.
Recursive largest first	color_rlf	Even less	Even more	Slowest and worst time complexity, but best results.

If you really want the least number of colors there is are slower algorightms like backtracking, SAT-solvers or HEA evolutionary approaches. The above algorithms are still useful to determine an upper bound in advance.

On the other hand, if you want to go faster then there exist parallel and distributed graph coloring algorithms.

Tests

Using a data set of instances (see instances/ folder) and the number of colors found by the naive algorithm as a measure of difficulty, we get the following results:

See the full results in data/instances.tsv.

Structs

CsrGraph

A graph in compressed format with all edges in one array.

VecVecGraph

Graph represented as multiple Vecs, one for each vertex.

Traits

ColorableGraph

Trait for graphs that the algorithms in this crate can work with.

Functions

color_greedy_by_degree

Colors vertices from highest degree to lowest by first possible color.

color_greedy_dsatur

Colors vertices from most colors of neighbors to least (dynamically) by first possible color. Known as DSATUR.

color_greedy_naive

The most simple greedy algorigthm. Colors vertices in index order by first possible color.

color_rlf

Colors vertices one color at a time by foming maximal independent sets. Known as Recursive Largest First.

count_colors

Counts the amount of colors in coloring by getting the maximum color plus one.

make_coloring_more_equitable

Adjust coloring to try to make each color used a similar amount

validate_coloring

Checks that the coloring is correct, else panics.