Function articulation_points

pub fn articulation_points<G>(
    graph: G,
    components: Option<&mut HashMap<(<G as GraphBase>::NodeId, <G as GraphBase>::NodeId), usize>>,
) -> HashSet<G::NodeId>
where
    G: GraphProp<EdgeType = Undirected> + EdgeCount + IntoEdges + Visitable + NodeIndexable + IntoNodeIdentifiers,
    G::NodeId: Eq + Hash,

Return the articulation points of an undirected graph.

An articulation point or cut vertex is any node whose removal (along with all its incident edges) increases the number of connected components of a graph. An undirected connected graph without articulation points is biconnected.

At the same time, you can record the biconnected components in components.

Biconnected components are maximal subgraphs such that the removal of a node (and all edges incident on that node) will not disconnect the subgraph. Note that nodes may be part of more than one biconnected component. Those nodes are articulation points, or cut vertices. The algorithm computes how many biconnected components are in the graph, and assigning each component an integer label.

Note

The function implicitly assumes that there are no parallel edges or self loops. It may produce incorrect/unexpected results if the input graph has self loops or parallel edges.

Example:

use std::iter::FromIterator;
use hashbrown::{HashMap, HashSet};

use rustworkx_core::connectivity::articulation_points;
use rustworkx_core::petgraph::graph::UnGraph;
use rustworkx_core::petgraph::graph::node_index as nx;

let graph = UnGraph::<(), ()>::from_edges(&[
   (0, 1), (0, 2), (1, 2), (1, 3),
]);

let mut bicomp = HashMap::new();
let a_points = articulation_points(&graph, Some(&mut bicomp));

assert_eq!(a_points, HashSet::from_iter([nx(1)]));
assert_eq!(bicomp, HashMap::from_iter([
    ((nx(0), nx(2)), 1), ((nx(2), nx(1)), 1), ((nx(1), nx(0)), 1),
    ((nx(1), nx(3)), 0)
]));