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.

This is a heuristic. So, it does not necessarily return a minimum coloring. The graph must be undirected. It should not contain loops.

Arguments

• graph: undirected graph without loops.

Returns

Returns a tuple of:

• [struct@hashbrown::HashMap] that associates to each NodeId its color.
• usize: the number of used colors.

Complexity

• Time complexity: O((|V| + |E|)log(|V|).
• Auxiliary space: O(|V| + |E|).

where |V| is the number of nodes and |E| is the number of edges.

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]);