Yog 🌳

যোগ • (jōg) noun

1. connection, link, union
2. addition, sum

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

Yog is a comprehensive graph algorithm library for Gleam, providing implementations of classic and research-grade graph algorithms with a functional API.

YogEx - Elixir implementation of Yog with a superset of features.

Gleam vs Elixir Comparison - Detailed feature comparison.

Features

Yog provides balanced graph algorithms across multiple domains:

Core Capabilities

Pathfinding & Flow — Shortest paths (Dijkstra, A*, Bellman-Ford, Floyd-Warshall, Johnson’s), maximum flow (Edmonds-Karp), min-cost flow (Network Simplex), min-cut (Stoer-Wagner), and implicit state-space search.

Network Analysis — Centrality measures (PageRank, betweenness, closeness, eigenvector, Katz), community detection (Louvain, Leiden, Infomap, Walktrap), and network metrics (assortativity, diameter).

Connectivity & Structure — SCCs (Tarjan/Kosaraju), bridges, articulation points, cyclicity detection, and reachability (transitive closure/reduction).

Graph Operations — Mapping, filtering, subgraph extraction, merge, and O(1) transpose.

Directed Acyclic Graphs (DAG) — Stable Dag(n, e) wrapper with strictly-enforced acyclicity and O(V+E) DP routines like longest_path (Critical Path).

Developer Experience

Generators & Builders — 40+ generators including classic patterns (complete, grid, trees, Platonic solids) and random models (Erdős-Rényi, Barabási-Albert, Watts-Strogatz).

I/O & Visualization — Mermaid, DOT (Graphviz), and high-quality ASCII/Unicode grid rendering for terminal diagnostic.

Efficient Data Structures — Built-in Pairing Heaps for priority queues, Disjoint Set (Union-Find) with path compression, and optimized two-list Queues.

Complete Algorithm Catalog — See all 60+ algorithms, selection guidance, and Big-O complexities.

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

  let assert Ok(graph) =
    yog.add_edges(graph, [
      #(1, 2, 5),
      #(2, 3, 3),
      #(1, 3, 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

Detailed examples are located in the test/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.
• Graph creation - Comprehensive guide to 10+ ways of creating graphs.

Running Examples Locally

The examples live in the test/examples/ directory and can be run directly:

gleam run -m examples/gps_navigation
gleam run -m examples/network_bandwidth
# etc.

Algorithm & Generator Catalog

Yog provides a vast library of algorithms and graph generators. See the Algorithm Catalog for a complete list including time complexities and use cases.

Benchmarking

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

gleam run -m bench/simple_pathfinding

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

Development

Running Tests

Run the full test suite:

gleam test

Run tests for a specific module:

./test_module.sh yog/pathfinding/bidirectional_test

Run a specific test function:

./test_module.sh yog/pathfinding/bidirectional_test dijkstra_complex_diamond_test

Running Examples

Run all examples at once:

./run_examples.sh

Run a specific example:

gleam run -m examples/gps_navigation

Project Structure

• src/yog/ - Core graph library modules
• test/ - Unit tests and property-based tests
• test/examples/ - Real-world usage examples
• test/pbt/ - Property-based tests
• test/bench/ - Performance benchmarks

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