v0.6.0 — Cython Acceleration & All-Pairs Shortest Path

Performance & Optimization

• Cython acceleration for breaking_barrier_sssp (~5-7x speedup over v0.5.0)
  • block_heap.pyx: cdef classes, C-level double arithmetic
  • breaking_barrier_core.pyx: _should_relax as cdef inline nogil, typed memoryviews
  • Automatic fallback to pure Python when Cython extensions are not compiled
• Pure-Python optimizations: node ID integer mapping, repr() eliminated (~11% runtime)
• graph_transform.py: batch NetworkX operations to reduce per-edge overhead

New Algorithms

• Floyd-Warshall: O(V³) all-pairs shortest paths with negative weight support and cycle detection
• Johnson's: O(V² log V + VE) all-pairs shortest paths optimized for sparse graphs
• Path reconstruction helpers: floyd_warshall_path(), johnson_path()

Documentation

• "When to use" guidance added for every algorithm (index.html, README)
• Breaking Barrier SSSP full section with performance benchmarks
• Floyd-Warshall vs Johnson comparison table
• Use-case descriptions on all algorithm cards

Code Quality

• Dead code cleanup: removed _find_component from prim.py
• 58 new unit tests (339 total, all passing)

Breaking Barrier SSSP Performance (sparse graphs, m ≈ 2n):
n=500: 99x → 75x vs Dijkstra (~24% faster)
n=1000: 129x → 26x vs Dijkstra (~5x faster)
n=2000: 162x → 21x vs Dijkstra (~7x faster)

v0.5.0 — Breaking the Sorting Barrier SSSP

What's New

First Python implementation of the Breaking the Sorting Barrier SSSP algorithm
(Duan, Mao, Mao, Shu, Yin — STOC 2025 Best Paper, arXiv:2504.17033v2).

Added

• lg.breaking_barrier_sssp(G, source) — O(m log²/³ n) deterministic SSSP for directed graphs
• BlockHeap — Lemma 3.3 block-based data structure
• Constant-degree graph transform (Frederickson 1983)
• plot_breaking_barrier_result() visualization
• Benchmark script: tests/benchmarks/benchmark_breaking_barrier.py

Stats

• 281 unit tests passing
• Verified against Dijkstra on 100+ random graphs

v0.4.0 — MST, Network Flow & Graph Properties

What's New in v0.4.0

This release adds three major algorithm categories and completes the graph analysis foundation.

New Algorithms

Minimum Spanning Tree (lg.kruskal_mst, lg.prim_mst)

• Kruskal's MST — Union-Find with path compression + union by rank, O(E log E)
• Prim's MST — min-heap implementation, O(E + V log V)
• Both return spanning forest for disconnected graphs

Network Flow (lg.max_flow)

• Edmonds-Karp algorithm (BFS-based Ford-Fulkerson), O(V·E²)
• Returns flow_value, flow_dict, and residual graph
• Directed and undirected graph support

Graph Properties (lg.tarjan_scc, lg.topological_sort)

• Tarjan's SCC — iterative implementation, O(V+E)
• Topological Sort — DFS (post-order) and Kahn (BFS/in-degree) methods, O(V+E)

New Exceptions

• NotDAGError — raised by topological_sort on cyclic graphs; carries .cycle attribute
• UndirectedGraphRequiredError — raised when a directed graph is passed to MST algorithms

Visualization (7 new functions, 23 total)

• plot_mst, plot_mst_comparison, plot_kruskal_steps
• plot_flow_network, plot_flow_paths
• plot_scc (with optional condensation DAG), plot_topological_order

Tests

• +70 unit tests → 182 total

---

Full Changelog: CHANGELOG.md

v0.3.3 — Algorithm-Specific Visualization & DFS Tree & Error Handling

What's New in v0.3.3

This release adds algorithm-specific visualization functions that expose the
internal behaviour of each shortest-path and traversal algorithm — beyond
generic graph drawing.

---

New: Shortest-Path Visualizations

Five new functions in logarithma.visualization:

Function	What it shows
plot_astar_search	Expanded nodes (closed set), open set, optional heuristic value labels per node
plot_bellman_ford_result	Negative edges in dashed red, distance labels on nodes, path highlighting
plot_negative_cycle	Cycle nodes/edges in bold red, total cycle weight in title
plot_bidirectional_search	Forward (blue) / backward (green) frontiers, meeting point (yellow), overlap (purple)
plot_shortest_path_comparison	Dijkstra, A*, and Bidirectional Dijkstra side-by-side in one figure

from logarithma.visualization import (
    plot_astar_search,
    plot_bellman_ford_result,
    plot_negative_cycle,
    plot_bidirectional_search,
    plot_shortest_path_comparison,
)

# Compare all three algorithms at once
plot_shortest_path_comparison(G, source=0, target=33)

# Visualize A* search space
from logarithma.algorithms.shortest_path.astar import manhattan_heuristic
plot_astar_search(G, source=(0,0), target=(4,4),
                  heuristic=manhattan_heuristic(pos), show_heuristic=True)

v0.3.2 — A*, Bellman-Ford, Bidirectional Dijkstra

What's New in v0.3.2

New Algorithms

A* (A-Star) — Heuristic-guided shortest path

• astar(graph, source, target, heuristic=None)
• astar_with_stats(...) — node expansion diagnostics
• Built-in heuristics: euclidean_heuristic, manhattan_heuristic, haversine_heuristic
• Optimal when heuristic is admissible; degenerates to Dijkstra with zero_heuristic

Bellman-Ford — Negative-weight edge support

• bellman_ford(graph, source) — returns distances + predecessors
• bellman_ford_path(graph, source, target) — path reconstruction
• NegativeCycleError raised with reconstructed cycle when detected
• Note: undirected graphs with negative edges always produce a negative cycle (2-cycle)

Bidirectional Dijkstra — Fast point-to-point queries

• bidirectional_dijkstra(graph, source, target)
• Simultaneous forward/backward search (Pohl 1971)
• ~2× fewer node expansions vs standard Dijkstra
• Backward search follows reversed edges on directed graphs

Bug Fix

• dijkstra_with_path: unreachable nodes now return [] in paths dict instead of being omitted

Installation

pip install --upgrade logarithma

v0.3.1 — A*, Bellman-Ford, Bidirectional Dijkstra

What's New in v0.3.1

New Algorithms

A* (A-Star) — Heuristic-guided shortest path

• astar(graph, source, target, heuristic=None)
• astar_with_stats(...) — node expansion diagnostics
• Built-in heuristics: euclidean_heuristic, manhattan_heuristic, haversine_heuristic
• Optimal when heuristic is admissible; degenerates to Dijkstra with zero_heuristic

Bellman-Ford — Negative-weight edge support

• bellman_ford(graph, source) — returns distances + predecessors
• bellman_ford_path(graph, source, target) — path reconstruction
• NegativeCycleError raised with reconstructed cycle when detected
• Note: undirected graphs with negative edges always produce a negative cycle (2-cycle)

Bidirectional Dijkstra — Fast point-to-point queries

• bidirectional_dijkstra(graph, source, target)
• Simultaneous forward/backward search (Pohl 1971)
• ~2× fewer node expansions vs standard Dijkstra
• Backward search follows reversed edges on directed graphs

Bug Fix

• dijkstra_with_path: unreachable nodes now return [] in paths dict instead of being omitted

Installation

pip install --upgrade logarithma

v0.3.0 — A*, Bellman-Ford, Bidirectional Dijkstra

What's New in v0.3.0

New Algorithms

A* (A-Star) — Heuristic-guided shortest path

• astar(graph, source, target, heuristic=None)
• astar_with_stats(...) — node expansion diagnostics
• Built-in heuristics: euclidean_heuristic, manhattan_heuristic, haversine_heuristic
• Optimal when heuristic is admissible; degenerates to Dijkstra with zero_heuristic

Bellman-Ford — Negative-weight edge support

• bellman_ford(graph, source) — returns distances + predecessors
• bellman_ford_path(graph, source, target) — path reconstruction
• NegativeCycleError raised with reconstructed cycle when detected
• Note: undirected graphs with negative edges always produce a negative cycle (2-cycle)

Bidirectional Dijkstra — Fast point-to-point queries

• bidirectional_dijkstra(graph, source, target)
• Simultaneous forward/backward search (Pohl 1971)
• ~2× fewer node expansions vs standard Dijkstra
• Backward search follows reversed edges on directed graphs

Bug Fix

• dijkstra_with_path: unreachable nodes now return [] in paths dict instead of being omitted

Installation

pip install --upgrade logarithma

v0.2.0 - Major Feature Update

🚀 logarithma v0.2.0 Release Notes

We're excited to announce the release of logarithma v0.2.0! This major update brings significant enhancements to the library with new algorithms, comprehensive utilities, and improved code quality.

🎯 What's New

📊 Graph Traversal Algorithms

• BFS (Breadth-First Search): Complete implementation with path finding capabilities
• DFS (Depth-First Search): Both recursive and iterative versions
• Cycle Detection: Detect cycles in directed and undirected graphs

🛠️ Comprehensive Utils Module

The new utils module provides 34 essential functions across 4 categories:

1. Graph Generators (9 functions)

   • Create random graphs, grids, complete graphs, trees, and more
   • Perfect for testing and experimentation

2. Validators (8 functions)

   • Check connectivity, DAG properties, negative weights
   • Validate graph properties before running algorithms

3. Converters (8 functions)

   • Convert between adjacency matrices, edge lists, and NetworkX graphs
   • Seamless integration with other graph libraries

4. Metrics (9 functions)

   • Calculate density, degree statistics, diameter, clustering coefficients
   • Comprehensive graph analysis tools

⚡ Enhanced Dijkstra Algorithm

• Added support for directed graphs (nx.DiGraph)
• Negative weight validation with clear error messages
• Improved documentation and examples
• Better error handling for edge cases

📚 Documentation & Examples

• New example scripts demonstrating all features
• Benchmark framework for performance testing
• Comprehensive API documentation

💻 Installation

pip install --upgrade logarithma

🔧 Quick Start

import logarithma as lg
from logarithma.utils import generate_random_graph, graph_summary

# Create a random graph
G = generate_random_graph(100, 0.1, weighted=True)

# Analyze the graph
summary = graph_summary(G)
print(f"Nodes: {summary['nodes']}, Edges: {summary['edges']}")
print(f"Density: {summary['density']:.4f}")

# Find shortest paths
distances = lg.dijkstra(G, source=0)

# Perform graph traversal
visited = lg.bfs(G, source=0)
path = lg.dfs_path(G, source=0, target=50)

# Detect cycles
has_cycle = lg.detect_cycle(G)

📈 Performance

All algorithms are optimized for performance with comprehensive test coverage. The new benchmark framework allows you to measure performance on your specific use cases.

🔮 What's Next (v0.3.0+)

• Visualization module with Matplotlib and Plotly support
• Additional algorithms: A*, Bellman-Ford, Floyd-Warshall
• Performance optimizations with Cython/Numba
• Advanced shortest path algorithm from "Breaking the Sorting Barrier" (2025)

🙏 Acknowledgments

Thank you to all users who provided feedback on v0.1.0. Your input has been invaluable in shaping this release.

📝 Full Changelog

See CHANGELOG.md for complete details.

---

GitHub: https://github.com/softdevcan/logarithma
PyPI: https://pypi.org/project/logarithma/
Issues: https://github.com/softdevcan/logarithma/issues