agenticraft_foundation.topology.connectivity

Graph connectivity analysis — vertex connectivity, edge connectivity, bridge detection, and connected components.

Network connectivity analysis for distributed systems.

This module provides tools for analyzing and verifying network connectivity properties important for distributed consensus and fault tolerance.

Key concepts: - k-connectivity: Graph remains connected after removing any k-1 nodes - Vertex cuts: Minimum set of vertices whose removal disconnects the graph - Robustness: Ability to maintain connectivity under failures

ConnectivityAnalysis dataclass

Results of connectivity analysis.

ATTRIBUTE	DESCRIPTION
is_connected	Whether graph is connected TYPE: bool
vertex_connectivity	Minimum nodes to remove to disconnect (κ) TYPE: int
edge_connectivity	Minimum edges to remove to disconnect (λ) TYPE: int
articulation_points	Nodes whose removal disconnects the graph TYPE: list[str]
bridges	Edges whose removal disconnects the graph TYPE: list[tuple[str, str]]
k_connected	Maximum k for which graph is k-connected TYPE: int
biconnected_components	List of biconnected component node sets TYPE: list[set[str]]
strongly_connected	Whether graph is strongly connected (for directed) TYPE: bool
weakly_connected	Whether underlying undirected graph is connected TYPE: bool

summary()

Generate human-readable summary.

can_tolerate_failures(f)

Check if graph can tolerate f node failures.

PARAMETER	DESCRIPTION
f	Number of failures TYPE: int

RETURNS	DESCRIPTION
bool	True if graph remains connected after f failures

FaultToleranceAnalysis dataclass

Analysis of fault tolerance capabilities.

ATTRIBUTE	DESCRIPTION
crash_tolerance	Maximum crash failures tolerable (f < n/2) TYPE: int
byzantine_tolerance	Maximum Byzantine failures (f < n/3) TYPE: int
critical_nodes	Nodes whose failure most impacts connectivity TYPE: list[str]
redundancy_score	Score indicating redundancy level (0-1) TYPE: float
suggested_redundancy	Suggested edges to improve fault tolerance TYPE: list[tuple[str, str]]

summary()

Generate human-readable summary.

ConnectivityAnalyzer

Analyzes network connectivity properties.

__init__(graph)

Initialize analyzer with graph.

PARAMETER	DESCRIPTION
graph	Network graph to analyze TYPE: NetworkGraph

analyze()

Perform full connectivity analysis.

RETURNS	DESCRIPTION
ConnectivityAnalysis	ConnectivityAnalysis with results

analyze_fault_tolerance()

Analyze fault tolerance capabilities.

RETURNS	DESCRIPTION
FaultToleranceAnalysis	FaultToleranceAnalysis with results

verify_consensus_requirements(graph, fault_model='crash', f=1)

Verify graph meets consensus requirements for given fault model.

PARAMETER	DESCRIPTION
graph	Network graph TYPE: NetworkGraph
fault_model	Type of failures ("crash" or "byzantine") TYPE: str DEFAULT: 'crash'
f	Number of failures to tolerate TYPE: int DEFAULT: 1

RETURNS	DESCRIPTION
tuple[bool, str]	Tuple of (meets_requirements, explanation)