Skip to main content

minimum_size_separators

rust_igraph

Function minimum_size_separators 

Source 
pub fn minimum_size_separators(
    graph: &Graph,
) -> IgraphResult<Vec<Vec<VertexId>>>
Expand description

Find all minimum-size separating vertex sets.

A vertex set is a separator if its removal disconnects the graph. This function lists every separator of minimum cardinality (the minimum equals the graph’s vertex connectivity).

Conventions, matching igraph_minimum_size_separators:

  • If the graph is already disconnected, no separators are returned (this differs from all_minimal_st_separators).
  • Complete graphs have no vertex separators, so the result is empty.
  • For a graph whose connectivity is 1, the minimum separators are exactly the articulation points (each returned as a singleton).

Each returned separator is sorted ascending, and the list contains no duplicates. The separators themselves are returned in an arbitrary order.

The implementation follows Arkady Kanevsky, “Finding all minimum-size separating vertex sets in a graph”, Networks 23 (1993), 533–541. It computes the vertex connectivity k, takes the k largest-degree vertices X, and for each x ∈ X and each non-adjacent vertex j computes a maximum flow on the Even–Tarjan reduction; whenever the flow equals k it enumerates all minimum (x, j) vertex cuts via all_st_mincuts, deduplicating as it goes. After each (x, j) pair an edge (x, j) is added so subsequent flows discover only new separators.

For undirected graphs only.

§Errors

§Examples

use rust_igraph::{Graph, minimum_size_separators};

// Path 0-1-2: vertex 1 is the unique minimum separator.
let mut g = Graph::with_vertices(3);
g.add_edge(0, 1).unwrap();
g.add_edge(1, 2).unwrap();
let seps = minimum_size_separators(&g).unwrap();
assert_eq!(seps, vec![vec![1]]);