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	Max crash-stop faults tolerable — min(κ - 1, (n-1)//2). TYPE: int
byzantine_tolerance	Max Byzantine faults — min((κ - 1)//2, (n-1)//3). This is structural capacity, not a realized-BFT guarantee: it also requires a running voting/agreement mechanism over the replicas. 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

classical_fault_tolerance(n_agents, vertex_connectivity)

Maximum (crash-stop, Byzantine) faults from the classical agreement bounds.

Single source of truth for the classical fault-tolerance bounds, shared by :meth:ConnectivityAnalyzer.analyze_fault_tolerance and the resilience diagnostic so the two never diverge.

With n agents and vertex connectivity κ (over the undirected graph):

• Crash-stop — stay connected (κ > f) and keep a quorum (n >= 2f+1)::

  f_crash = min(κ - 1, (n - 1) // 2)

• Byzantine — needs (2f+1)-connectivity (κ >= 2f+1) and a super-majority quorum (n >= 3f+1)::

  f_byz = min((κ - 1) // 2, (n - 1) // 3)

The Byzantine figure is structural capacity: necessary but not sufficient — realized tolerance also requires a running voting/agreement mechanism over the redundant agents. κ is undirected, so f_byz cannot see directed source-multiplicity; treat it as a coarse structural proxy.

PARAMETER	DESCRIPTION
n_agents	Number of agents (graph nodes). TYPE: int
vertex_connectivity	κ — minimum nodes to remove to disconnect. TYPE: int

RETURNS	DESCRIPTION
tuple[int, int]	(f_crash, f_byz) — both clamped at 0.

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)