High-performance graph algorithms for Python — from classic Dijkstra to cutting-edge research.
Logarithma is a Python library for graph algorithms built on NetworkX. It provides clean, well-tested implementations of shortest path and traversal algorithms, including the Breaking the Sorting Barrier SSSP algorithm (Duan et al., 2025) — the first Python implementation of an algorithm that surpasses Dijkstra's classical O(n log n) sorting barrier.
pip install logarithmaWith visualization support:
pip install logarithma[viz]With optional Cython acceleration for breaking_barrier_sssp:
pip install "logarithma[fast]"
python setup_ext.py build_ext --inplaceRequirements: Python 3.8+, NumPy ≥ 1.20, NetworkX ≥ 2.6
import logarithma as lg
import networkx as nx
G = nx.Graph()
G.add_edge('A', 'B', weight=4)
G.add_edge('A', 'C', weight=2)
G.add_edge('B', 'C', weight=1)
G.add_edge('C', 'D', weight=8)
# Shortest distances from A
distances = lg.dijkstra(G, 'A')
# {'A': 0, 'C': 2, 'B': 3, 'D': 10}
# Shortest path to D
result = lg.dijkstra_with_path(G, 'A', 'D')
print(result['path']) # ['A', 'C', 'D']
print(result['distance']) # 10Dijkstra — O(E + V log V), non-negative weights, directed & undirected
distances = lg.dijkstra(G, source='A')
result = lg.dijkstra_with_path(G, source='A', target='D')A* (A-Star) — heuristic-guided, optimal with admissible heuristic
from logarithma import astar, euclidean_heuristic, manhattan_heuristic, haversine_heuristic
pos = {'A': (0, 0), 'B': (3, 0), 'C': (3, 4)}
result = astar(G, 'A', 'C', heuristic=euclidean_heuristic(pos))
print(result['distance']) # 5
print(result['path']) # ['A', 'B', 'C']Bellman-Ford — O(V·E), supports negative-weight edges and cycle detection
from logarithma import bellman_ford, bellman_ford_path, NegativeCycleError
DG = nx.DiGraph()
DG.add_edge('A', 'B', weight=4)
DG.add_edge('B', 'C', weight=-3)
result = bellman_ford(DG, 'A')
# distances: {'A': 0, 'B': 4, 'C': 1}
try:
bellman_ford(graph_with_cycle, 'A')
except NegativeCycleError as e:
print(e.cycle) # reconstructed cycle nodesBidirectional Dijkstra — simultaneous forward/backward search, ~2× faster for point-to-point
result = lg.bidirectional_dijkstra(G, source='A', target='D')
print(result['distance'])
print(result['path'])Floyd-Warshall — O(V³), all-pairs shortest paths, negative weights
result = lg.floyd_warshall(G)
print(result['distances']['A']['D']) # shortest distance A→D
path = lg.floyd_warshall_path(G, 'A', 'D')
print(path) # ['A', 'C', 'D']When to use: All-pairs distances on dense graphs (E ≈ V²). Graph diameter, transitive closure, distance matrices.
Johnson's — O(V² log V + VE), all-pairs shortest paths for sparse graphs
result = lg.johnson(G)
print(result['distances']['A']['D'])
path = lg.johnson_path(G, 'A', 'D')
print(path) # ['A', 'C', 'D']When to use: All-pairs distances on sparse graphs (E ≪ V²), especially with negative weights. Faster than Floyd-Warshall when the graph is sparse.
Breaking the Sorting Barrier SSSP — O(m log²/³ n), directed graphs, non-negative weights
The first Python implementation of Duan, Mao, Mao, Shu, Yin (2025) — arXiv:2504.17033v2. Breaks Dijkstra's classical Ω(n log n) sorting barrier for sparse directed graphs. Optional Cython acceleration available in v0.6.0.
import networkx as nx
import logarithma as lg
G = nx.DiGraph()
G.add_edge('s', 'A', weight=2)
G.add_edge('s', 'B', weight=5)
G.add_edge('A', 'C', weight=1)
G.add_edge('B', 'C', weight=2)
distances = lg.breaking_barrier_sssp(G, 's')
# {'s': 0, 'A': 2, 'B': 5, 'C': 3}Performance (v0.6.0, sparse graphs m ≈ 2n):
| n | Dijkstra | Breaking Barrier | Ratio |
|---|---|---|---|
| 500 | 0.8ms | 61ms | 75× |
| 1000 | 1.7ms | 47ms | 26× |
| 2000 | 3.4ms | 74ms | 21× |
The algorithm is asymptotically optimal (O(m log²/³ n) vs Dijkstra's O(m + n log n)) — the practical crossover point requires very large n. Cython acceleration reduces the constant factor ~5–7× vs pure Python.
BFS and DFS with path reconstruction and cycle detection:
# BFS — shortest path by edge count
distances = lg.bfs(G, source='A')
result = lg.bfs_path(G, source='A', target='D')
# DFS — traversal order, path finding, cycle detection
visited = lg.dfs(G, source='A') # recursive (default)
visited = lg.dfs(G, source='A', mode='iterative')
path = lg.dfs_path(G, source='A', target='D')
has_cycle, cycle = lg.detect_cycle(G)34 utility functions across 4 categories:
from logarithma.utils import (
# Generators
generate_random_graph, generate_grid_graph, generate_scale_free_graph,
# Validators
is_connected, is_dag, has_negative_weights, validate_graph,
# Converters
to_adjacency_matrix, from_edge_list, to_graphml,
# Metrics
graph_density, diameter, graph_summary,
)
G = generate_random_graph(n=100, edge_prob=0.1, weighted=True, seed=42)
print(graph_summary(G))
# {'nodes': 100, 'edges': 491, 'density': 0.099, 'avg_degree': 9.82, ...}Kruskal — O(E log E), Union-Find with path compression
result = lg.kruskal_mst(G)
print(result['mst_edges']) # [(u, v, weight), ...]
print(result['total_weight'])
print(result['num_components']) # 1 = spanning tree, >1 = spanning forestPrim — O(E + V log V), min-heap based
result = lg.prim_mst(G, start='A')Edmonds-Karp max flow — O(V·E²), deterministic
result = lg.max_flow(G, source='s', sink='t')
print(result['flow_value']) # total max flow
print(result['flow_dict']) # flow on each edgeTarjan SCC — O(V+E), iterative, returns SCCs in reverse topological order
sccs = lg.tarjan_scc(G) # List[List[node]]
for scc in sccs:
print(scc)Topological Sort — O(V+E), DFS or Kahn method
from logarithma import NotDAGError
order = lg.topological_sort(G, method='dfs') # or 'kahn'
try:
order = lg.topological_sort(cyclic_graph)
except NotDAGError as e:
print(e.cycle) # detected cycle24 visualization functions — requires pip install logarithma[viz].
General graph plotting:
from logarithma.visualization import plot_graph, plot_shortest_path, plot_traversal
plot_graph(G, layout='spring', title='My Graph')
plot_shortest_path(G, path, title='Shortest Path')
plot_traversal(G, visited_order, title='BFS Traversal')Algorithm-specific visualizations:
from logarithma.visualization import (
plot_astar_search, # expanded nodes, open set, heuristic values
plot_bellman_ford_result, # negative edges (dashed red), distance labels
plot_negative_cycle, # cycle nodes/edges highlighted in red
plot_bidirectional_search, # forward/backward frontiers, meeting point
plot_shortest_path_comparison, # Dijkstra vs A* vs BiDijkstra side by side
plot_breaking_barrier_result, # distance gradient colouring, path highlight
plot_dfs_tree, # tree/back/cross edges, discovery-finish times
# MST
plot_mst, # MST edges highlighted on original graph
plot_mst_comparison, # Kruskal vs Prim side by side
plot_kruskal_steps, # step-by-step Kruskal animation
# Network Flow
plot_flow_network, # flow/capacity labels, saturated/partial/empty
plot_flow_paths, # active flow paths (width ∝ flow)
# Graph Properties
plot_scc, # each SCC a distinct colour + condensation DAG
plot_topological_order, # left-to-right layered layout with rank numbers
)
# Breaking Barrier — distance gradient + path to target
distances = lg.breaking_barrier_sssp(G, 's')
plot_breaking_barrier_result(G, 's', distances, highlight_targets=['C'])
# DFS tree — edge classification + discovery/finish timestamps
plot_dfs_tree(G, source='A', show_discovery_finish=True, show_depth=True)
# MST step-by-step
plot_kruskal_steps(G, max_steps=6)
# SCC with condensation DAG
plot_scc(G, show_condensation=True)All algorithms raise descriptive exceptions from a unified hierarchy:
from logarithma.algorithms.exceptions import (
GraphError, # base class for all logarithma errors
EmptyGraphError, # graph has no nodes
NodeNotFoundError, # source or target not in graph (.node, .role)
NegativeWeightError, # negative edge in Dijkstra/A*/BiDijkstra
NegativeCycleError, # Bellman-Ford detected a cycle (.cycle)
InvalidModeError, # invalid mode string (.mode, .valid_modes)
NotDAGError, # topological_sort called on cyclic graph (.cycle)
UndirectedGraphRequiredError, # DiGraph passed to MST algorithm
)
try:
result = bellman_ford(G, source='A')
except NegativeCycleError as e:
print(e.cycle) # ['A', 'B', 'C', 'A']
except NodeNotFoundError as e:
print(e.node, e.role) # 'Z', 'source'All exceptions are subclasses of both GraphError and ValueError, so existing except ValueError blocks remain compatible.
| Algorithm | Time | Notes |
|---|---|---|
| Dijkstra | O(E + V log V) |
non-negative weights |
| A* | O(b^d) practical |
heuristic-guided |
| Bellman-Ford | O(V · E) |
negative weights, cycle detection |
| Bidirectional Dijkstra | O(E + V log V) ~2× faster |
point-to-point |
| Floyd-Warshall | O(V³) |
all-pairs SP, dense graphs, negative weights |
| Johnson's | O(V² log V + VE) |
all-pairs SP, sparse graphs, negative weights |
| Breaking Barrier SSSP | O(m log²/³ n) |
directed, breaks sorting barrier |
| BFS / DFS | O(V + E) |
traversal |
| Kruskal MST | O(E log E) |
undirected, spanning forest |
| Prim MST | O(E + V log V) |
undirected, spanning forest |
| Max Flow (Edmonds-Karp) | O(V · E²) |
directed/undirected |
| Tarjan SCC | O(V + E) |
directed/undirected |
| Topological Sort | O(V + E) |
DAG only |
Full documentation and examples: softdevcan.github.io/logarithma
Logarithma's primary goal is implementing the Breaking the Sorting Barrier for Directed Single-Source Shortest Paths (Duan, Mao, Mao, Shu, Yin — arXiv:2504.17033v2, STOC 2025 Best Paper), which surpasses the classical O(m + n log n) sorting barrier for directed SSSP. This is the first Python implementation of this algorithm.
Key components:
- BMSSP (Bounded Multi-Source Shortest Path) — recursive divide-and-conquer framework
- BlockHeap (Lemma 3.3) — block-based linked list data structure with Insert / BatchPrepend / Pull
- Constant-degree transform (Frederickson 1983) — graph preprocessing for theoretical guarantees
- Assumption 2.1 — lexicographic tiebreaking for deterministic predecessor forest
- Cython acceleration (v0.6.0) —
_should_relaxascdef inline nogil, typed memoryviews for ~5–7× speedup over v0.5.0
MIT — see LICENSE for details.