Zog Roadmap

View Source

Roadmap and release planning for Zog's native Elixir/Zig graph algorithms.

Current Status (v0.2.0-dev)

Zog v0.2.0 implements high-performance native implementations of core graph algorithms including Pathfinding (Dijkstra, A*, Bellman-Ford, Floyd-Warshall, Johnson's), Flow (Edmonds-Karp, Push-Relabel, Stoer-Wagner), MST (Kruskal's), Connectivity (Tarjan's SCC, Bridges, Articulation, K-core), Centrality (PageRank, Betweenness, Closeness, Katz, Eigenvector), and Community Detection (Louvain, Leiden, Label Propagation).

Release Milestones

📅 v0.3.0: Matching & Graph Manipulation

Focuses on bipartite/general matchings and subgraph extraction.

  • Matching Algorithms
    • [ ] Hopcroft-Karp (Maximum Bipartite Matching)
    • [ ] Hungarian Algorithm (Weighted Bipartite Matching)
    • [ ] Blossom Algorithm (Maximum Matching in General Graphs)
  • Graph Properties
    • [ ] Bipartite Check (2-colorability verification)
    • [ ] Bipartite Partition (Color assignment)
    • [ ] Maximum Bipartite Matching
  • Transformations
    • [ ] Subgraph extraction (Induced subgraphs by node IDs)

📅 v0.4.0: DAG Analysis & Network Health

Focuses on Directed Acyclic Graph (DAG) sorting/checks and structural health metrics.

  • DAG & Traversals
    • [ ] Topological Sort (DFS-based)
    • [ ] Kahn's Algorithm (Topological sort with queue)
    • [ ] Acyclicity Test (Cycle detection)
  • Network Health Metrics
    • [ ] Diameter (Longest shortest path)
    • [ ] Radius (Minimum eccentricity)
    • [ ] Eccentricity (Max distance from a node)
    • [ ] Average Path Length (APL)

📅 v0.5.0: Multigraph Support

Focuses on parallel edges, edge keys, and edge-aware traversals.

  • Multigraph Core
    • [ ] Multi-edge storage (extending SoA and NIF boundary for edge key mappings)
    • [ ] Edge-specific deletion (removing a specific parallel edge by ID)
    • [ ] Collapse multigraph to simple graph (to_simple_graph)
  • Multigraph Traversals & Eulerian Paths
    • [ ] Eulerian Circuit / Path (Hierholzer with edge IDs)
    • [ ] Edge-ID aware BFS / DFS / Fold Walk
    • [ ] Multigraph Cycle Check & Topological Sort

📋 Future Backlog (Deferred & On-Demand)

These features are not scheduled for immediate releases and will be implemented based on community demand or specific needs.

  • Pathfinding: Bidirectional Dijkstra, Bidirectional BFS, Yen's K-Shortest, Widest Path, All-Pairs Unweighted.
  • Network Flow: Successive Shortest Path (Min-cost max-flow).
  • Spanning Tree: Minimum Spanning Arborescence (Edmonds' Directed MST).
  • Connectivity: Weakly Connected Components, Reachability Exact.
  • Centrality & Metrics: HITS (Hubs and Authorities), Transitivity.
  • Community Detection: Walktrap, Infomap, Clique Percolation, Fluid Communities, Local Community.
  • Transformations & Operations: Ego Graph, Transitive Closure/Reduction, Contract, node/edge filter predicates.
  • Graph Properties: Complete Graph detection, Tree/Forest/Branching checks, Isomorphism, Graph Hash.
  • Generators: GNM random generator, Stochastic Block Models (SBM, DCSBM, HSBM), Random Regular, Geometric/Waxman generators.