YogEx 🌳

যোগ • (jōg) noun

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

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

A comprehensive pure Elixir graph algorithm library providing implementations of classic graph algorithms with a functional API. Formerly a wrapper around the Gleam Yog library, YogEx is now fully implemented in Elixir with no external runtime dependencies.

🔷 Pure Elixir — No Gleam dependencies, just fast native Elixir graph algorithms

Features

• Graph Data Structures: Directed and undirected graphs with generic node and edge data
• Pathfinding Algorithms: Dijkstra, A, Bellman-Ford, Floyd-Warshall, Johnson's, and *Implicit Variants (state-space search)
• Maximum Flow: Highly optimized Edmonds-Karp algorithm with flat dictionary residuals
• Graph Generators: Create classic patterns (complete, cycle, path, star, wheel, bipartite, trees, grids) and random graphs (Erdős-Rényi, Barabási-Albert, Watts-Strogatz)
• Graph Traversal: BFS and DFS with early termination and path finding
• Graph Transformations: Transpose (O(1)!), map, filter, merge, subgraph extraction, edge contraction
• Graph Operations: Union, intersection, difference, Cartesian product, graph power, isomorphism
• Graph Serialization & I/O: First-class support for GraphML, GDF, JSON, LEDA, Pajek, and TGF allowing interoperability with standard tools via Yog.IO.*
• Graph Visualization: ASCII, Mermaid, and DOT (Graphviz) rendering
• Minimum Spanning Tree: Kruskal's and Prim's algorithms with Union-Find and Priority Queues
• Minimum Cut: Stoer-Wagner algorithm for global min-cut
• Network Health: Diameter, radius, eccentricity, assortativity, average path length
• Centrality Measures: PageRank, betweenness, closeness, harmonic, eigenvector, Katz, degree
• Community Detection: Louvain, Leiden, Label Propagation, Girvan-Newman, Infomap, Walktrap, Clique Percolation, Local Community, Fluid Communities
• Community Metrics: Modularity, clustering coefficients, density, triangle counts
• DAG Operations: Type-safe wrapper for directed acyclic graphs with longest path, LCA, transitive closure/reduction
• Topological Sorting: Kahn's algorithm with lexicographical variant
• Strongly Connected Components: Tarjan's and Kosaraju's algorithms
• Maximum Clique: Bron-Kerbosch algorithm for maximal and all maximal cliques
• Connectivity: Bridge and articulation point detection
• Eulerian Paths & Circuits: Detection and finding using Hierholzer's algorithm
• Bipartite Graphs: Detection, maximum matching, and stable marriage (Gale-Shapley)
• Minimum Cost Flow (MCF): Global optimization using the robust Network Simplex algorithm
• Graph Builders: Grid builders (regular & toroidal), labeled builders, live/incremental builders
• Disjoint Set (Union-Find): With path compression and union by rank
• Efficient Data Structures: Pairing heap for priority queues, two-list queue for BFS
• Functional Graphs (Experimental): Elegant port of Erwig's Inductive Graph Library (FGL) for purely functional recursive traversal

Installation

Basic Installation

Add YogEx to your list of dependencies in mix.exs (or Mix.install([...]) for LiveBook or Scripts):

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

Then run:

mix deps.get

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

Optional Dependencies

For improved performance with large GraphML files, add the saxy dependency:

def deps do
  [
    {:yog_ex, "~> 0.60.0"},
    {:saxy, "~> 1.5"}  # Optional: 3-4x faster GraphML parsing
  ]
end

When saxy is available, GraphML parsing automatically uses a fast streaming SAX parser instead of the default DOM parser. For example, a 60MB GraphML file with ~500k edges loads in ~6s with saxy vs ~20s without it.

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!(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 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_node(1, nil) |> Yog.add_node(2, nil) |> Yog.add_node(3, nil)
  |> Yog.add_node(4, nil) |> Yog.add_node(5, nil) |> Yog.add_node(6, nil)
  |> Yog.add_edge!(from: 1, to: 2, with: 1)
  |> Yog.add_edge!(from: 2, to: 3, with: 1)
  |> Yog.add_edge!(from: 1, to: 3, with: 1)   # Triangle: 1-2-3
  |> Yog.add_edge!(from: 4, to: 5, with: 1)
  |> Yog.add_edge!(from: 5, to: 6, with: 1)
  |> Yog.add_edge!(from: 4, to: 6, with: 1)   # Triangle: 4-5-6
  |> Yog.add_edge!(from: 3, to: 4, with: 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_unicode(grid, %{0 => "S", 11 => "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!(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}

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.

Module Overview

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 Flow: Flat dictionary residuals with O(1) amortized BFS queue operations
• Graph Generators: O(V²) for complete graphs, O(V) or O(VE) for others
• Stable Marriage: O(n²) Gale-Shapley with deterministic proposal ordering
• Test Suite: 1000+ tests including doctests ensuring equivalence to the core Gleam suite

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

Pre-publishing checklist:

1. Update version in mix.exs (@version)
2. Update CHANGELOG.md with release date and changes
3. Ensure version is consistent in README.md examples
4. Run mix test - all tests must pass
5. Run mix credo --strict - no issues
6. Update git: git add . and commit changes

Publishing command:

mix hex.publish package

Documentation: HexDocs automatically builds and publishes documentation from your package source code. No separate docs publishing step is needed - your docs will be available at https://hexdocs.pm/yog_ex shortly (5-15 minutes) after publishing the package.

After publishing:

1. Verify package: mix hex.info yog_ex
2. Check package page: https://hex.pm/packages/yog_ex
3. Wait for docs to build: https://hexdocs.pm/yog_ex
4. Tag the release: git tag v0.60.0 && git push --tags

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 🌳