yog - v5.1.1

Yog

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

Package Version Hex 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

⚠️ Experimental Features

The following modules are experimental and provide minimal, working functionality:

These modules are functional but may not be fully optimized for performance. Additional features, performance enhancements, and API changes are expected in future versions. Use with caution in production environments.

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.

AlgorithmUse WhenTime Complexity
DijkstraNon-negative weights, single shortest pathO((V+E) log V)
Bidirectional DijkstraKnown target, weighted graphs, ~2× fasterO((V+E) log V / 2)
Bidirectional BFSKnown target, unweighted graphs, up to 500× fasterO(b^(d/2))
A*Non-negative weights + good heuristicO((V+E) log V)
Bellman-FordNegative weights OR cycle detection neededO(VE)
Floyd-WarshallAll-pairs shortest paths, distance matricesO(V³)
Johnson’sAll-pairs shortest paths in sparse graphs with negative weightsO(V² log V + VE)
Edmonds-KarpMaximum flow, bipartite matching, network optimizationO(VE²)
BFS/DFSUnweighted graphs, exploring reachabilityO(V+E)
Kruskal’s MSTFinding minimum spanning treeO(E log E)
Stoer-WagnerGlobal minimum cut, graph partitioningO(V³)
Tarjan’s SCCFinding strongly connected componentsO(V+E)
Tarjan’s ConnectivityFinding bridges and articulation pointsO(V+E)
HierholzerEulerian paths/circuits, route planningO(V+E)
DAG Longest PathCritical path analysis on strictly directed acyclic graphsO(V+E)
Topological SortOrdering tasks with dependenciesO(V+E)
Gale-ShapleyStable matching, college admissions, medical residencyO(n²)
Prim’s MSTMinimum spanning tree (starts from node)O(E log V)
Kosaraju’s SCCStrongly connected components (two-pass)O(V + E)
Bron-KerboschMaximum and all maximal cliquesO(3^(n/3))
Network SimplexGlobal minimum cost flow optimizationO(E) pivots
Implicit SearchPathfinding/Traversal on on-demand graphsO((V+E) log V)
PageRankLink-quality node importanceO(V+E) per iter
BetweennessBridge/gatekeeper detectionO(VE) or O(V³)
Closeness / HarmonicDistance-based importanceO(VE log V)
Eigenvector / KatzInfluence based on neighbor centralityO(V+E) per iter
LouvainModularity optimization, large graphsO(E log V)
LeidenQuality guarantee, well-connected communitiesO(E log V)
Label PropagationVery large graphs, extreme speedO(E) per iter
InfomapInformation-theoretic flow trackingO(E) per iter
WalktrapRandom-walk structural communitiesO(V² log V)
Girvan-NewmanHierarchical edge betweennessO(E²V)
Clique PercolationOverlapping community discoveryO(3^(V/3))
Local CommunityMassive/infinite graphs, seed expansionO(S × E_S)
Fluid CommunitiesExact k partitions, fastO(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.

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

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

✨ Search Document