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