weavatrix_graph/algo/
biconnected.rs

1use crate::{IndexUndirectedGraphView, Vec};
2
3/// Deterministic vertex-biconnected edge blocks and their cut vertices.
4#[derive(Debug, Clone, PartialEq, Eq)]
5pub struct BiconnectedComponents<Node, Edge> {
6    components: Vec<Vec<Edge>>,
7    articulation_points: Vec<Node>,
8}
9
10impl<Node, Edge> BiconnectedComponents<Node, Edge> {
11    /// Returns canonical edge blocks, ordered by their smallest edge index.
12    #[must_use]
13    pub fn components(&self) -> &[Vec<Edge>] {
14        &self.components
15    }
16
17    /// Returns the number of edge blocks.
18    #[must_use]
19    pub fn component_count(&self) -> usize {
20        self.components.len()
21    }
22
23    /// Returns cut vertices in canonical node-index order.
24    #[must_use]
25    pub fn articulation_points(&self) -> &[Node] {
26        &self.articulation_points
27    }
28
29    /// Consumes the result and returns its canonical edge blocks.
30    #[must_use]
31    pub fn into_components(self) -> Vec<Vec<Edge>> {
32        self.components
33    }
34}
35
36/// Finds vertex-biconnected edge blocks and articulation points.
37#[must_use]
38pub fn biconnected_components<G>(graph: &G) -> BiconnectedComponents<G::Node, G::Edge>
39where
40    G: IndexUndirectedGraphView,
41{
42    biconnected_components_with_allowed::<G, false>(graph, Vec::new())
43}
44
45/// Finds vertex-biconnected edge blocks using accepted edges only.
46///
47/// The predicate is evaluated exactly once per edge. Isolated vertices do not
48/// form edge blocks; a self-loop forms its own block.
49#[must_use]
50pub fn biconnected_components_filtered<G, F>(
51    graph: &G,
52    allows_edge: F,
53) -> BiconnectedComponents<G::Node, G::Edge>
54where
55    G: IndexUndirectedGraphView,
56    F: Fn(G::Edge) -> bool,
57{
58    let mut allowed = vec![false; graph.edge_bound()];
59    for edge in graph.edge_indices() {
60        allowed[G::edge_slot(edge)] = allows_edge(edge);
61    }
62    biconnected_components_with_allowed::<G, true>(graph, allowed)
63}
64
65fn biconnected_components_with_allowed<G, const FILTERED: bool>(
66    graph: &G,
67    allowed: Vec<bool>,
68) -> BiconnectedComponents<G::Node, G::Edge>
69where
70    G: IndexUndirectedGraphView,
71{
72    let mut nodes = graph.node_indices().collect::<Vec<_>>();
73    nodes.sort_unstable_by_key(|node| G::node_slot(*node));
74    let mut state = State::<G, FILTERED>::new(graph, allowed);
75    for root in nodes {
76        if state.discovery[G::node_slot(root)] == usize::MAX {
77            state.search_from(graph, root);
78        }
79    }
80    state.finish(graph)
81}
82
83struct Frame<Node, Edge> {
84    node: Node,
85    parent_edge: Option<Edge>,
86    next: usize,
87    degree: usize,
88    children: usize,
89}
90
91struct State<G, const FILTERED: bool>
92where
93    G: IndexUndirectedGraphView,
94{
95    time: usize,
96    discovery: Vec<usize>,
97    low: Vec<usize>,
98    articulation: Vec<bool>,
99    allowed: Vec<bool>,
100    seen_self_loop: Vec<bool>,
101    edge_stack: Vec<G::Edge>,
102    edge_component: Vec<usize>,
103    component_count: usize,
104}
105
106impl<G, const FILTERED: bool> State<G, FILTERED>
107where
108    G: IndexUndirectedGraphView,
109{
110    fn new(graph: &G, allowed: Vec<bool>) -> Self {
111        Self {
112            time: 0,
113            discovery: vec![usize::MAX; graph.node_bound()],
114            low: vec![0; graph.node_bound()],
115            articulation: vec![false; graph.node_bound()],
116            allowed,
117            seen_self_loop: vec![false; graph.edge_bound()],
118            edge_stack: Vec::new(),
119            edge_component: vec![usize::MAX; graph.edge_bound()],
120            component_count: 0,
121        }
122    }
123
124    fn search_from(&mut self, graph: &G, root: G::Node) {
125        self.discover(root);
126        let mut frames = vec![Self::frame(graph, root, None)];
127        while !frames.is_empty() {
128            let next = {
129                let frame = frames.last_mut().expect("non-empty DFS stack");
130                if frame.next == frame.degree {
131                    None
132                } else {
133                    let edge = graph
134                        .incident_edge_at(frame.node, frame.next)
135                        .expect("offset is inside incident edge range");
136                    frame.next += 1;
137                    Some((frame.node, frame.parent_edge, edge))
138                }
139            };
140            if let Some((node, parent_edge, edge)) = next {
141                self.explore_edge(graph, &mut frames, node, parent_edge, edge);
142            } else {
143                let frame = frames.pop().expect("non-empty DFS stack");
144                self.finish_frame(frames.last_mut(), &frame);
145            }
146        }
147        debug_assert!(self.edge_stack.is_empty());
148    }
149
150    fn explore_edge(
151        &mut self,
152        graph: &G,
153        frames: &mut Vec<Frame<G::Node, G::Edge>>,
154        node: G::Node,
155        parent_edge: Option<G::Edge>,
156        edge: G::Edge,
157    ) {
158        let edge_slot = G::edge_slot(edge);
159        if FILTERED && !self.allowed[edge_slot] {
160            return;
161        }
162        if Some(edge) == parent_edge {
163            return;
164        }
165        let Some(neighbor) = graph.opposite(edge, node) else {
166            return;
167        };
168        if neighbor == node {
169            if !self.seen_self_loop[edge_slot] {
170                self.seen_self_loop[edge_slot] = true;
171                self.edge_component[edge_slot] = self.component_count;
172                self.component_count += 1;
173            }
174            return;
175        }
176        let slot = G::node_slot(node);
177        let neighbor_slot = G::node_slot(neighbor);
178        if self.discovery[neighbor_slot] == usize::MAX {
179            frames.last_mut().expect("parent frame").children += 1;
180            self.edge_stack.push(edge);
181            self.discover(neighbor);
182            frames.push(Self::frame(graph, neighbor, Some(edge)));
183        } else if self.discovery[neighbor_slot] < self.discovery[slot] {
184            self.edge_stack.push(edge);
185            self.low[slot] = self.low[slot].min(self.discovery[neighbor_slot]);
186        }
187    }
188
189    fn finish_frame(
190        &mut self,
191        parent: Option<&mut Frame<G::Node, G::Edge>>,
192        frame: &Frame<G::Node, G::Edge>,
193    ) {
194        let slot = G::node_slot(frame.node);
195        let Some(tree_edge) = frame.parent_edge else {
196            if frame.children > 1 {
197                self.articulation[slot] = true;
198            }
199            return;
200        };
201        let parent = parent.expect("non-root frame has parent");
202        let parent_slot = G::node_slot(parent.node);
203        self.low[parent_slot] = self.low[parent_slot].min(self.low[slot]);
204        let parent_discovery = self.discovery[parent_slot];
205        if self.low[slot] >= parent_discovery {
206            if parent.parent_edge.is_some() {
207                self.articulation[parent_slot] = true;
208            }
209            self.pop_component(tree_edge);
210        }
211    }
212
213    fn frame(graph: &G, node: G::Node, parent_edge: Option<G::Edge>) -> Frame<G::Node, G::Edge> {
214        Frame {
215            node,
216            parent_edge,
217            next: 0,
218            degree: graph.incident_edges(node).len(),
219            children: 0,
220        }
221    }
222
223    fn discover(&mut self, node: G::Node) {
224        let slot = G::node_slot(node);
225        self.discovery[slot] = self.time;
226        self.low[slot] = self.time;
227        self.time += 1;
228    }
229
230    fn pop_component(&mut self, stop: G::Edge) {
231        let component = self.component_count;
232        self.component_count += 1;
233        while let Some(edge) = self.edge_stack.pop() {
234            self.edge_component[G::edge_slot(edge)] = component;
235            if edge == stop {
236                break;
237            }
238        }
239    }
240
241    fn finish(self, graph: &G) -> BiconnectedComponents<G::Node, G::Edge> {
242        let mut counts = vec![0; self.component_count];
243        for &component in &self.edge_component {
244            if component != usize::MAX {
245                counts[component] += 1;
246            }
247        }
248        let mut components = counts
249            .into_iter()
250            .map(Vec::with_capacity)
251            .collect::<Vec<_>>();
252        let mut edges = graph.edge_indices().collect::<Vec<_>>();
253        if !edges.is_sorted_by_key(|edge| G::edge_slot(*edge)) {
254            edges.sort_unstable_by_key(|edge| G::edge_slot(*edge));
255        }
256        for edge in edges {
257            let component = self.edge_component[G::edge_slot(edge)];
258            if component != usize::MAX {
259                components[component].push(edge);
260            }
261        }
262        components.retain(|component| !component.is_empty());
263        components.sort_unstable_by_key(|component| G::edge_slot(component[0]));
264        let mut articulation_points = graph
265            .node_indices()
266            .filter(|node| self.articulation[G::node_slot(*node)])
267            .collect::<Vec<_>>();
268        articulation_points.sort_unstable_by_key(|node| G::node_slot(*node));
269        BiconnectedComponents {
270            components,
271            articulation_points,
272        }
273    }
274}
weavatrix_graph/algo/biconnected.rs

weavatrix_graph/algo/
biconnected.rs
