graph_spanning/
articulation.rs

1use graph_core::{Graph, NodeId};
2use std::collections::{HashMap, HashSet};
3
4/// Finds all **articulation points** (cut vertices) in an undirected graph.
5///
6/// An articulation point is a node whose removal increases the number of
7/// connected components. Removing it disconnects at least one pair of nodes
8/// that were previously reachable from each other.
9///
10/// # Algorithm
11///
12/// DFS with discovery time (`disc`) and low-link value (`low`). A node `u` is
13/// an articulation point in two cases:
14///
15/// 1. `u` is the **DFS root** and has **two or more children** in the DFS tree.
16/// 2. `u` is **not** the root and has a child `v` with `low[v] >= disc[u]`
17///    (the subtree at `v` cannot bypass `u` via a back-edge).
18///
19/// # Returns
20///
21/// A `HashSet<NodeId>` of all articulation points. Empty if the graph has no
22/// cut vertices (is 2-vertex-connected or trivially small).
23///
24/// # Complexity
25///
26/// O(V + E).
27///
28/// # Examples
29///
30/// ```
31/// use graph_core::{AdjacencyList, Graph};
32/// use graph_spanning::articulation_points;
33///
34/// // Graph: 0-1-2, with extra edge 0-2 (a cycle, no cut vertices)
35/// // Plus node 3 attached only to node 1 — making 1 an articulation point.
36/// //
37/// //  0 - 1 - 3
38/// //   \ /
39/// //    2
40/// let mut g: AdjacencyList<()> = AdjacencyList::undirected();
41/// let n: Vec<_> = (0..4).map(|_| g.add_node(())).collect();
42/// g.add_edge(n[0], n[1], 1.0).unwrap();
43/// g.add_edge(n[1], n[2], 1.0).unwrap();
44/// g.add_edge(n[0], n[2], 1.0).unwrap(); // closes cycle: 0-1-2-0
45/// g.add_edge(n[1], n[3], 1.0).unwrap(); // n[3] only reachable via n[1]
46///
47/// let aps = articulation_points(&g);
48/// assert!(aps.contains(&n[1]));
49/// assert!(!aps.contains(&n[0]));
50/// assert_eq!(aps.len(), 1);
51/// ```
52pub fn articulation_points<G>(graph: &G) -> HashSet<NodeId>
53where
54    G: Graph<Weight = f64>,
55{
56    let mut state = ArticulationState {
57        disc: HashMap::new(),
58        low: HashMap::new(),
59        timer: 0,
60        result: HashSet::new(),
61    };
62
63    for node in graph.nodes() {
64        if !state.disc.contains_key(&node) {
65            dfs_ap(graph, node, None, &mut state);
66        }
67    }
68
69    state.result
70}
71
72struct ArticulationState {
73    disc: HashMap<NodeId, usize>,
74    low: HashMap<NodeId, usize>,
75    timer: usize,
76    result: HashSet<NodeId>,
77}
78
79fn dfs_ap<G>(graph: &G, node: NodeId, parent: Option<NodeId>, state: &mut ArticulationState)
80where
81    G: Graph<Weight = f64>,
82{
83    state.disc.insert(node, state.timer);
84    state.low.insert(node, state.timer);
85    state.timer += 1;
86
87    let mut child_count = 0usize;
88
89    for (neighbour, _) in graph.neighbors(node) {
90        if !state.disc.contains_key(&neighbour) {
91            child_count += 1;
92            dfs_ap(graph, neighbour, Some(node), state);
93
94            // Pull up low-link from child.
95            let child_low = state.low[&neighbour];
96            let node_low = state.low.get_mut(&node).unwrap();
97            if child_low < *node_low {
98                *node_low = child_low;
99            }
100
101            // Case 2: non-root node whose child cannot bypass it.
102            if parent.is_some() && state.low[&neighbour] >= state.disc[&node] {
103                state.result.insert(node);
104            }
105        } else if Some(neighbour) != parent {
106            // Back edge: update low[node].
107            let neighbour_disc = state.disc[&neighbour];
108            let node_low = state.low.get_mut(&node).unwrap();
109            if neighbour_disc < *node_low {
110                *node_low = neighbour_disc;
111            }
112        }
113    }
114
115    // Case 1: root node with multiple DFS children.
116    if parent.is_none() && child_count >= 2 {
117        state.result.insert(node);
118    }
119}
graph_spanning/articulation.rs

graph_spanning/
articulation.rs
