3 releases (breaking)

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

#849 in Math

Download history 8/week @ 2024-02-18 7/week @ 2024-02-25 114/week @ 2024-03-17 10/week @ 2024-03-24 176/week @ 2024-03-31 17/week @ 2024-04-07

132 downloads per month

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

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

Dependencies

~2MB
~30K SLoC