Yog

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

Package VersionHex Docs

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

🔷 F# Port - Also available for F# with similar functional APIs | 📊 Gleam vs F# Comparison - Detailed feature comparison

Features

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

We have some real-world projects that use Yog for graph algorithms:

Detailed examples are located in the test/examples/ directory:

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 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³)
Johnson's All-pairs shortest paths in sparse graphs with negative weights O(V² log V + VE)
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)
PageRank Link-quality node importance O(V+E) per iter
Betweenness Bridge/gatekeeper detection O(VE) or O(V³)
Closeness / Harmonic Distance-based importance O(VE log V)
Eigenvector / Katz Influence based on neighbor centrality O(V+E) per iter
Louvain Modularity optimization, large graphs O(E log V)
Leiden Quality guarantee, well-connected communities O(E log V)
Label Propagation Very large graphs, extreme speed O(E) per iter
Infomap Information-theoretic flow tracking O(E) per iter
Walktrap Random-walk structural communities O(V² log V)
Girvan-Newman Hierarchical edge betweenness O(E²V)
Clique Percolation Overlapping community discovery O(3^(V/3))
Local Community Massive/infinite graphs, seed expansion O(S × E_S)
Fluid Communities Exact k partitions, fast O(E) per iter

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.

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