petgraph/algo/
coloring.rs

1use std::collections::{BinaryHeap, HashMap, HashSet};
2use std::hash::Hash;
3
4use crate::scored::MaxScored;
5use crate::visit::{IntoEdges, IntoNodeIdentifiers, NodeIndexable, VisitMap, Visitable};
6
7/// \[Generic\] DStatur algorithm to properly color a non weighted undirected graph.
8/// https://en.wikipedia.org/wiki/DSatur
9///
10/// This is a heuristic. So, it does not necessarily return a minimum coloring.
11///
12/// The graph must be undirected. It should not contain loops.
13/// It must implement `IntoEdges`, `IntoNodeIdentifiers` and `Visitable`
14/// Returns a tuple composed of a HashMap that associates to each `NodeId` its color and the number of used colors.
15///
16/// Computes in **O((|V| + |E|)*log(|V|)** time
17///
18/// # Example
19/// ```rust
20/// use petgraph::{Graph, Undirected};
21/// use petgraph::algo::dsatur_coloring;
22///
23/// let mut graph: Graph<(), (), Undirected> = Graph::new_undirected();
24/// let a = graph.add_node(());
25/// let b = graph.add_node(());
26/// let c = graph.add_node(());
27/// let d = graph.add_node(());
28/// let e = graph.add_node(());
29/// let f = graph.add_node(());
30///
31/// graph.extend_with_edges(&[
32///     (a, b),
33///     (b, c),
34///     (c, d),
35///     (d, e),
36///     (e, f),
37///     (f, a),
38/// ]);
39///
40/// // a ----- b ----- c
41/// // |               |
42/// // |               |
43/// // |               |
44/// // f ----- e------ d
45///
46/// let (coloring, nb_colors) = dsatur_coloring(&graph);
47/// assert_eq!(nb_colors, 2);
48/// assert_ne!(coloring[&a], coloring[&b]);
49/// ```
50
51pub fn dsatur_coloring<G>(graph: G) -> (HashMap<G::NodeId, usize>, usize)
52where
53    G: IntoEdges + IntoNodeIdentifiers + Visitable + NodeIndexable,
54    G::NodeId: Eq + Hash,
55{
56    let ix = |v| graph.to_index(v);
57    let n = graph.node_bound();
58
59    let mut degree_map = vec![0; n];
60    let mut queue = BinaryHeap::with_capacity(n);
61    let mut colored = HashMap::with_capacity(n);
62    let mut adj_color_map = vec![HashSet::new(); n];
63    let mut seen = graph.visit_map();
64    let mut max_color = 0;
65
66    for node in graph.node_identifiers() {
67        let degree = graph.edges(node).count();
68        queue.push(MaxScored((0, degree), node));
69        degree_map[ix(node)] = degree;
70    }
71
72    while let Some(MaxScored(_, node)) = queue.pop() {
73        if seen.is_visited(&node) {
74            continue;
75        }
76        seen.visit(node);
77
78        let adj_color = &adj_color_map[ix(node)];
79        let mut color = 0;
80        while adj_color.contains(&color) {
81            color += 1;
82        }
83
84        colored.insert(node, color);
85        max_color = max_color.max(color);
86
87        for nbor in graph.neighbors(node) {
88            if let Some(adj_color) = adj_color_map.get_mut(ix(nbor)) {
89                adj_color.insert(color);
90                queue.push(MaxScored((adj_color.len(), degree_map[ix(nbor)]), nbor));
91            }
92        }
93    }
94
95    (colored, max_color + 1)
96}
petgraph/algo/coloring.rs

petgraph/algo/
coloring.rs
