YogEx 🌳

যোগ • (jōg) noun

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

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

Yog is a set of Graph and Network algorithms and data structures implemented in Elixir and packaged as a common API.

There is also a similar library written in Gleam, which I used to learn Gleam by collecting and translating most of the algorithms I have written in Elixir over the years.

Both libraries are actively maintained, with the Elixir version getting new features more frequently, and also sporting more experimental features.

Features

YogEx provides comprehensive graph algorithms organized into modules:

Core Capabilities

Pathfinding & Flow — Shortest paths (Dijkstra, A*, Bellman-Ford, Floyd-Warshall, Johnson's), maximum flow (Edmonds-Karp), min-cut (Stoer-Wagner), and implicit state-space search for on-demand graphs.

Network Analysis — Centrality measures (PageRank, betweenness, closeness, eigenvector, Katz) and network health metrics.

Community Detection — Detect communities and cluster structures using Louvain, Leiden, Infomap, and Walktrap, with modularity and coverage metrics.

Connectivity & Structure — SCCs (Tarjan/Kosaraju), bridges, articulation points, K-core decomposition, and reachability analysis with exact and HyperLogLog-based estimation.

Graph Operations — Union, intersection, difference, Cartesian product, power, isomorphism, and O(1) transpose.

Developer Experience

Generators & Builders — Classic patterns (complete, cycle, grid, Petersen), random models (SBM, R-MAT), and a comprehensive Maze Generation suite (Recursive Backtracker, Wilson's, Kruskal's, Eller's, etc.) with labeled and grid builders.

Graph Layouts — Compute 2D node coordinates in pure Elixir (Circular, Random, Spring/Barnes-Hut, Tutte, Concentric Shell, Multipartite, Grid, and Manual placement) or import layouts from GraphViz.

I/O & Visualization — GraphML, GDF, Pajek, LEDA, TGF, JSON serialization plus ASCII, DOT, and Mermaid rendering.

Functional (Experimental) — Pure inductive graph library (FGL) for elegant recursive algorithms.

Complete Algorithm Catalog — See all 60+ algorithms, underlying data structures (Pairing Heap, Union-Find, HyperLogLog), and selection guidance with Big-O complexities.

Installation

Basic Installation

Add YogEx to your list of dependencies in mix.exs:

def deps do
  [
    {:yog_ex, "~> 0.99.1"}
  ]
end

Then run:

mix deps.get

Optional Dependencies

YogEx includes several optional dependencies that enable additional I/O and interoperability features:

To use these features, add the optional dependencies to your mix.exs:

def deps do
  [
    {:yog_ex, "~> 0.99.1"},
    {:saxy, "~> 1.5"},       # For fast GraphML/XML parsing
    {:jason, "~> 1.4"},      # For JSON import/export
    {:libgraph, "~> 0.16"}   # For libgraph interoperability
  ]
end

XML/GraphML with Saxy

# Reading large GraphML files is significantly faster with saxy
{:ok, graph} = Yog.IO.GraphML.read("large_network.graphml")

# Writing GraphML
Yog.IO.GraphML.write("output.graphml", graph)

JSON Serialization with Jason

# Export to various JSON formats
json = Yog.IO.JSON.to_json(graph, Yog.IO.JSON.export_options_for(:d3_force))

# Import from JSON
{:ok, graph} = Yog.IO.JSON.from_json(json_string)

Libgraph Interoperability

# Convert Yog graph to libgraph
libgraph = Yog.IO.Libgraph.to_libgraph(graph)

# Convert libgraph back to Yog
{:ok, yog_graph} = Yog.IO.Libgraph.from_libgraph(libgraph)

Livebook

For livebook, add the following:

Mix.install(
  {:yog_ex, "~> 0.99.1"}
)

There is a Kino App that can be used to explore the library and create and render graphs.

Usage

alias Yog.Pathfinding

# Create a directed graph
graph =
  Yog.directed()
  |> Yog.add_node(1, "Start")
  |> Yog.add_node(2, "Middle")
  |> Yog.add_node(3, "End")
  |> Yog.add_edge_ensure(from: 1, to: 2, with: 5)
  |> Yog.add_edge_ensure(from: 2, to: 3, with: 3)
  |> Yog.add_edge_ensure(from: 1, to: 3, with: 10)

# Find shortest path using Dijkstra (uses :ok/:error tuples and Path struct)
case Pathfinding.shortest_path(
  in: graph,
  from: 1,
  to: 3
) do
  {:ok, path} ->
    IO.puts("Found path with weight: #{path.weight}")
  :error ->
    IO.puts("No path found")
end
# => Found path with weight: 8

Examples

Detailed examples are located in the examples/README.md file.

Advent of Code Solutions

YogEx is used to solve Advent of Code challenges.

See all Advent of Code solutions tagged with graph that demonstrate usage of YogEx algorithms in the Advent of Code Repository.

Projects Using Yog

Yog powers the following open-source libraries that build domain-specific abstractions on top of its graph engine:

Choreo

An analysis-first diagramming library for Elixir that models systems (including infrastructure, FSMs, dataflows, threat models, and workflows) to perform live queries like reachability, cycle detection, and bottleneck analysis.

Meridian

A projection-aware spatial graph library for Elixir that integrates geographic coordinate systems, road networks (GeoJSON), and hex grids (H3) directly into graph theory algorithms.

Development

Running Tests

mix test

Run tests for a specific module:

mix test test/yog/pathfinding/dijkstra_test.exs

Project Structure

• lib/yog/ — Core graph library modules (pure Elixir)
• test/ — Unit tests and doctests
• examples/ — Real-world usage examples

Property-Based Testing

This library uses property-based testing (PBT) via StreamData to ensure that algorithms hold up against a wide range of automatically generated graph structures.

See the PROPERTIES.md for a complete catalog of all algorithmic invariants (hypotheses) verified by the test suite.

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.