graphalgs/connect/
find_bridges.rs

1use petgraph::visit::{IntoNeighbors, IntoNodeIdentifiers, NodeIndexable};
2
3/// Find all [bridges](https://en.wikipedia.org/wiki/Bridge_(graph_theory)) in a simple undirected graph.
4///
5/// Returns the vector of pairs `(G::NodeID, G:: NodeID)`,
6/// representing the edges of the input graph that are bridges.
7/// The order of the vertices in the pair and the order of the edges themselves are arbitrary.
8///
9/// # Examples
10///
11/// ```
12/// use graphalgs::connect::find_bridges;
13/// use petgraph::graph::UnGraph;
14///
15/// // Create the following graph:
16/// // 0----1    4
17/// //      | __/|
18/// // 5----2/---3
19///
20/// let mut g = UnGraph::new_undirected();
21/// let n0 = g.add_node(());
22/// let n1 = g.add_node(());
23/// let n2 = g.add_node(());
24/// let n3 = g.add_node(());
25/// let n4 = g.add_node(());
26/// let n5 = g.add_node(());
27/// g.add_edge(n0, n1, ());
28/// g.add_edge(n1, n2, ());
29/// g.add_edge(n2, n3, ());
30/// g.add_edge(n3, n4, ());
31/// g.add_edge(n2, n4, ());
32/// g.add_edge(n5, n2, ());
33///
34/// // The bridges in this graph are the undirected edges {2, 5}, {1, 2}, {0, 1}.
35/// assert_eq!(find_bridges(&g), vec![(n2, n5), (n1, n2), (n0, n1)]);
36/// ```
37pub fn find_bridges<G>(graph: G) -> Vec<(G::NodeId, G::NodeId)>
38where
39    G: IntoNodeIdentifiers + IntoNeighbors + NodeIndexable,
40{
41    let mut bridges = Vec::new();
42    let mut visited = vec![false; graph.node_bound()];
43    let mut tin = vec![0usize; graph.node_bound()];
44    let mut fup = vec![0usize; graph.node_bound()];
45    let mut timer = 0usize;
46
47    for start in 0..graph.node_bound() {
48        if !visited[start] {
49            dfs_helper(
50                graph,
51                start,
52                graph.node_bound() + 1,
53                &mut bridges,
54                &mut visited,
55                &mut timer,
56                &mut tin,
57                &mut fup,
58            );
59        }
60    }
61
62    bridges
63}
64
65#[allow(clippy::too_many_arguments)]
66fn dfs_helper<G>(
67    graph: G,
68    v: usize,
69    p: usize,
70    bridges: &mut Vec<(G::NodeId, G::NodeId)>,
71    visited: &mut Vec<bool>,
72    timer: &mut usize,
73    tin: &mut Vec<usize>,
74    fup: &mut Vec<usize>,
75) where
76    G: IntoNodeIdentifiers + IntoNeighbors + NodeIndexable,
77{
78    visited[v] = true;
79    *timer += 1;
80    tin[v] = *timer;
81    fup[v] = *timer;
82
83    for n in graph.neighbors(graph.from_index(v)) {
84        let to = graph.to_index(n);
85        if to == p {
86            continue;
87        }
88        if visited[to] {
89            fup[v] = fup[v].min(tin[to]);
90        } else {
91            dfs_helper(graph, to, v, bridges, visited, timer, tin, fup);
92            fup[v] = fup[v].min(fup[to]);
93            if fup[to] > tin[v] {
94                bridges.push((graph.from_index(v), graph.from_index(to)));
95            }
96        }
97    }
98}
99
100#[cfg(test)]
101mod tests {
102    use super::*;
103    use petgraph::graph::UnGraph;
104
105    #[test]
106    fn test_find_bridges() {
107        let mut g = UnGraph::<i8, i8>::new_undirected();
108        assert_eq!(find_bridges(&g), vec![]);
109
110        let n0 = g.add_node(0);
111        assert_eq!(find_bridges(&g), vec![]);
112
113        let n1 = g.add_node(1);
114        assert_eq!(find_bridges(&g), vec![]);
115
116        g.add_edge(n0, n1, 0);
117        assert_eq!(find_bridges(&g), vec![(n0, n1)]);
118
119        let n2 = g.add_node(2);
120        assert_eq!(find_bridges(&g), vec![(n0, n1)]);
121
122        g.add_edge(n2, n1, 1);
123        g.add_edge(n0, n2, 2);
124        assert_eq!(find_bridges(&g), vec![]);
125
126        let n3 = g.add_node(3);
127        let n4 = g.add_node(4);
128        g.add_edge(n2, n3, 3);
129        g.add_edge(n3, n4, 4);
130        assert_eq!(find_bridges(&g), vec![(n3, n4), (n2, n3)]);
131
132        g.add_edge(n3, n0, 5);
133        assert_eq!(find_bridges(&g), vec![(n3, n4)]);
134
135        let mut g = UnGraph::new_undirected();
136        let n0 = g.add_node(());
137        let n1 = g.add_node(());
138        let n2 = g.add_node(());
139        let n3 = g.add_node(());
140        g.add_edge(n0, n2, ());
141        g.add_edge(n2, n3, ());
142        g.add_edge(n1, n3, ());
143
144        assert_eq!(find_bridges(&g), vec![(n3, n1), (n2, n3), (n0, n2)]);
145
146        let n4 = g.add_node(());
147        let n5 = g.add_node(());
148        let n6 = g.add_node(());
149        let n7 = g.add_node(());
150        g.add_edge(n4, n6, ());
151        g.add_edge(n6, n7, ());
152        g.add_edge(n5, n7, ());
153
154        assert_eq!(
155            find_bridges(&g),
156            vec![(n3, n1), (n2, n3), (n0, n2), (n7, n5), (n6, n7), (n4, n6)]
157        );
158
159        g.add_edge(n5, n4, ());
160        assert_eq!(find_bridges(&g), vec![(n3, n1), (n2, n3), (n0, n2)]);
161    }
162}
graphalgs/connect/find_bridges.rs

graphalgs/connect/
find_bridges.rs
