petgraph/algo/
articulation_points.rs

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

petgraph/algo/
articulation_points.rs
