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.

CohesiveBlocks

Result of cohesive_blocks.

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.

ReachabilityResult

Result of a reachability analysis.

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

Enums

ConnectednessMode

Connectivity mode for directed graphs.

ReachabilityMode

Direction mode for reachability in directed graphs.

SubcomponentMode

Direction mode for subcomponent search.

Functions

all_minimal_st_separators

List all vertex sets that are minimal (s,t) separators for some s and t.

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.

cohesive_blocks

Identify the hierarchical cohesive block structure of a graph.

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.

is_connected

Tests whether the graph is connected.

is_minimal_separator

Check whether a set of vertices is a minimal separator.

is_separator

Check whether a set of vertices is a separator of the graph.

minimum_size_separators

Find all minimum-size separating vertex sets.

reachability

Compute per-component reachability bitsets.

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.

subcomponent

Returns all vertices reachable from source following edges in the specified mode.

transitive_closure

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