Function dsatur_coloring

pub fn dsatur_coloring<G>(graph: G) -> (HashMap<G::NodeId, usize>, usize)
where
    G: IntoEdges + IntoNodeIdentifiers + Visitable + NodeIndexable,
    G::NodeId: Eq + Hash,

[Generic] DStatur algorithm to properly color a non weighted undirected graph. https://en.wikipedia.org/wiki/DSatur

This is a heuristic. So, it does not necessarily return a minimum coloring.

The graph must be undirected. It should not contain loops. It must implement IntoEdges, IntoNodeIdentifiers and Visitable Returns a tuple composed of a HashMap that associates to each NodeId its color and the number of used colors.

Computes in *O((|V| + |E|)log(|V|) time

Example

use petgraph::{Graph, Undirected};
use petgraph::algo::dsatur_coloring;

let mut graph: Graph<(), (), Undirected> = Graph::new_undirected();
let a = graph.add_node(());
let b = graph.add_node(());
let c = graph.add_node(());
let d = graph.add_node(());
let e = graph.add_node(());
let f = graph.add_node(());

graph.extend_with_edges(&[
    (a, b),
    (b, c),
    (c, d),
    (d, e),
    (e, f),
    (f, a),
]);

// a ----- b ----- c
// |               |
// |               |
// |               |
// f ----- e------ d

let (coloring, nb_colors) = dsatur_coloring(&graph);
assert_eq!(nb_colors, 2);
assert_ne!(coloring[&a], coloring[&b]);