A graph algorithm library for Gleam, providing implementations of classic graph algorithms with a functional API.
In many Indic languages, Yog (pronounced like "yoke") translates to "Union," "Addition," or "Connection." It stems from the ancient root yuj, meaning to join or to fasten together.
In the world of computer science, this is the literal definition of Graph Theory. A graph is nothing more than the union of independent points through purposeful connections.
- Graph Data Structures: Directed and undirected graphs with generic node and edge data
- Pathfinding Algorithms: Dijkstra, A*, Bellman-Ford, Floyd-Warshall, and Implicit Variants (state-space search)
- Maximum Flow: Highly optimized Edmonds-Karp algorithm with flat dictionary residuals
- Graph Generators: Create classic patterns (complete, cycle, path, star, wheel, bipartite, trees, grids) and random graphs (Erdős-Rényi, Barabási-Albert, Watts-Strogatz)
- Graph Traversal: BFS and DFS with early termination and Implicit Variants
- Graph Transformations: Transpose (O(1)!), map, filter, merge, subgraph extraction, edge contraction
- Graph Visualization: Mermaid, DOT (Graphviz), and JSON rendering
- Minimum Spanning Tree: Kruskal's and Prim's algorithms with Union-Find and Priority Queues
- Minimum Cut: Stoer-Wagner algorithm for global min-cut
- Directed Acyclic Graphs (DAG): Strictly-validated
Dag(n, e)wrapper bringing O(V+E) DP routines likelongest_path(Critical Path), LCA, and transitive structures - Topological Sorting: Kahn's algorithm with lexicographical variant, alongside guaranteed cycle-free DAG-specific sorts
- Strongly Connected Components: Tarjan's and Kosaraju's algorithms
- Maximum Clique: Bron-Kerbosch algorithm for maximal and all maximal cliques
- Connectivity: Bridge and articulation point detection
- Eulerian Paths & Circuits: Detection and finding using Hierholzer's algorithm
- Bipartite Graphs: Detection, maximum matching, and stable marriage (Gale-Shapley)
- Minimum Cost Flow (MCF): Global optimization using the robust Network Simplex algorithm
- Disjoint Set (Union-Find): With path compression and union by rank
- Efficient Data Structures: Pairing heap for priority queues, two-list queue for BFS
Add Yog to your Gleam project:
gleam add yogimport gleam/int
import gleam/io
import gleam/option.{None, Some}
import yog
import yog/pathfinding/dijkstra
pub fn main() {
// Create a directed graph
let graph =
yog.directed()
|> yog.add_node(1, "Start")
|> yog.add_node(2, "Middle")
|> yog.add_node(3, "End")
|> yog.add_edge(from: 1, to: 2, with: 5)
|> yog.add_edge(from: 2, to: 3, with: 3)
|> yog.add_edge(from: 1, to: 3, with: 10)
// Find shortest path
case dijkstra.shortest_path(
in: graph,
from: 1,
to: 3,
with_zero: 0,
with_add: int.add,
with_compare: int.compare
) {
Some(path) -> {
io.println("Found path with weight: " <> int.to_string(path.total_weight))
}
None -> io.println("No path found")
}
}We have some real-world projects that use Yog for graph algorithms:
- Lustre Graph Generator (Demo) - Showcases graph generation, topological sort and shortest distance feature of Yog.
- Advent of Code Solutions - Multiple AoC puzzles solved using Yog's graph capabilities.
Detailed examples are located in the examples/ directory:
- Social Network Analysis - Finding communities using SCCs.
- Task Scheduling - Basic topological sorting.
- GPS Navigation - Shortest path using A* and heuristics.
- Network Cable Layout - Minimum Spanning Tree using Kruskal's.
- Network Bandwidth - ⭐ Max flow for bandwidth optimization with bottleneck analysis.
- Job Matching - ⭐ Max flow for bipartite matching and assignment problems.
- Cave Path Counting - Custom DFS with backtracking.
- Task Ordering - Lexicographical topological sort.
- Bridges of Königsberg - Eulerian circuit and path detection.
- Global Minimum Cut - Stoer-Wagner algorithm.
- Job Assignment - Bipartite maximum matching.
- Medical Residency - Stable marriage matching (Gale-Shapley algorithm).
- City Distance Matrix - Floyd-Warshall for all-pairs shortest paths.
- Graph Generation Showcase - ⭐ All 9 classic graph patterns with statistics.
- DOT rendering - Exporting graphs to Graphviz format.
- Mermaid rendering - Generating Mermaid diagrams.
- JSON rendering - Exporting graphs to JSON for web use.
- Graph creation - Comprehensive guide to 10+ ways of creating graphs.
The examples live in the examples/ directory. To run them with gleam run, create a one-time symlink that makes Gleam's module system aware of them:
ln -sf "$(pwd)/examples" src/yog/internal/examplesThen run any example by its module name:
gleam run -m yog/internal/examples/gps_navigation
gleam run -m yog/internal/examples/network_bandwidth
# etc.The symlink is listed in
.gitignoreand is not committed to the repository, so it won't affect CI or other contributors' environments.
Detailed documentation for each algorithm can be found on HexDocs.
| Algorithm | Use When | Time Complexity |
|---|---|---|
| Dijkstra | Non-negative weights, single shortest path | O((V+E) log V) |
| A* | Non-negative weights + good heuristic | O((V+E) log V) |
| Bellman-Ford | Negative weights OR cycle detection needed | O(VE) |
| Floyd-Warshall | All-pairs shortest paths, distance matrices | O(V³) |
| Edmonds-Karp | Maximum flow, bipartite matching, network optimization | O(VE²) |
| BFS/DFS | Unweighted graphs, exploring reachability | O(V+E) |
| Kruskal's MST | Finding minimum spanning tree | O(E log E) |
| Stoer-Wagner | Global minimum cut, graph partitioning | O(V³) |
| Tarjan's SCC | Finding strongly connected components | O(V+E) |
| Tarjan's Connectivity | Finding bridges and articulation points | O(V+E) |
| Hierholzer | Eulerian paths/circuits, route planning | O(V+E) |
| DAG Longest Path | Critical path analysis on strictly directed acyclic graphs | O(V+E) |
| Topological Sort | Ordering tasks with dependencies | O(V+E) |
| Gale-Shapley | Stable matching, college admissions, medical residency | O(n²) |
| Prim's MST | Minimum spanning tree (starts from node) | O(E log V) |
| Kosaraju's SCC | Strongly connected components (two-pass) | O(V + E) |
| Bron-Kerbosch | Maximum and all maximal cliques | O(3^(n/3)) |
| Network Simplex | Global minimum cost flow optimization | O(E) pivots |
| Implicit Search | Pathfinding/Traversal on on-demand graphs | O((V+E) log V) |
- Graph storage: O(V + E)
- Transpose: O(1) - dramatically faster than typical O(E) implementations
- Dijkstra/A*: O(V) for visited set and pairing heap
- Maximum Flow: Flat dictionary residuals with O(1) amortized BFS queue operations
- Graph Generators: O(V²) for complete graphs, O(V) or O(VE) for others
- Stable Marriage: O(n²) Gale-Shapley with deterministic proposal ordering
- Test Suite: 733 tests pass in ~2 seconds
Parts of this project were developed with the assistance of AI coding tools. All AI-generated code has been reviewed, tested, and validated by the maintainer.
Yog - Graph algorithms for Gleam 🌳
