petgraph/algo/
articulation_points.rs

1use alloc::{vec, vec::Vec};
2use core::{cmp::min, hash::Hash};
3
4use fixedbitset::FixedBitSet;
5use hashbrown::{HashMap, HashSet};
6
7use crate::visit;
8use crate::visit::{EdgeRef, IntoEdges, IntoNodeReferences, NodeIndexable, NodeRef};
9
10/// \[Generic\] Find articulation points in a graph using [Tarjan's algorithm](https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm).
11///
12/// Compute the articulation points of a graph (Nodes, which would increase the number of connected components in the graph.
13///
14/// # Arguments
15/// * `graph`: A directed graph.
16///
17/// # Returns
18/// * `HashSet`: [`struct@hashbrown::HashSet`] of the node ids which correspond to the articulation points of the graph.
19///
20/// # Complexity
21/// - Time complexity: **O(|V| + |E|)**,
22/// - Auxiliary space: **O(|V|)**,
23///
24/// where **|V|** is the number of nodes and **|E|** is the number of edges.
25///
26///
27/// # Examples
28/// ```rust
29/// use petgraph::{
30///     algo::articulation_points,
31///     graph::{NodeIndex, UnGraph},
32///     algo::articulation_points::articulation_points,
33/// };
34///
35/// let mut gr = UnGraph::<&str, ()>::new_undirected();
36/// let a = gr.add_node("A");
37/// let b = gr.add_node("B");
38/// let c = gr.add_node("C");
39///
40/// gr.add_edge(a, b, ());
41/// gr.add_edge(b, c, ());
42///
43/// let articulation_points: Vec<&str> = articulation_points(&gr)
44///     .into_iter()
45///     .map(|node_idx| gr[node_idx])
46///     .collect();
47///
48/// // Articulation Points: ["B"]
49/// println!("Articulation Points: {:?}", articulation_points);
50/// ```
51pub fn articulation_points<G>(g: G) -> HashSet<G::NodeId>
52where
53    G: IntoNodeReferences + IntoEdges + NodeIndexable + visit::GraphProp,
54    G::NodeWeight: Clone,
55    G::EdgeWeight: Clone + PartialOrd,
56    G::NodeId: Eq + Hash,
57{
58    let graph_size = g.node_references().size_hint().0;
59    let mut auxiliary_const = ArticulationPointTracker::new(graph_size);
60
61    for node in g.node_references() {
62        let node_id = g.to_index(node.id());
63        if !auxiliary_const.visited[node_id] {
64            _dfs(&g, node_id, &mut auxiliary_const);
65        }
66    }
67
68    auxiliary_const
69        .articulation_points
70        .into_iter()
71        .map(|id| g.from_index(id))
72        .collect()
73}
74
75/// Small helper enum that defines the various splitup recursion steps of Tarjan's algorithm.
76enum RecursionStep {
77    BaseStep(usize),
78    ProcessChildStep(usize, usize),
79    NoBackEdgeConditionCheck(usize, usize),
80    RootMoreThanTwoChildrenCheck(usize),
81}
82
83/// Internal auxiliary helper struct for global variables.
84struct ArticulationPointTracker {
85    visited: FixedBitSet,
86    low: Vec<usize>,
87    disc: Vec<usize>,
88    parent: Vec<usize>,
89    time: usize,
90    articulation_points: HashSet<usize>,
91}
92
93impl ArticulationPointTracker {
94    fn new(graph_size: usize) -> Self {
95        Self {
96            visited: FixedBitSet::with_capacity(graph_size),
97            low: vec![usize::MAX; graph_size],
98            disc: vec![usize::MAX; graph_size],
99            parent: vec![usize::MAX; graph_size],
100            articulation_points: HashSet::with_capacity(graph_size),
101            time: 0,
102        }
103    }
104}
105
106/// Helper that performs the required DFS in an iterative manner.
107fn _dfs<G>(g: &G, target_node: usize, articulation_point_tracker: &mut ArticulationPointTracker)
108where
109    G: IntoEdges + NodeIndexable,
110{
111    let mut stack: Vec<RecursionStep> = vec![RecursionStep::BaseStep(target_node)];
112    let mut children_count: HashMap<usize, usize> = HashMap::new();
113
114    while let Some(recursion_step) = stack.pop() {
115        match recursion_step {
116            RecursionStep::BaseStep(current_node) => {
117                articulation_point_tracker.visited.insert(current_node);
118                articulation_point_tracker.disc[current_node] = articulation_point_tracker.time;
119                articulation_point_tracker.low[current_node] = articulation_point_tracker.time;
120                articulation_point_tracker.time += 1;
121
122                stack.push(RecursionStep::RootMoreThanTwoChildrenCheck(current_node));
123                for edge in g.edges(g.from_index(current_node)) {
124                    let child_node = g.to_index(edge.target());
125                    stack.push(RecursionStep::ProcessChildStep(current_node, child_node));
126                }
127            }
128            RecursionStep::ProcessChildStep(current_node, child_node) => {
129                if !articulation_point_tracker.visited.contains(child_node) {
130                    articulation_point_tracker.parent[child_node] = current_node;
131                    children_count
132                        .entry(current_node)
133                        .and_modify(|c| *c += 1)
134                        .or_insert(1);
135
136                    stack.push(RecursionStep::NoBackEdgeConditionCheck(
137                        current_node,
138                        child_node,
139                    ));
140                    stack.push(RecursionStep::BaseStep(child_node));
141                } else if child_node != articulation_point_tracker.parent[current_node] {
142                    articulation_point_tracker.low[current_node] = min(
143                        articulation_point_tracker.low[current_node],
144                        articulation_point_tracker.disc[child_node],
145                    );
146                }
147            }
148            RecursionStep::NoBackEdgeConditionCheck(current_node, child_node) => {
149                articulation_point_tracker.low[current_node] = min(
150                    articulation_point_tracker.low[current_node],
151                    articulation_point_tracker.low[child_node],
152                );
153
154                if articulation_point_tracker.parent[current_node] != usize::MAX
155                    && articulation_point_tracker.low[child_node]
156                        >= articulation_point_tracker.disc[current_node]
157                {
158                    articulation_point_tracker
159                        .articulation_points
160                        .insert(current_node);
161                }
162            }
163
164            RecursionStep::RootMoreThanTwoChildrenCheck(current_node) => {
165                let child_count = children_count.get(&current_node).cloned().unwrap_or(0);
166                if articulation_point_tracker.parent[current_node] == usize::MAX && child_count > 1
167                {
168                    articulation_point_tracker
169                        .articulation_points
170                        .insert(current_node);
171                }
172            }
173        }
174    }
175}
petgraph/algo/articulation_points.rs

petgraph/algo/
articulation_points.rs
