Function bridges 

pub fn bridges<G>(graph: &G) -> Vec<(NodeId, NodeId)>
where
    G: Graph<Weight = f64>,

Finds all bridges in an undirected graph using Tarjan’s algorithm.

A bridge (also called a cut edge) is an edge whose removal increases the number of connected components — i.e., it is the only path between some pair of nodes.

Algorithm

DFS assigns each node a discovery time (disc). The low-link value (low[u]) is the smallest discovery time reachable from the subtree rooted at u via back-edges. An edge (u, v) is a bridge iff low[v] > disc[u]: the subtree at v cannot reach u or any earlier node without crossing this edge.

Returns

A Vec of bridge edges (source, target). For undirected graphs each bridge is returned once (in the direction it was discovered by DFS).

Complexity

O(V + E).

Examples

use graph_core::{AdjacencyList, Graph};
use graph_spanning::bridges;

// Graph: 0-1-2-3, with extra edge 0-2 (making 0-1-2 a cycle).
// The only bridge is 2-3.
let mut g: AdjacencyList<()> = AdjacencyList::undirected();
let n: Vec<_> = (0..4).map(|_| g.add_node(())).collect();
g.add_edge(n[0], n[1], 1.0).unwrap();
g.add_edge(n[1], n[2], 1.0).unwrap();
g.add_edge(n[0], n[2], 1.0).unwrap(); // back-edge, closes a cycle
g.add_edge(n[2], n[3], 1.0).unwrap(); // bridge

let b = bridges(&g);
assert_eq!(b.len(), 1);
assert!((b[0] == (n[2], n[3])) || (b[0] == (n[3], n[2])));