## biconnected-components

Find biconnected components in a graph

### 3 releases(breaking)

 0.3.0 Apr 3, 2024 Mar 22, 2024 Jul 20, 2023

#849 in Math

MIT/Apache

14KB
302 lines

# 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:?}");
}
``````

### `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));
``````

~2MB
~30K SLoC