Yog 🌳

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

Features

Graph Data Structures: Directed and undirected graphs with generic node and edge data
Pathfinding Algorithms: Dijkstra, A*, Bellman-Ford, Floyd-Warshall
Graph Traversal: BFS and DFS with early termination support
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 algorithm with Union-Find
Minimum Cut: Stoer-Wagner algorithm
Topological Sorting: Kahn’s algorithm with lexicographical variant
Strongly Connected Components: Tarjan’s algorithm
Connectivity: Bridge and articulation point detection
Eulerian Paths & Circuits: Detection and finding using Hierholzer’s algorithm
Bipartite Graphs: Detection and maximum matching (O(1) lookup!)
Disjoint Set (Union-Find): With path compression and union by rank
Efficient Data Structures: Pairing heap for priority queues

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

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 pathfinding.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 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.
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.
City Distance Matrix - Floyd-Warshall for all-pairs shortest paths.
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.

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³)
BFS/DFS	Unweighted graphs, exploring reachability	O(V+E)
Kruskal’s MST	Finding minimum spanning tree	O(E log E)
Tarjan’s SCC	Finding strongly connected components	O(V+E)
Tarjan’s Connectivity	Finding bridges and articulation points	O(V+E)
Topological Sort	Ordering tasks with dependencies	O(V+E)

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 Matching: O(V * E) with O(1) matching lookups.

Yog - Graph algorithms for Gleam 🌳