Yog

                    ★
                   /|\
                  / | \
                 /  |  \
                Y   |   O--------G
               /    |    \      /
              /     |     \    /
             /      |      \  /
            যো------+-------গ
           / \      |      / \
          /   \     |     /   \
         /     \    |    /     \
        ✦       ✦   |   ✦       ✦
                   

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
• Property-Based Testing: Exhaustively tested across core graph operations and invariants using qcheck

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)

Benchmarking

Yog includes built-in benchmarking utilities using gleamy/bench. Run the example benchmark:

gleam run -m internal/bench/simple_pathfinding

Or use the provided script to run all benchmarks:

./run_benchmarks.sh

For detailed instructions on creating custom benchmarks, interpreting results, and comparing against reference implementations, see the Benchmarking Guide.

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