Default
Default
In-browser search
Settings
This document maps all algorithms implemented in YogEx and shows their implementation status in Zog , including native performance notes and future roadmap details.
1. Pathfinding 2. Flow & Cuts Algorithm YogEx Module Purpose Zog Status Notes / Details Edmonds-Karp Yog.Flow.MaxFlowMaximum flow (BFS augmenting paths) ✅ Implemented Native Zig via Zog.Flow.max_flow/4 Dinic's Yog.Flow.MaxFlowMaximum flow (blocking flow) ❌ Missing Deliberately Omitted — Zog implements Push-Relabel instead, which is generally faster.Push-Relabel N/A (Zog exclusive) High-performance max flow (preflow-push) ✅ Implemented Native Zig via Zog.Flow.max_flow/4[algorithm: :push_relabel]. Successive Shortest Path Yog.Flow.SuccessiveShortestPathMin-cost max-flow ❌ Missing WIP/Roadmap — planned for future network flow releases.Stoer-Wagner Yog.Flow.MinCutGlobal minimum cut ✅ Implemented Native Zig via Zog.Flow.global_min_cut/1
3. Spanning Tree Algorithm YogEx Module Purpose Zog Status Notes / Details Kruskal's Yog.MSTMST via edge sorting ✅ Implemented Native Zig via Zog.MST.kruskal/1 Prim's Yog.MSTMST via vertex growing ❌ Missing Deliberately Omitted — Kruskal's is sufficient for MST; Prim's offers no major advantage here.Borůvka's Yog.MSTParallel MST ❌ Missing Won't Have — Kruskal's is sufficient.Edmonds' Yog.MSTMinimum Spanning Arborescence (Directed) ❌ Missing Deferred — low priority.Wilson's Yog.MSTUniform Spanning Tree (Probabilistic) ❌ Missing Won't Have — outside project scope.Max Spanning Tree Yog.MSTMaximum weight tree ❌ Missing Deferred — can be achieved by negating weights and using Kruskal's.
4. Matching Algorithm YogEx Module Purpose Zog Status Notes / Details Hopcroft-Karp Yog.MatchingMaximum bipartite matching ❌ Missing WIP/Roadmap — matching algorithms are planned for v0.3.0.Hungarian Yog.MatchingWeighted bipartite matching ❌ Missing WIP/Roadmap — planned for v0.3.0.Blossom Yog.MatchingMaximum matching in general graphs ❌ Missing WIP/Roadmap — planned for v0.3.0.
5. Connectivity & Components 6. Centrality Measures 9. Traversal & Search Algorithm YogEx Module Purpose Zog Status Notes / Details BFS Yog.TraversalBreadth-first exploration ❌ Missing Deliberately Omitted — BFS traversal is done internally in Zig; not exposed as a public API.DFS Yog.TraversalDepth-first exploration ❌ Missing Deliberately Omitted — DFS traversal is done internally in Zig; not exposed as a public API.Topological Sort Yog.TraversalDAG vertex ordering ❌ Missing WIP/Roadmap — planned for a future DAG-focused release.Find Path Yog.TraversalAny path between nodes ❌ Missing Deliberately Omitted — shortest path algorithms (Dijkstra/BFS) handle path finding.Implicit Search Yog.Traversal.ImplicitOn-demand graph traversal ❌ Missing Won't Have — FGL/lazy evaluation concepts do not fit Zog's memory model.Kahn's Algorithm Yog.Traversal.SortTopological sort (BFS-based) ❌ Missing WIP/Roadmap — planned for a future DAG release.Lexicographical TopSort Yog.Traversal.SortDeterministic topological ordering ❌ Missing Won't Have — low priority.Best-First Walk Yog.Traversal.WalkPriority-guided traversal ❌ Missing Won't Have — low priority.Random Walk Yog.Traversal.WalkStochastic path exploration ❌ Missing Deferred — low priority.BFS Path Yog.Traversal.WalkBFS shortest path between nodes ❌ Missing Deliberately Omitted — Dijkstra handles shortest paths.
Algorithm YogEx Module Purpose Zog Status Notes / Details Transpose Yog.TransformReverse edge directions ❌ Missing Deliberately Omitted — transpose logic is handled at graph build time.Subgraph Yog.TransformInduced subgraph by node IDs ❌ Missing WIP/Roadmap — planned for v0.3.0.Ego Graph Yog.Transformk-hop neighborhood subgraph ❌ Missing Deferred — low priority.Transitive Closure Yog.TransformReachability matrix ❌ Missing Deferred — high memory footprint, low priority.Transitive Reduction Yog.TransformMinimal equivalent DAG ❌ Missing Deferred — low priority.Quotient Graph Yog.TransformPartition-based contraction ❌ Missing Won't Have — low priority.Contract Yog.TransformMerge two nodes ❌ Missing Deferred — low priority.Filter Nodes Yog.TransformPredicate-based subgraph ❌ Missing Deferred — low priority.Filter Edges Yog.TransformPredicate-based edge removal ❌ Missing Deferred — low priority.
11. Graph Properties 12. DAG Algorithms Note: Dedicated DAG optimizations are planned for future releases. Standard graph pathfinding handles basic cases for now.
Algorithm YogEx Module Purpose Zog Status Notes / Details Longest Path Yog.DAG.AlgorithmCritical path in weighted DAG ❌ Missing Deferred — low priority.Shortest Path Yog.DAG.AlgorithmShortest path in DAG ❌ Missing Deliberately Omitted — standard pathfinding handles this.Transitive Closure Yog.TransformReachability matrix ❌ Missing Deferred — low priority.Transitive Reduction Yog.TransformMinimal equivalent DAG ❌ Missing Deferred — low priority.LCA Yog.Pathfinding.LCALowest common ancestors ❌ Missing Deferred — low priority.Topological Generations Yog.DAGLayer-by-layer ordering ❌ Missing Deferred — low priority.Sources Yog.DAGIn-degree 0 nodes ❌ Missing Deferred — low priority.Sinks Yog.DAGOut-degree 0 nodes ❌ Missing Deferred — low priority.Ancestors Yog.DAGAll ancestors of a node ❌ Missing Deferred — low priority.Descendants Yog.DAGAll descendants of a node ❌ Missing Deferred — low priority.Single-Source Distances Yog.DAGSSSP in DAG ❌ Missing Deliberately Omitted — standard pathfinding handles this.Path Count Yog.DAGNumber of distinct paths ❌ Missing Deferred — low priority.
13. Graph Operations Note: Standard graph operations are generally left to Elixir to process or build via SoA structures rather than native Zig conversions.
Algorithm / Op YogEx Module Purpose Zog Status Notes / Details Union Yog.OperationGraph union ❌ Missing Deliberately Omitted — easily done in Elixir during SoA compilation.Intersection Yog.OperationGraph intersection ❌ Missing Deliberately Omitted — easily done in Elixir.Difference Yog.OperationGraph difference ❌ Missing Deliberately Omitted — easily done in Elixir.Symmetric Difference Yog.OperationXOR of graphs ❌ Missing Deliberately Omitted — easily done in Elixir.Cartesian Product Yog.OperationGraph product ❌ Missing Deferred — low priority.Power Graph Yog.Operationk-th power ❌ Missing Deferred — low priority.Line Graph Yog.OperationEdge-to-vertex dual ❌ Missing Deferred — low priority.Transpose Yog.OperationReverse all edges ❌ Missing Deliberately Omitted — easily done in Elixir/SoA.Isomorphism Yog.OperationGraph equality ❌ Missing Deferred — low priority.Subgraph Yog.OperationInduced subgraph ❌ Missing WIP/Roadmap — planned for v0.3.0.Subgraph Check Yog.OperationSubgraph relationship ❌ Missing Deferred — low priority.Graph Composition Yog.OperationRelational graph composition ❌ Missing Won't Have — outside project scope.Graph Complement Yog.OperationInverse edge set ❌ Missing Deferred — low priority.Disjoint Union Yog.OperationUnion with re-indexing ❌ Missing Deliberately Omitted — easily done in Elixir.Map Nodes Yog.OperationTransform node data ❌ Missing Deliberately Omitted — nodes are arbitrarily labeled in Elixir.Map Edges Yog.OperationTransform edge weights ❌ Missing Deliberately Omitted — easily mapped in Elixir.Filter Nodes Yog.OperationFilter-based node removal ❌ Missing Deferred — low priority.Filter Edges Yog.OperationFilter-based edge removal ❌ Missing Deferred — low priority.Relabel Nodes Yog.OperationRename node IDs ❌ Missing Deliberately Omitted — labels are managed in Elixir.
14. Multigraph Note: Zog currently only supports simple directed or undirected graphs. Multigraphs are planned for the v0.5.0 release.
Algorithm YogEx Module Purpose Zog Status Notes / Details Eulerian Circuit Yog.Multi.EulerianHierholzer with edge IDs ❌ Missing WIP/Roadmap — planned for v0.5.0.Eulerian Path Yog.Multi.EulerianOpen Eulerian walk ❌ Missing WIP/Roadmap — planned for v0.5.0.BFS Yog.Multi.TraversalEdge-ID aware BFS ❌ Missing WIP/Roadmap — planned for v0.5.0.DFS Yog.Multi.TraversalEdge-ID aware DFS ❌ Missing WIP/Roadmap — planned for v0.5.0.Fold Walk Yog.Multi.TraversalStateful traversal ❌ Missing WIP/Roadmap — planned for v0.5.0.Cycle Check Yog.MultiMultigraph cycle detection ❌ Missing WIP/Roadmap — planned for v0.5.0.Topological Sort Yog.MultiMultigraph topological ordering ❌ Missing WIP/Roadmap — planned for v0.5.0.To Simple Graph Yog.MultiCollapse parallel edges ❌ Missing WIP/Roadmap — planned for v0.5.0.
15. Health Metrics Algorithm YogEx Module Purpose Zog Status Notes / Details Diameter Yog.HealthLongest shortest path ❌ Missing WIP/Roadmap — planned for a future metrics update.Radius Yog.HealthMinimum eccentricity ❌ Missing WIP/Roadmap — planned for a future metrics update.Eccentricity Yog.HealthMax distance from node ❌ Missing WIP/Roadmap — planned for a future metrics update.Assortativity Yog.HealthDegree correlation ✅ Implemented Native Zig via Zog.Metrics.assortativity/1 APL Yog.HealthAverage path length ❌ Missing WIP/Roadmap — planned for a future metrics update.Global Efficiency Yog.HealthInverse mean distance ❌ Missing Deferred — low priority.Local Efficiency Yog.HealthNeighborhood efficiency ❌ Missing Deferred — low priority.
16. Random Graph Generation 17. Classic Graph Generators Generator YogEx Module Purpose Zog Status Notes / Details Grid 2D Yog.Generator.ClassicRectangular lattice ✅ Implemented Natively generated via Zog.Generator.grid_2d/3 Others (Complete, Cycle, Path, Star, Wheel, Peterson, Crown, Hypercube, Platonic, Friendship, Book, Turán, platonic solids) Yog.Generator.ClassicClassic topology generation ❌ Missing Deferred — low priority; grid_2d is the most commonly used. Complete/Cycle/Path are easily constructed via Elixir.
18. Graph Builders Builder YogEx Module Purpose Zog Status Notes / Details Grid / Toroidal Yog.BuilderLattice construction ❌ Missing Deliberately Omitted — unneeded, handled via grid_2d generators.Labeled / Live Builders Yog.BuilderIncremental building ❌ Missing Omitted — Zog utilizes the SoA struct for builder patterns.
19. Functional Graphs (FGL-style) Feature YogEx Module Purpose Zog Status Notes / Details Inductive Decomposition / Context Embedding / Algorithms Yog.FunctionalInductive functional graph operations ❌ Missing Deliberately Omitted — Zog is built on mutable ArrayGraph/GraphMap representations in native Zig for speed, which are fundamentally incompatible with FGL-style inductive models.
20. Rendering Format YogEx Module Purpose Zog Status Notes / Details ASCII Render Yog.Render.ASCIITerminal visualization ❌ Missing Deferred — client-side rendering is preferred.DOT Export Yog.Render.DOTGraphviz DOT format ❌ Missing Deferred — easily implemented in Elixir; low priority.Mermaid Export Yog.Render.MermaidMermaid.js diagram format ❌ Missing Deferred — easily implemented in Elixir; low priority.
21. Data Structures Structure YogEx Module Purpose Zog Status Notes / Details Pairing Heap Yog.PairingHeapPriority queue ❌ Missing Deliberately Omitted — Zig's standard std.PriorityQueue is used natively; no need to expose an Elixir heap module.Disjoint Set Yog.DisjointSetUnion-Find ❌ Missing Deliberately Omitted — handled internally in native code.HyperLogLog Yog.ConnectivityCardinality estimation ❌ Missing Won't Have — unneeded.
22. Maze Generation Algorithm YogEx Module Purpose Zog Status Notes / Details Maze generation (Binary Tree, Sidewinder, backtracker, Hunt-and-Kill, Aldous-Broder, Eller's, division, Kruskal/Prim) Yog.Generator.MazeGraph-based mazes ❌ Missing Won't Have — deliberately out of scope for Zog's core graph library.
23. Approximation Algorithms Algorithm YogEx Module Purpose Zog Status Notes / Details Approximation (Diameter, Betweenness, Avg Path, Efficiency, Transitivity, Clique, Cover) Yog.ApproximateApproximate scaling algorithms ❌ Missing Deferred — Zog runs exact algorithms natively. Approximation might be added in future scalability updates.
24. I/O & Serialization Format YogEx Module Purpose Zog Status Notes / Details Edgelist Yog.IOSpace-separated edges ✅ Implemented Supported via Zog.IO.load/2Zog.IO.dump/3 CSV Yog.IOComma-separated edges ✅ Implemented Supported via Zog.IO.load/2Zog.IO.dump/3 Pajek Yog.IO.net format✅ Implemented Supported via Zog.IO.dump/3 TGF Yog.IOTrivial Graph Format ✅ Implemented Supported via Zog.IO.load/2Zog.IO.dump/3 Adjlist Yog.IOAdjacency list format ✅ Implemented Supported via Zog.IO.load/2Zog.IO.dump/3 Lesser-used (GDF, GEXF, GraphML, Graph6, Sparse6, JSON, LEDA, Matrix Market, Libgraph) Yog.IOVarious serialization formats ❌ Missing Deferred — only the most common standard formats are implemented in Zog.