agenticraft_foundation.topology.laplacian

Laplacian matrix analysis — spectral decomposition, algebraic connectivity (\(\lambda_2\)), and consensus convergence bounds.

Graph Laplacian analysis for network topology optimization.

This module provides spectral analysis tools for understanding and optimizing distributed system topologies based on graph-theoretic principles.

Key concepts: - Algebraic Connectivity (λ₂): Second smallest eigenvalue of Laplacian - Fiedler Vector: Eigenvector corresponding to λ₂ - Consensus Convergence: T = O(n log n / λ₂)

References: - Fiedler, M. (1973). Algebraic connectivity of graphs. - Olfati-Saber, R. (2006). Flocking for multi-agent dynamic systems.

TopologyType

Bases: str, Enum

Common network topology types.

Node dataclass

A node in the network graph.

ATTRIBUTE	DESCRIPTION
id	Unique identifier TYPE: str
neighbors	Set of neighbor node IDs TYPE: set[str]
weight	Optional weight for weighted graphs TYPE: float
metadata	Additional node metadata TYPE: dict[str, Any]

Edge dataclass

An edge in the network graph.

ATTRIBUTE	DESCRIPTION
source	Source node ID TYPE: str
target	Target node ID TYPE: str
weight	Edge weight (default 1.0) TYPE: float

LaplacianAnalysis dataclass

Results of Laplacian spectral analysis.

ATTRIBUTE	DESCRIPTION
num_nodes	Number of nodes in the graph TYPE: int
num_edges	Number of edges in the graph TYPE: int
algebraic_connectivity	Second smallest eigenvalue (λ₂) TYPE: float
spectral_gap	Gap between λ₁ and λ₂ TYPE: float
fiedler_vector	Eigenvector for λ₂ (maps node ID to value) TYPE: dict[str, float]
eigenvalues	All eigenvalues in ascending order TYPE: list[float]
consensus_bound	Upper bound on consensus convergence time TYPE: float
diameter_estimate	Estimated graph diameter from spectral properties TYPE: float
bottleneck_edges	Edges with high Fiedler values (potential bottlenecks) TYPE: list[tuple[str, str]]
suggested_edges	Suggested edges to add for improved connectivity TYPE: list[tuple[str, str]]
is_connected	Whether the graph is connected TYPE: bool

summary()

Generate human-readable summary.

NetworkGraph

Network graph for topology analysis.

Provides methods for building and analyzing network topologies using graph Laplacian spectral analysis.

node_count property

Number of nodes.

edge_count property

Number of edges.

__init__()

Initialize empty graph.

add_node(node_id, weight=1.0, **metadata)

Add a node to the graph.

PARAMETER	DESCRIPTION
node_id	Unique node identifier TYPE: str
weight	Node weight TYPE: float DEFAULT: 1.0
**metadata	Additional metadata TYPE: Any DEFAULT: {}

RETURNS	DESCRIPTION
Node	The created Node

add_edge(source, target, weight=1.0, bidirectional=True)

Add an edge to the graph.

PARAMETER	DESCRIPTION
source	Source node ID TYPE: str
target	Target node ID TYPE: str
weight	Edge weight TYPE: float DEFAULT: 1.0
bidirectional	If True, add edge in both directions TYPE: bool DEFAULT: True

RETURNS	DESCRIPTION
Edge	The created Edge

remove_node(node_id)

Remove a node and all its edges.

PARAMETER	DESCRIPTION
node_id	Node to remove TYPE: str

RETURNS	DESCRIPTION
bool	True if node was removed

get_node(node_id)

Get a node by ID.

get_nodes()

Get all nodes.

get_edges()

Get all edges.

analyze()

Perform spectral analysis on the graph.

RETURNS	DESCRIPTION
LaplacianAnalysis	LaplacianAnalysis with spectral properties

create_ring(n, node_prefix='node') classmethod

Create a ring topology.

PARAMETER	DESCRIPTION
n	Number of nodes TYPE: int
node_prefix	Prefix for node IDs TYPE: str DEFAULT: 'node'

RETURNS	DESCRIPTION
NetworkGraph	NetworkGraph with ring topology

create_complete(n, node_prefix='node') classmethod

Create a complete (fully connected) topology.

PARAMETER	DESCRIPTION
n	Number of nodes TYPE: int
node_prefix	Prefix for node IDs TYPE: str DEFAULT: 'node'

RETURNS	DESCRIPTION
NetworkGraph	NetworkGraph with complete topology

create_star(n, node_prefix='node') classmethod

Create a star topology.

PARAMETER	DESCRIPTION
n	Number of nodes (including center) TYPE: int
node_prefix	Prefix for node IDs TYPE: str DEFAULT: 'node'

RETURNS	DESCRIPTION
NetworkGraph	NetworkGraph with star topology

create_mesh(rows, cols, node_prefix='node') classmethod

Create a 2D mesh/grid topology.

PARAMETER	DESCRIPTION
rows	Number of rows TYPE: int
cols	Number of columns TYPE: int
node_prefix	Prefix for node IDs TYPE: str DEFAULT: 'node'

RETURNS	DESCRIPTION
NetworkGraph	NetworkGraph with mesh topology

analyze_consensus_time(graph, epsilon=0.01)

Estimate consensus convergence time.

For linear consensus protocols, convergence time is bounded by: T = O(log(1/ε) / λ₂)

PARAMETER	DESCRIPTION
graph	Network graph to analyze TYPE: NetworkGraph
epsilon	Convergence tolerance TYPE: float DEFAULT: 0.01

RETURNS	DESCRIPTION
float	Estimated convergence time

compare_topologies(topologies)

Compare multiple network topologies.

PARAMETER	DESCRIPTION
topologies	Dictionary mapping topology name to graph TYPE: dict[str, NetworkGraph]

RETURNS	DESCRIPTION
dict[str, LaplacianAnalysis]	Dictionary mapping topology name to analysis

optimal_topology_for_consensus(n, max_edges=None)

Find optimal topology for consensus with edge budget.

If unconstrained, complete graph is optimal (λ₂ = n). With edge constraints, we optimize for maximum λ₂.

PARAMETER	DESCRIPTION
n	Number of nodes TYPE: int
max_edges	Maximum number of edges (None = unconstrained) TYPE: int | None DEFAULT: None

RETURNS	DESCRIPTION
tuple[NetworkGraph, LaplacianAnalysis]	Tuple of (optimal graph, analysis)