Yog 🌳

A graph algorithm library for Gleam, providing implementations of classic graph algorithms with a functional API.

Why Yog?

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.

Features

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 like longest_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

Installation

Add Yog to your Gleam project:

gleam add yog

Quick Start

import 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")
  }
}

Examples

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.

Running Examples Locally

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/examples

Then 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 .gitignore and is not committed to the repository, so it won’t affect CI or other contributors’ environments.

Algorithm Selection Guide

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)

Performance Characteristics

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

AI Assistance

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 🌳