Function dsatur_coloring

Source
pub fn dsatur_coloring<G>(graph: G) -> (HashMap<G::NodeId, usize>, usize)
Expand description

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