### 1 unstable release

0.1.0 | Jul 11, 2022 |
---|

#**1424** in Algorithms

**99** downloads per month

**MIT/Apache**

18KB

317 lines

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

folder) and the number of colors found by the naive algorithm as a measure of difficulty, we get the following results:`instances/`

See the full results in

.`data /instances.tsv`