petgraph/algo/
bridges.rs

1use crate::visit::{
2    EdgeRef, IntoEdgeReferences, IntoNeighbors, IntoNodeIdentifiers, NodeIndexable,
3};
4
5use alloc::{vec, vec::Vec};
6
7/// Find all [bridges](https://en.wikipedia.org/wiki/Bridge_(graph_theory)) in a simple undirected graph.
8///
9/// # Arguments
10/// * `graph`: a simple undirected graph.
11///
12/// # Returns
13/// * `impl Iterator`:  the iterator of edge references `G::EdgeRef` representing the edges
14///   of the input graph that are bridges. The order of the edges is arbitrary.
15///
16/// # Complexity
17/// * Time complexity: **O(|V| + |E|)**.
18/// * Auxiliary space: **O(|V|)**.
19///
20/// where **|V|** is the number of nodes and **|E|** is the number of edges.
21///
22///
23/// # Examples
24///
25/// ```
26/// use petgraph::algo::bridges::bridges;
27/// use petgraph::graph::UnGraph;
28/// use petgraph::visit::EdgeRef;
29///
30/// // Create the following graph:
31/// // 0----1    4
32/// //      | __/|
33/// // 5----2/---3
34///
35/// let mut g = UnGraph::new_undirected();
36/// let n0 = g.add_node(());
37/// let n1 = g.add_node(());
38/// let n2 = g.add_node(());
39/// let n3 = g.add_node(());
40/// let n4 = g.add_node(());
41/// let n5 = g.add_node(());
42/// let e0 = g.add_edge(n0, n1, ());
43/// let e1 = g.add_edge(n1, n2, ());
44/// let e2 = g.add_edge(n2, n3, ());
45/// let e3 = g.add_edge(n3, n4, ());
46/// let e4 = g.add_edge(n2, n4, ());
47/// let e5 = g.add_edge(n5, n2, ());
48///
49/// let bridges: Vec<_> = bridges(&g).map(|edge_ref| edge_ref.id()).collect();
50///
51/// // The bridges in this graph are the undirected edges {2, 5}, {1, 2}, {0, 1}.
52/// assert_eq!(bridges, vec![e0, e1, e5]);
53/// ```
54pub fn bridges<G>(graph: G) -> impl Iterator<Item = G::EdgeRef>
55where
56    G: IntoNodeIdentifiers + IntoNeighbors + NodeIndexable + IntoEdgeReferences,
57{
58    let mut clock: usize = 0usize;
59    // If and when a node was visited by the dfs
60    let mut visit_time = vec![None; graph.node_bound()];
61    // Lowest time on a node that is the target of a back-edge from the subtree rooted
62    // at the indexed node.
63    let mut earliest_backedge = vec![usize::MAX; graph.node_bound()];
64
65    for start in 0..graph.node_bound() {
66        // If node hasn't been visited yet, make it the root of a new dfs-tree in the forest.
67        if visit_time[start].is_none() {
68            visit_time[start] = Some(clock);
69            clock += 1;
70
71            // Perform a DFS starting at start
72            let start = graph.from_index(start);
73            let mut stack: Vec<(G::NodeId, G::Neighbors)> = vec![(start, graph.neighbors(start))];
74
75            while let Some((stack_frame, rest_of_stack)) = stack.split_last_mut() {
76                let &mut (node, ref mut neighbors) = stack_frame;
77                let parent = rest_of_stack.last().map(|&(n, _)| n);
78
79                let node_index = graph.to_index(node);
80
81                if let Some(child) = neighbors.next() {
82                    // Pre-order DFS
83                    if parent != Some(child) {
84                        let child_index = graph.to_index(child);
85
86                        if let Some(time) = visit_time[child_index] {
87                            earliest_backedge[node_index] = earliest_backedge[node_index].min(time);
88                        } else {
89                            visit_time[child_index] = Some(clock);
90                            clock += 1;
91                            stack.push((child, graph.neighbors(child)));
92                        }
93                    }
94                } else {
95                    // Post-order DFS
96                    if let Some(parent) = parent {
97                        let parent_index = graph.to_index(parent);
98                        earliest_backedge[parent_index] =
99                            earliest_backedge[parent_index].min(earliest_backedge[node_index]);
100                    }
101                    stack.pop();
102                }
103            }
104        }
105    }
106
107    graph.edge_references().filter(move |edge| {
108        let source_index = graph.to_index(edge.source());
109        let target_index = graph.to_index(edge.target());
110
111        // All nodes have been visited by the time we return, so unwraps are safe.
112        // The node with the lower visit time is the "parent" in the dfs-forest created above.
113        let (parent, node) =
114            if visit_time[source_index].unwrap() < visit_time[target_index].unwrap() {
115                (source_index, target_index)
116            } else {
117                (target_index, source_index)
118            };
119
120        // If there's no back-edge to before parent, then this the only way from parent to here
121        // is directly from parent, so it's a bridge edge.
122        earliest_backedge[node] > visit_time[parent].unwrap()
123    })
124}
125
126#[cfg(test)]
127mod tests {
128    use super::*;
129    use crate::graph::EdgeReference;
130    use crate::graph::UnGraph;
131    use crate::visit::EdgeRef;
132
133    #[test]
134    fn test_bridges() {
135        let mut g = UnGraph::<i8, i8>::new_undirected();
136        let bridge_nodes = |g: &_| {
137            bridges(g)
138                .map(|e: EdgeReference<_>| (e.source(), e.target()))
139                .collect::<Vec<_>>()
140        };
141
142        assert_eq!(bridge_nodes(&g), vec![]);
143        let n0 = g.add_node(0);
144        assert_eq!(bridge_nodes(&g), vec![]);
145        let n1 = g.add_node(1);
146        assert_eq!(bridge_nodes(&g), vec![]);
147        g.add_edge(n0, n1, 0);
148        assert_eq!(bridge_nodes(&g), vec![(n0, n1)]);
149        let n2 = g.add_node(2);
150        assert_eq!(bridge_nodes(&g), vec![(n0, n1)]);
151        g.add_edge(n2, n1, 1);
152        assert_eq!(bridge_nodes(&g), vec![(n0, n1), (n2, n1)]);
153        g.add_edge(n0, n2, 2);
154        assert_eq!(bridge_nodes(&g), vec![]);
155        let n3 = g.add_node(3);
156        let n4 = g.add_node(4);
157        g.add_edge(n2, n3, 3);
158        g.add_edge(n3, n4, 4);
159        assert_eq!(bridge_nodes(&g), vec![(n2, n3), (n3, n4)]);
160        g.add_edge(n3, n0, 5);
161        assert_eq!(bridge_nodes(&g), vec![(n3, n4)]);
162    }
163}
petgraph/algo/bridges.rs

petgraph/algo/
bridges.rs
