Function graphalgs::connect::find_bridges

pub fn find_bridges<G>(graph: G) -> Vec<(G::NodeId, G::NodeId)>where
    G: IntoNodeIdentifiers + IntoNeighbors + NodeIndexable,

Find all bridges in a simple undirected graph.

Returns the vector of pairs (G::NodeID, G:: NodeID), representing the edges of the input graph that are bridges. The order of the vertices in the pair and the order of the edges themselves are arbitrary.

Examples

use graphalgs::connect::find_bridges;
use petgraph::graph::UnGraph;

// Create the following graph:
// 0----1    4
//      | __/|
// 5----2/---3

let mut g = UnGraph::new_undirected();
let n0 = g.add_node(());
let n1 = g.add_node(());
let n2 = g.add_node(());
let n3 = g.add_node(());
let n4 = g.add_node(());
let n5 = g.add_node(());
g.add_edge(n0, n1, ());
g.add_edge(n1, n2, ());
g.add_edge(n2, n3, ());
g.add_edge(n3, n4, ());
g.add_edge(n2, n4, ());
g.add_edge(n5, n2, ());

// The bridges in this graph are the undirected edges {2, 5}, {1, 2}, {0, 1}.
assert_eq!(find_bridges(&g), vec![(n2, n5), (n1, n2), (n0, n1)]);