Module connectivity 

Connectivity algorithms. Phase 1: ALGO-CC-001 (weak connected components), ALGO-CC-002 (strongly connected components), ALGO-CC-010 (articulation points), ALGO-CC-013 (is_biconnected), ALGO-CC-014 (bridges), ALGO-CC-020 (reachability counts), ALGO-CC-021 (reachability matrix), ALGO-CC-022 (transitive closure).

Structs

BiconnectedComponents

Output of biconnected_components.

ConnectedComponents

Result of a weak connected-components scan.

EdgelistPercolation

Outputs of edgelist_percolation. Same length as the input edge slice. giant_size[i] is the size of the largest component after edge i is added; vertex_count[i] is the number of distinct vertices touched by edges 0..=i.

SitePercolation

Outputs of site_percolation. Same length as vertex_order. giant_size[i] is the size of the largest connected component after vertex vertex_order[i] is activated; edge_count[i] is the cumulative number of edges added through step i (an edge is “added” the moment both its endpoints become active).

Functions

articulation_points

Articulation points of graph (returns vertices in upstream’s DFS-discovery order).

biconnected_components

Compute the biconnected components of graph.

bond_percolation

Bond percolation: the size of the largest component as edges of graph are added in the order specified by edge_order.

bridges

Bridges of graph — edges whose removal would increase the number of (weakly) connected components.

connected_components

Compute the weak connected components of graph.

count_reachable

Per-vertex count of reachable vertices (including the vertex itself).

decompose

Decompose graph into its weakly connected components.

edgelist_percolation

Percolation curve as a sequence of vertex-pair edges is added.

is_biconnected

Check whether graph is biconnected.

reachability_matrix

Dense reachability matrix of graph. result[i][j] is true iff vertex j is reachable from i in zero or more steps.

site_percolation

Site percolation: the size of the largest component as vertices (sites) of graph are activated in the order specified by vertex_order.

strongly_connected_components

Compute the strongly connected components of graph.

transitive_closure

Transitive closure of graph. The returned graph shares the same vertex count and direction as the input.