Module components 

Connectivity: connected components, cut vertices and bridges, vertex separators, cohesive blocks, reachability and neighborhoods.

This module binds five igraph headers:

• igraph_components.h: (weakly or strongly) connected components, decomposition into component graphs, articulation points, bridges, biconnected components and percolation curves;
• igraph_separators.h: vertex separators (sets of vertices whose removal disconnects the graph);
• igraph_cohesive_blocks.h: the Moody–White hierarchy of cohesive blocks;
• igraph_reachability.h: which vertices can reach which others, and the transitive closure;
• igraph_neighborhood.h: the vertices within a given distance of some vertices, as sets, counts or induced subgraphs.

All the graph algorithms are methods of Graph; the only free function is edgelist_percolation. The randomized percolation curves draw from the calling thread’s default random number generator, so they are reproducible after rng::seed.

Example

use igraph::prelude::*;

// Two triangles joined by the edge 2-3, plus an isolated vertex 6.
let g = Graph::from_edges(
    &[(0, 1), (1, 2), (2, 0), (2, 3), (3, 4), (4, 5), (5, 3)],
    7,
    false,
)
.unwrap();

let cc = g.connected_components(Connectedness::Weak).unwrap();
assert_eq!(cc.count, 2);
assert_eq!(cc.sizes, vec![6, 1]);
assert!(!g.is_connected(Connectedness::Weak).unwrap());

// The edge 2-3 (id 3) is the only bridge; 2 and 3 are the cut vertices.
assert_eq!(g.bridges().unwrap(), vec![3]);
let mut cut = g.articulation_points().unwrap();
cut.sort();
assert_eq!(cut, vec![2, 3]);

// Removing vertex 2 separates vertex 0 from vertex 5.
assert!(g.is_separator(2).unwrap());

// Vertices at distance at most 1 from vertex 3.
assert_eq!(g.neighborhood(3, Some(1), NeighborMode::All, 0).unwrap(), vec![vec![3, 2, 4, 5]]);

// Zachary's karate club: one component, a single cut vertex (the
// instructor, 0) and a nested hierarchy of cohesive blocks.
let karate = Graph::famous("Zachary").unwrap();
assert!(karate.is_connected(Connectedness::Weak).unwrap());
assert_eq!(karate.articulation_points().unwrap(), vec![0]);
let blocks = karate.cohesive_blocks().unwrap();
assert_eq!(blocks.cohesion, vec![1, 2, 2, 4, 3, 3, 4, 3]);

Provided functionality

Rust	C function	Purpose
Graph::connected_components	igraph_connected_components	membership, sizes and number of components
Graph::is_connected	igraph_is_connected	weak / strong connectedness test
Graph::decompose	igraph_decompose	one Graph per component
Graph::articulation_points	igraph_articulation_points	cut vertices
Graph::bridges	igraph_bridges	cut edges
Graph::biconnected_components	igraph_biconnected_components	BiconnectedComponents
Graph::is_biconnected	igraph_is_biconnected	2-vertex-connectedness test
Graph::bond_percolation	igraph_bond_percolation	giant component while adding edges
Graph::site_percolation	igraph_site_percolation	giant component while adding vertices
edgelist_percolation	igraph_edgelist_percolation	bond percolation of a bare edge list
Graph::is_separator	igraph_is_separator	does removing a vertex set disconnect the graph?
Graph::is_minimal_separator	igraph_is_minimal_separator	… and no proper subset does?
Graph::all_minimal_st_separators	igraph_all_minimal_st_separators	all minimal (s,t) separators
Graph::minimum_size_separators	igraph_minimum_size_separators	all minimum-size vertex separators
Graph::cohesive_blocks	igraph_cohesive_blocks	CohesiveBlocks hierarchy
Graph::reachability	igraph_reachability	Reachability bitsets per strong component
Graph::count_reachable	igraph_count_reachable	number of reachable vertices
Graph::transitive_closure	igraph_transitive_closure	the transitive closure graph
Graph::neighborhood_size	igraph_neighborhood_size	sizes of the k-neighborhoods
Graph::neighborhood	igraph_neighborhood	vertices of the k-neighborhoods
Graph::neighborhood_graphs	igraph_neighborhood_graphs	induced subgraphs of the k-neighborhoods

See also

• Single-source reachability: Graph::subcomponent; traversals: Graph::bfs, Graph::dfs; distances: Graph::distances.
• Quantitative connectivity (minimum cuts, Menger paths): Graph::vertex_connectivity, Graph::edge_connectivity, Graph::st_vertex_connectivity, Graph::all_st_mincuts and Graph::dominator_tree in flow.
• Forests, DAGs and orderings: Graph::is_tree, Graph::is_forest, Graph::is_dag, Graph::topological_sorting.
• Subgraphs of components or neighborhoods: Graph::induced_subgraph; graphs whose edges are k-neighborhoods: Graph::connect_neighborhood, Graph::graph_power.
• Another nested “cohesion” decomposition: Graph::coreness (k-cores).

Structs

BiconnectedComponents

The biconnected components of a graph, see Graph::biconnected_components.

BondPercolation

A bond (edge) percolation curve, see Graph::bond_percolation and edgelist_percolation.

CohesiveBlocks

The cohesive block hierarchy of a graph, see Graph::cohesive_blocks.

ConnectedComponents

The connected components of a graph, see Graph::connected_components.

Reachability

Reachability information, see Graph::reachability.

SitePercolation

A site (vertex) percolation curve, see Graph::site_percolation.

Functions

edgelist_percolation

Bond percolation curve of a bare list of vertex pairs.