graph_spanning/
bridges.rs

1use graph_core::{Graph, NodeId};
2use std::collections::HashMap;
3
4/// Finds all **bridges** in an undirected graph using Tarjan's algorithm.
5///
6/// A bridge (also called a cut edge) is an edge whose removal increases the
7/// number of connected components — i.e., it is the only path between some
8/// pair of nodes.
9///
10/// # Algorithm
11///
12/// DFS assigns each node a **discovery time** (`disc`). The **low-link value**
13/// (`low[u]`) is the smallest discovery time reachable from the subtree rooted
14/// at `u` via back-edges. An edge `(u, v)` is a bridge iff `low[v] > disc[u]`:
15/// the subtree at `v` cannot reach `u` or any earlier node without crossing
16/// this edge.
17///
18/// # Returns
19///
20/// A `Vec` of bridge edges `(source, target)`. For undirected graphs each
21/// bridge is returned once (in the direction it was discovered by DFS).
22///
23/// # Complexity
24///
25/// O(V + E).
26///
27/// # Examples
28///
29/// ```
30/// use graph_core::{AdjacencyList, Graph};
31/// use graph_spanning::bridges;
32///
33/// // Graph: 0-1-2-3, with extra edge 0-2 (making 0-1-2 a cycle).
34/// // The only bridge is 2-3.
35/// let mut g: AdjacencyList<()> = AdjacencyList::undirected();
36/// let n: Vec<_> = (0..4).map(|_| g.add_node(())).collect();
37/// g.add_edge(n[0], n[1], 1.0).unwrap();
38/// g.add_edge(n[1], n[2], 1.0).unwrap();
39/// g.add_edge(n[0], n[2], 1.0).unwrap(); // back-edge, closes a cycle
40/// g.add_edge(n[2], n[3], 1.0).unwrap(); // bridge
41///
42/// let b = bridges(&g);
43/// assert_eq!(b.len(), 1);
44/// assert!((b[0] == (n[2], n[3])) || (b[0] == (n[3], n[2])));
45/// ```
46pub fn bridges<G>(graph: &G) -> Vec<(NodeId, NodeId)>
47where
48    G: Graph<Weight = f64>,
49{
50    let mut state = BridgeState {
51        disc: HashMap::new(),
52        low: HashMap::new(),
53        timer: 0,
54        result: Vec::new(),
55    };
56
57    for node in graph.nodes() {
58        if !state.disc.contains_key(&node) {
59            dfs_bridge(graph, node, None, &mut state);
60        }
61    }
62
63    state.result
64}
65
66struct BridgeState {
67    disc: HashMap<NodeId, usize>,
68    low: HashMap<NodeId, usize>,
69    timer: usize,
70    result: Vec<(NodeId, NodeId)>,
71}
72
73fn dfs_bridge<G>(graph: &G, node: NodeId, parent: Option<NodeId>, state: &mut BridgeState)
74where
75    G: Graph<Weight = f64>,
76{
77    state.disc.insert(node, state.timer);
78    state.low.insert(node, state.timer);
79    state.timer += 1;
80
81    for (neighbour, _) in graph.neighbors(node) {
82        if !state.disc.contains_key(&neighbour) {
83            // Tree edge: recurse.
84            dfs_bridge(graph, neighbour, Some(node), state);
85
86            // Update low[node] from the subtree.
87            let child_low = state.low[&neighbour];
88            let node_low = state.low.get_mut(&node).unwrap();
89            if child_low < *node_low {
90                *node_low = child_low;
91            }
92
93            // Bridge condition: subtree at neighbour cannot reach node or earlier.
94            if state.low[&neighbour] > state.disc[&node] {
95                state.result.push((node, neighbour));
96            }
97        } else if Some(neighbour) != parent {
98            // Back edge: update low[node].
99            let neighbour_disc = state.disc[&neighbour];
100            let node_low = state.low.get_mut(&node).unwrap();
101            if neighbour_disc < *node_low {
102                *node_low = neighbour_disc;
103            }
104        }
105    }
106}
107
108/// Returns true if the graph has no bridges (is 2-edge-connected).
109///
110/// # Examples
111///
112/// ```
113/// use graph_core::{AdjacencyList, Graph};
114/// use graph_spanning::bridges::is_two_edge_connected;
115///
116/// // Complete graph K4 has no bridges.
117/// let mut g: AdjacencyList<()> = AdjacencyList::undirected();
118/// let n: Vec<_> = (0..4).map(|_| g.add_node(())).collect();
119/// for i in 0..4 {
120///     for j in i+1..4 {
121///         g.add_edge(n[i], n[j], 1.0).unwrap();
122///     }
123/// }
124/// assert!(is_two_edge_connected(&g));
125/// ```
126pub fn is_two_edge_connected<G>(graph: &G) -> bool
127where
128    G: Graph<Weight = f64>,
129{
130    graph.node_count() > 0 && bridges(graph).is_empty()
131}
graph_spanning/bridges.rs

graph_spanning/
bridges.rs
