YogEx 🌳

যোগ • (jōg) noun

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

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

A comprehensive pure Elixir graph algorithm and network analysis library providing implementations of classic graph algorithms with a functional API.

🔷 Pure Elixir — It started off as a wrapper around the Gleam Yog library, YogEx is now fully implemented in Elixir with no external runtime dependencies.

[!WARNING] API Stability: Until the version reaches 1.0.0, there may be breaking changes. While I'll try my best to keep the API stable, there's no guarantee. The primary focus is on performance, documentation, and bugfixes.

Features

YogEx provides comprehensive graph algorithms organized into focused 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), community detection (Louvain, Leiden, Infomap, Walktrap), and network health 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) and random models (Erdős-Rényi, Barabási-Albert, Watts-Strogatz) with labeled and grid builders.

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

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

📖 Complete Algorithm Catalog — See all 60+ algorithms with time complexities and selection guidance.

Installation

Basic Installation

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

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

Then run:

mix deps.get

Livebook

For livebook, add the following:

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

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

Graph I/O Support

YogEx includes comprehensive graph I/O modules (Yog.IO.*) for popular formats:

• GraphML - XML-based format (Gephi, yEd, Cytoscape, NetworkX)
• GDF - GUESS Graph Format (Gephi)
• Pajek - Social network analysis (.net format)
• LEDA - Library of Efficient Data types and Algorithms
• TGF - Trivial Graph Format
• JSON - Adjacency list and matrix formats

Quick Start

Shortest Path

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

Community Detection

alias Yog.Community

# Build a graph with two communities
graph =
  Yog.undirected()
  |> Yog.add_edge_with(1, 2, 1, & &1)
  |> Yog.add_edge_with(2, 3, 1, & &1)
  |> Yog.add_edge_with(1, 3, 1, & &1)   # Triangle: 1-2-3
  |> Yog.add_edge_with(4, 5, 1, & &1)
  |> Yog.add_edge_with(5, 6, 1, & &1)
  |> Yog.add_edge_with(4, 6, 1, & &1)   # Triangle: 4-5-6
  |> Yog.add_edge_with(3, 4, 1, & &1)   # Bridge between communities

communities = Community.Louvain.detect(graph)
IO.puts("Found #{communities.num_communities} communities")
# => Found 2 communities

modularity = Community.modularity(graph, communities)
IO.puts("Modularity: #{modularity}")
# => Modularity: 0.35714285714285715

Graph Generators

alias Yog.Generator.{Classic, Random}
# Classic graph patterns
complete = Classic.complete(10)       # K₁₀ complete graph
cycle = Classic.cycle(20)              # C₂₀ cycle graph
petersen = Classic.petersen()           # The famous Petersen graph
grid = Classic.grid_2d(5, 5)           # 5×5 grid lattice

# Random graph models
sparse = Random.erdos_renyi_gnp(100, 0.05)    # G(n,p) model
scale_free = Random.barabasi_albert(1000, 3)   # Preferential attachment
small_world = Random.watts_strogatz(100, 6, 0.1)  # Small-world

Grid Builder (Maze Solving)

alias Yog.Builderr.Grid
alias Yog.Pathfinding
alias Yog.Render.ASCII

# Build a maze from a 2D grid
maze = [
  [".", "#", "#", "."],
  [".", ".", "#", "#"],
  ["#", ".", ".", "."],
  ["#", "#", "#", "."],
  ["#", ".", "#", "."],
]

# Create grid with walkable predicate
grid = Grid.from_2d_list(maze, :undirected, Grid.including(["."]))

IO.puts(ASCII.grid_to_string(grid, %{0 => "S", 19 => "E"}))

# Prints the Maze:
#
#  +---+---+---+---+
#  | S |   |   |   |
#  +   +---+---+---+
#  |       |   |   |
#  +---+   +---+---+
#  |   |           |
#  +---+---+---+   +
#  |   |   |   |   |
#  +---+---+---+   +
#  |   |   |   | E |
#  +---+---+---+---+
#

Labeled Graph Builder

alias Yog.Builder.Labeled
alias Yog.Pathfinding

# Build graphs with meaningful labels instead of integer IDs
builder =
  Labeled.directed()
  |> Labeled.add_edge("London", "Paris", 450)
  |> Labeled.add_edge("Paris", "Berlin", 878)
  |> Labeled.add_edge("London", "Berlin", 930)

# Convert to graph for algorithms
graph = Labeled.to_graph(builder)

# Look up internal IDs by label
{:ok, london_id} = Labeled.get_id(builder, "London")
{:ok, berlin_id} = Labeled.get_id(builder, "Berlin")

# Find shortest path using integer IDs
case Pathfinding.shortest_path(in: graph, from: london_id, to: berlin_id) do
  {:ok, path} ->
    labeled_path = Enum.map(path.nodes, fn id ->
      graph.nodes[id]
    end)
    IO.puts("Route: #{Enum.join(labeled_path, " -> ")}, Distance: #{path.weight} km")
end
# => Route: London -> Berlin, Distance: 930 km

Centrality Analysis

alias Yog.Centrality

graph =
  Yog.directed()
  |> Yog.add_node(1, nil) 
  |> Yog.add_node(2, nil) 
  |> Yog.add_node(3, nil)
  |> Yog.add_edges!([{1, 2, 1}, {2, 3, 1}, {1, 3, 1}])

# Various centrality measures
pagerank = Centrality.pagerank(graph)
# => %{1 => 0.19757597883790196, 2 => 0.2815434776603495, 3 => 0.5208805435017486}
betweenness = Centrality.betweenness(graph)
# => %{1 => 0.0, 2 => 0.0, 3 => 0.0}
closeness = Centrality.closeness(graph)
# => %{1 => 1.0, 2 => 0.0, 3 => 0.0}
degree = Centrality.degree(graph, :out_degree)
# => %{1 => 1.0, 2 => 0.5, 3 => 0.0}

Graph I/O & Interoperability

alias Yog.IO.{GDF, GraphML, Pajek}
# Create graph
graph =
  Yog.directed()
  |> Yog.add_node(1, "Alice")
  |> Yog.add_node(2, "Bob")
  |> Yog.add_edge_ensure(from: 1, to: 2, with: "follows")

# Serialize to popular formats like GraphML, TGF, LEDA, Pajek, JSON, or GDF
gdf_string = GDF.serialize(graph)
graphml_string = GraphML.serialize(graph)
pajek_string = Pajek.serialize(graph)

# Parse from string or read from file
{:ok, graph} = GraphML.deserialize(graphml_string)

# Read directly from file
# {:ok, loaded} = GraphML.read("slashdot.xml")

Functional Inductive Graphs (Experimental)

YogEx now includes an experimental implementation of Martin Erwig's Functional Graph Library (FGL) natively in Elixir under the Yog.Functional namespace. This provides an elegant, purely functional approach to graph algorithms using inductive decomposition (match/2) instead of mutable references or explicit "visited" sets.

alias Yog.Functional.{Algorithms, Model}

# Create an inductive functional graph
graph =
  Model.empty()
  |> Model.put_node(1, "A")
  |> Model.put_node(2, "B")
  |> Model.put_node(3, "C")
  |> Model.add_edge!(1, 2, 1)
  |> Model.add_edge!(2, 3, 2)

# Inductive Top-Sort - consumes the graph naturally, no mutable visited sets!
{:ok, order} = Algorithms.topsort(graph)
# => [1, 2, 3]

# Inductive Dijkstra
Algorithms.shortest_path(graph, 1, 3)
# => {:ok, [1, 2, 3], 3}

📖 Learn more: See the Functional Graphs README for a deep dive into the build/burn pattern, context-based traversal, and the philosophy of inductive graph decomposition.

Examples

Detailed examples are located in the examples/ directory:

Pathfinding & Optimization

• GPS Navigation - Shortest path using A* and heuristics
• City Distance Matrix - Floyd-Warshall for all-pairs shortest paths
• Network Bandwidth - ⭐ Max flow for bandwidth optimization with bottleneck analysis
• Network Cable Layout - Minimum Spanning Tree using Kruskal's

Matching & Assignment

• Job Matching - ⭐ Max flow for bipartite matching and assignment problems
• Job Assignment - Bipartite maximum matching
• Medical Residency - Stable marriage matching (Gale-Shapley algorithm)

Graph Analysis

• Social Network Analysis - Finding communities using SCCs
• Global Minimum Cut - Stoer-Wagner algorithm
• Bridges of Königsberg - Eulerian circuit and path detection

Ordering & Scheduling

• Task Scheduling - Basic topological sorting
• Task Ordering - Lexicographical topological sort

Traversal & Exploration

• Cave Path Counting - Custom DFS with backtracking
• Flood Fill - BFS-based region exploration
• Number of Islands - Connected component counting

Graph Construction & Visualization

• Graph Creation - Comprehensive guide to 10+ ways of creating graphs
• Graph Generation Showcase - ⭐ All classic graph patterns with statistics
• DOT rendering - Exporting graphs to Graphviz format
• Mermaid rendering - Generating Mermaid diagrams
• Graph I/O - Exporting matrices and objects to JSON and other formats for interoperability

Running Examples

mix run examples/gps_navigation.exs
mix run examples/network_bandwidth.exs
# etc.

Algorithm Selection Guide

Detailed documentation for each algorithm can be found on HexDocs.

Underlying Algorithms & Data Structures

Beyond graph algorithms, YogEx implements several fundamental computer science techniques:

Probabilistic Data Structures

Classic Algorithms

Data Structures

Module Overview

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.

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

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.

YogEx — Graph algorithms for Elixir 🌳