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 let Some(frame) = frames.last_mut() {
128            let next = {
129                if frame.next == frame.degree {
130                    None
131                } else {
132                    let edge = graph.incident_edge_at(frame.node, frame.next);
133                    frame.next += 1;
134                    edge.map(|edge| (frame.node, frame.parent_edge, edge))
135                }
136            };
137            if let Some((node, parent_edge, edge)) = next {
138                self.explore_edge(graph, &mut frames, node, parent_edge, edge);
139            } else {
140                let Some(frame) = frames.pop() else {
141                    break;
142                };
143                self.finish_frame(frames.last_mut(), &frame);
144            }
145        }
146        self.edge_stack.clear();
147    }
148
149    fn explore_edge(
150        &mut self,
151        graph: &G,
152        frames: &mut Vec<Frame<G::Node, G::Edge>>,
153        node: G::Node,
154        parent_edge: Option<G::Edge>,
155        edge: G::Edge,
156    ) {
157        let edge_slot = G::edge_slot(edge);
158        if FILTERED && !self.allowed[edge_slot] {
159            return;
160        }
161        if Some(edge) == parent_edge {
162            return;
163        }
164        let Some(neighbor) = graph.opposite(edge, node) else {
165            return;
166        };
167        if neighbor == node {
168            if !self.seen_self_loop[edge_slot] {
169                self.seen_self_loop[edge_slot] = true;
170                self.edge_component[edge_slot] = self.component_count;
171                self.component_count += 1;
172            }
173            return;
174        }
175        let slot = G::node_slot(node);
176        let neighbor_slot = G::node_slot(neighbor);
177        if self.discovery[neighbor_slot] == usize::MAX {
178            let Some(parent) = frames.last_mut() else {
179                return;
180            };
181            parent.children += 1;
182            self.edge_stack.push(edge);
183            self.discover(neighbor);
184            frames.push(Self::frame(graph, neighbor, Some(edge)));
185        } else if self.discovery[neighbor_slot] < self.discovery[slot] {
186            self.edge_stack.push(edge);
187            self.low[slot] = self.low[slot].min(self.discovery[neighbor_slot]);
188        }
189    }
190
191    fn finish_frame(
192        &mut self,
193        parent: Option<&mut Frame<G::Node, G::Edge>>,
194        frame: &Frame<G::Node, G::Edge>,
195    ) {
196        let slot = G::node_slot(frame.node);
197        let Some(tree_edge) = frame.parent_edge else {
198            if frame.children > 1 {
199                self.articulation[slot] = true;
200            }
201            return;
202        };
203        let Some(parent) = parent else {
204            return;
205        };
206        let parent_slot = G::node_slot(parent.node);
207        self.low[parent_slot] = self.low[parent_slot].min(self.low[slot]);
208        let parent_discovery = self.discovery[parent_slot];
209        if self.low[slot] >= parent_discovery {
210            if parent.parent_edge.is_some() {
211                self.articulation[parent_slot] = true;
212            }
213            self.pop_component(tree_edge);
214        }
215    }
216
217    fn frame(graph: &G, node: G::Node, parent_edge: Option<G::Edge>) -> Frame<G::Node, G::Edge> {
218        Frame {
219            node,
220            parent_edge,
221            next: 0,
222            degree: graph.incident_edges(node).len(),
223            children: 0,
224        }
225    }
226
227    fn discover(&mut self, node: G::Node) {
228        let slot = G::node_slot(node);
229        self.discovery[slot] = self.time;
230        self.low[slot] = self.time;
231        self.time += 1;
232    }
233
234    fn pop_component(&mut self, stop: G::Edge) {
235        let component = self.component_count;
236        self.component_count += 1;
237        while let Some(edge) = self.edge_stack.pop() {
238            self.edge_component[G::edge_slot(edge)] = component;
239            if edge == stop {
240                break;
241            }
242        }
243    }
244
245    fn finish(self, graph: &G) -> BiconnectedComponents<G::Node, G::Edge> {
246        let mut counts = vec![0; self.component_count];
247        for &component in &self.edge_component {
248            if component != usize::MAX {
249                counts[component] += 1;
250            }
251        }
252        let mut components = counts
253            .into_iter()
254            .map(Vec::with_capacity)
255            .collect::<Vec<_>>();
256        let mut edges = graph.edge_indices().collect::<Vec<_>>();
257        if !edges.is_sorted_by_key(|edge| G::edge_slot(*edge)) {
258            edges.sort_unstable_by_key(|edge| G::edge_slot(*edge));
259        }
260        for edge in edges {
261            let component = self.edge_component[G::edge_slot(edge)];
262            if component != usize::MAX {
263                components[component].push(edge);
264            }
265        }
266        components.retain(|component| !component.is_empty());
267        components.sort_unstable_by_key(|component| G::edge_slot(component[0]));
268        let mut articulation_points = graph
269            .node_indices()
270            .filter(|node| self.articulation[G::node_slot(*node)])
271            .collect::<Vec<_>>();
272        articulation_points.sort_unstable_by_key(|node| G::node_slot(*node));
273        BiconnectedComponents {
274            components,
275            articulation_points,
276        }
277    }
278}
weavatrix_graph/algo/biconnected.rs

weavatrix_graph/algo/
biconnected.rs
