biconnected-components

Compute the biconnected components of a graph.

Example

use petgraph::graph::UnGraph;
use biconnected_components::Bcc;

// construct a simple graph
let g = UnGraph::<(), ()>::from_edges([
   (0, 1),
   (1, 2)
 ]);

// Get a vector of the biconnected components defined by their node indices
let bcc = g.bcc();
assert_eq!(bcc.len(), 2);
for bcc_nodes in bcc {
   println!("Found biconnected component with nodes {bcc_nodes:?}");
}

License: MIT OR Apache-2.0

lib.rs:

Compute the biconnected components of a graph.

Example

use petgraph::graph::UnGraph;
use biconnected_components::{Bcc, SplitIntoBcc};

// construct a simple graph
let g = UnGraph::<(), ()>::from_edges([
   (0, 1),
   (1, 2)
 ]);

// Get a vector of the biconnected components defined by their node indices
let bcc = g.bcc();
assert_eq!(bcc.len(), 2);
for bcc_nodes in bcc {
   println!("Found biconnected component with nodes {bcc_nodes:?}");
}

// Split up the graph into its biconnected components, that is
// two identical graphs with two nodes connected by single edge
let bcc = g.split_into_bcc();
assert_eq!(bcc.len(), 2);
assert!(bcc.iter().all(|g| g.node_count() == 2));
assert!(bcc.iter().all(|g| g.edge_count() == 1));