Skip to content

AlgoGraph v1.3.0 - Core Algorithms

Choose a tag to compare

View all tags
@queelius queelius released this 15 Nov 12:49
· 11 commits to main since this release
v1.3.0
c3e2c4a

AlgoGraph v1.3.0 - Core Algorithms Release

Phase 2 complete! Massive expansion adding 24 new algorithms across 4 critical categories.

🎯 New Algorithm Categories

Centrality Algorithms (5)

Measure vertex importance in networks:

  • PageRank - Google's page ranking algorithm with damping factor
  • Betweenness Centrality - Identify bridge vertices (Brandes' O(V*E) algorithm)
  • Closeness Centrality - Average distance to all vertices
  • Degree Centrality - Simple degree-based importance
  • Eigenvector Centrality - Importance based on connections to important vertices
from AlgoGraph import Graph
from AlgoGraph.algorithms import pagerank, betweenness_centrality

# Analyze social network
social = Graph.builder().add_star('Alice', 'Bob', 'Carol', 'Dave').build()
pr = pagerank(social)
bc = betweenness_centrality(social)
print(f"Top influencer: {max(pr, key=pr.get)}")

Flow Network Algorithms (5)

Solve maximum flow and minimum cut problems:

  • Edmonds-Karp - Maximum flow using BFS (O(V*E²))
  • Max Flow - Convenience wrapper for maximum flow value
  • Min Cut - Minimum cut using max-flow/min-cut theorem
  • Ford-Fulkerson - Generic max flow framework
  • Capacity Scaling - Improved Ford-Fulkerson variant
from AlgoGraph.algorithms import max_flow, min_cut

# Network capacity planning
network = (Graph.builder()
           .add_edge('Source', 'A', weight=100)
           .add_edge('A', 'Sink', weight=80)
           .build())
           
flow = max_flow(network, 'Source', 'Sink')
cut_value, source_set, sink_set = min_cut(network, 'Source', 'Sink')
print(f"Maximum throughput: {flow}")

Matching Algorithms (6)

Find optimal pairings and assignments:

  • Hopcroft-Karp - Maximum bipartite matching (O(E*sqrt(V)))
  • Maximum Bipartite Matching - Returns matching as edge set
  • Is Perfect Matching - Check if all vertices can be matched
  • Maximum Matching - For general graphs
  • Matching Size - Get cardinality of matching
  • Is Maximal Matching - Verify matching cannot be extended
from AlgoGraph.algorithms import hopcroft_karp, is_perfect_matching

# Job assignment
jobs = Graph.builder().add_bipartite(
    ['Alice', 'Bob'], 
    ['Backend', 'Frontend'], 
    complete=True
).build()

matching = hopcroft_karp(jobs, {'Alice', 'Bob'}, {'Backend', 'Frontend'})
for worker, job in matching.items():
    print(f"{worker} → {job}")

Graph Coloring Algorithms (8)

Solve scheduling and constraint satisfaction:

  • Greedy Coloring - Simple greedy vertex coloring
  • Welsh-Powell - Greedy with degree ordering (often better)
  • DSatur - Degree of saturation (superior average performance)
  • Chromatic Number - Estimate minimum colors needed
  • Is Valid Coloring - Verify coloring correctness
  • Edge Coloring - Color edges (no adjacent edges same color)
  • Chromatic Index - Edge chromatic number
  • Is K-Colorable - Check if colorable with k colors
from AlgoGraph.algorithms import welsh_powell, chromatic_number

# Exam scheduling
conflicts = (Graph.builder()
             .add_edge('Math', 'Physics', directed=False)
             .add_edge('Physics', 'Chemistry', directed=False)
             .build())

coloring = welsh_powell(conflicts)
num_slots = chromatic_number(conflicts)
print(f"Need {num_slots} time slots")

📊 Growth Metrics

Metric v1.2.0 v1.3.0 Change
Total Algorithms 32 56 +75% 🚀
NetworkX Parity 40% 65% +25 pts
Test Count 98 143 +45 tests
Algorithm Categories 4 8 +4 new

🔬 Research-Based Implementations

All algorithms based on peer-reviewed research:

  • Brandes (2001): Betweenness centrality O(V*E)
  • Page et al. (1999): PageRank algorithm
  • Edmonds & Karp (1972): Maximum flow O(V*E²)
  • Hopcroft & Karp (1973): Bipartite matching O(E*sqrt(V))
  • Brélaz (1979): DSatur coloring algorithm
  • Welsh & Powell (1967): Degree-ordered coloring

💼 Real-World Use Cases

Social Network Analysis

# Find influencers and bridge people
pr = pagerank(social_network)
bc = betweenness_centrality(social_network)
top_influencer = max(pr, key=pr.get)
top_broker = max(bc, key=bc.get)

Network Optimization

# Maximum throughput and bottlenecks
flow = max_flow(transport_network, 'Factory', 'Store')
cut_value, source, sink = min_cut(transport_network, 'Factory', 'Store')

Assignment Problems

# Optimal job assignments
matching = hopcroft_karp(assignments, workers, jobs)
if is_perfect_matching(assignments, workers, jobs):
    print("Everyone assigned!")

Exam Scheduling

# Minimize time slots for exams
coloring = welsh_powell(exam_conflicts)
num_slots = chromatic_number(exam_conflicts)

✅ Quality Assurance

  • ✅ 100% test coverage for all new algorithms
  • ✅ 45 new comprehensive tests (143 total)
  • ✅ Edge case handling (empty, single vertex, disconnected)
  • ✅ Full docstrings with examples and complexity analysis
  • ✅ 100% backward compatibility - no breaking changes
  • ✅ 0 regressions - all existing tests pass

📦 What's Included

New Files:

  • algorithms/centrality.py (380 lines, 5 algorithms)
  • algorithms/flow.py (340 lines, 5 algorithms)
  • algorithms/matching.py (320 lines, 6 algorithms)
  • algorithms/coloring.py (370 lines, 8 algorithms)
  • test/test_phase2_algorithms.py (490 lines, 45 tests)
  • PHASE2_SUMMARY.md (comprehensive documentation)

Total: ~1,900 lines of new, tested, documented code

Updated Files:

  • algorithms/__init__.py - Exports 24 new functions
  • __init__.py - Version → 1.3.0

🚀 Installation

pip install AlgoGraph  # Coming soon to PyPI

Or from source:

git clone https://github.com/queelius/AlgoGraph.git
cd AlgoGraph
pip install -e .

📚 Documentation

  • Full Documentation: https://queelius.github.io/AlgoGraph/
  • Phase 2 Summary: See PHASE2_SUMMARY.md for detailed examples and analysis
  • API Reference: Each algorithm has comprehensive docstrings with examples

🔜 What's Next

Phase 3: Advanced Features (coming soon)

  • Transformer pattern with pipe composition
  • Selector pattern for complex queries
  • Generic types for type safety
  • Graph views for lazy evaluation

See ARCHITECTURAL_REVIEW.md for complete roadmap.

🙏 Acknowledgments

Built with research-based algorithms from computer science literature. See individual algorithm docstrings for citations and references.

Full Changelog: v1.2.0...v1.3.0

Assets 2
Loading