Getting Started with Yog

Mix.install([
  {:yog_ex, "~> 0.98"},
  {:kino_vizjs, "~> 0.8.0"}
])

What is Yog?

যোগ (jōg) means connection, link, or union.

Yog is a comprehensive graph algorithm library for Elixir. It provides efficient, immutable data structures and a wide array of algorithms for network analysis, pathfinding, and community detection.

Creating your first Graph

In Yog, graphs are immutable structures. You can create an empty graph of a specific kind:

# Create a directed graph
g = Yog.directed()

# Create an undirected graph
u = Yog.undirected()

By default, a graph consists of:

• kind: :directed or :undirected
• nodes: A map of node_id => data
• edges: Adjacency maps for fast lookups and O(1) transpose.

Growing the Graph

We build graphs by adding nodes and edges. Since Yog is functional and immutable, every operation returns a new graph.

Adding Nodes

Nodes can have any term as an ID and any term as data.

g = 
  Yog.directed()
  |> Yog.add_node(1, %{label: "Start"})
  |> Yog.add_node(2, %{label: "End"})
  |> Yog.add_nodes_from([3, 4, 5]) # Adding multiple nodes with nil data

Now let’s visualize the nodes. Yog supports both Dot and Mermaid for rendering graphs.

Kino.Layout.tabs(
  Dot: Kino.VizJS.render(Yog.Render.DOT.to_dot(g), height: "100px"),
  Mermaid: Kino.Mermaid.new(Yog.Render.Mermaid.to_mermaid(g))
)

Adding Edges

Edges connect nodes. In Yog, we provide several ways to add edges, depending on whether you want to ensure the nodes exist or handle missing nodes.

# 1. add_edge! - Raises if nodes don't exist
g = g |> Yog.add_edge!(1, 2, 10)
IO.inspect(g)

# 2. add_edge_ensure - Automatically creates nodes if they are missing
g = g |> Yog.add_edge_ensure(2, 3, 5, %{label: "Auto-created"})
IO.inspect(g)

# 3. add_simple_edge - Adds an edge with weight 1
g = g |> Yog.add_simple_edge!(3, 1)
IO.inspect(g)

And this is how the graph looks like:

Kino.Layout.tabs(
  Dot: Kino.VizJS.render(Yog.Render.DOT.to_dot(g)),
  Mermaid: Kino.Mermaid.new(Yog.Render.Mermaid.to_mermaid(g))
)

LabeledBuilder and the Builder pattern

Yog lets you define your graph with any data as node ID or edge weight.

graph =
  Yog.directed()
  |> Yog.add_node({0, 0}, nil)
  |> Yog.add_node(:point, %{})
  |> Yog.add_edge!({0, 0}, :point, :unreachable)


Yog.all_edges(graph)

However, many algorithms or graph file formats are simplier when the Node IDs are integers. It also makes traversals and lookups faster. The graph above could look like:

graph =
  Yog.directed()
  |> Yog.add_node(1, {{0, 0}, nil})
  |> Yog.add_node(2, {:point, %{}})
  |> Yog.add_edge!(1, 2, :unreachable)

Yog.all_edges(graph)

The example above is much cleaner. But it also come with an ergonomic tax. If consuming from a stream, one would need to keep a map of ID to Data, and Data to ID.

This is exactly where the LabeledBuilder becomes relevant.

Yog has a set of Builders that acts like a domain specific graph creation API - hides the implementation detail but creates Yog graph underneath. They can be added anywhere, but Yog provides a few builders to get you going.

The one we discuss here is the LabeledBuilder. This lets you build graphs with any data as NodeID but creates a graph with integer based ID.

Here’s an example:

builder =
  Yog.Builder.Labeled.directed()
  |> Yog.Builder.Labeled.add_edge("A", "B", 10)
  |> Yog.Builder.Labeled.add_edge("B", "C", 5)

IO.puts("These are the labels")
IO.inspect(builder |> Yog.Builder.Labeled.all_labels())

IO.puts("A registry that maps labels to Node IDs")
IO.inspect(builder |> Yog.Builder.Labeled.to_registry())

IO.puts("The underlying graph")
graph = builder |> Yog.Builder.Labeled.to_graph()
IO.inspect(Yog.node_ids(graph))

IO.puts("To query between NodeID and Label")
IO.inspect(Yog.Builder.Labeled.get_id(builder, "A"))
IO.inspect(Yog.Builder.Labeled.get_label(builder, 0))

There are a few other builders:

• LiveBuilder - superpowered LabeledBuilder instead of creating the whole builder, it lets you continuously add/remove nodes from builder and create graph via a WAL log lite.
• GridGraph & ToroidalGraph - Creates graphs from 2D grid data. Toroidal wraps ends of rows and columns.

A use case for Yog builders is Choreo where builder pattern is used to add system design DSL on top of Yog.

Examining the Graph

You can query the graph’s structure using functions in the main Yog module or Yog.Model.

IO.puts "Nodes: #{Yog.node_count(g)}"
IO.puts "Edges: #{Yog.edge_count(g)}"

# Get successors of node 2
IO.inspect(Yog.successors(g, 2), label: "Successors of 2")

# Get neighbors regardless of direction
IO.inspect(Yog.neighbors(g, 3), label: "Neighbors of 3")

# Check if the graph is cyclic
IO.puts("Is cyclic? #{Yog.cyclic?(g)}")

Transformations

Yog excels at functional transformations. You can map or filter nodes and edges to create new graph versions.

# Double all edge weights
high_weight_graph = Yog.Transform.map_edges(g, fn weight -> 
  if is_number(weight), do: weight * 2, else: weight 
end)

# Filter for nodes with numeric IDs
numeric_only = Yog.Transform.filter_nodes_indexed(g, fn id, _ -> is_integer(id) end)

Comprehensive Algorithms

Yog comes with 223 registered algorithms, generators, and helper tools categorized across 22 areas

Pathfinding

cols = 6
grid_data = List.duplicate(List.duplicate(".", cols), cols)
grid_builder = Yog.Builder.Grid.from_2d_list(grid_data, :undirected, Yog.Builder.Grid.always())
graph = Yog.Builder.Grid.to_graph(grid_builder)

start_node = Yog.Builder.Grid.coord_to_id(0, 0, cols)
end_node = Yog.Builder.Grid.coord_to_id(5, 5, cols)

{:ok, path} = Yog.Pathfinding.Dijkstra.shortest_path(graph, start_node, end_node)

# Create base options with coordinate labels for nodes, and hide edge labels
base_opts = 
  Yog.Render.DOT.default_options()
  |> Map.put(:node_label, fn id, _data ->
    {r, c} = Yog.Builder.Grid.id_to_coord(id, cols)
    "#{r},#{c}"
  end)
  |> Map.put(:edge_label, fn _weight -> "" end)

# Pass base_opts to path_to_options to highlight path and retain custom labeling
opts = Yog.Render.DOT.path_to_options(path, base_opts)

Kino.VizJS.render(Yog.Render.DOT.to_dot(graph, opts), height: "800px")

Community Detection

# Generate a graph with 24 nodes, 3 communities, p_in = 0.7, p_out = 0.1
sbm = Yog.Generator.Random.sbm(24, 3, 0.7, 0.1, community_sizes: [8, 8, 8])
result = Yog.Community.Louvain.detect(sbm)

IO.puts("Detected #{result.num_communities} communities")
IO.inspect(result.assignments, label: "Node -> Community")

# Visualize with community colors
opts = Yog.Render.DOT.community_to_options(result)
Kino.VizJS.render(Yog.Render.DOT.to_dot(sbm, opts), engine: "circo", height: "1200px")

Visualization Formats

Yog supports both Graphviz DOT and Mermaid.js output.

# Graphviz DOT (rich, customizable)
dot = Yog.Render.DOT.to_dot(g)

# Mermaid.js (great for Markdown docs)
mermaid = Yog.Render.Mermaid.to_mermaid(g)


IO.puts("DOT")
IO.puts(dot)
IO.puts("Mermaid")
IO.puts(mermaid)

Kino.Layout.tabs(
  Dot: Kino.VizJS.render(dot),
  Mermaid: Kino.Mermaid.new(mermaid)
)

Serialization

You can easily import/export graphs in various formats like GraphML, JSON, GDF, Graph6, or DOT.

xml = """
<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns"  
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns
     http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
  <graph id="G" edgedefault="undirected">
    <node id="n0"/>
    <node id="n1"/>
    <node id="n2"/>
    <node id="n3"/>
    <node id="n4"/>
    <node id="n5"/>
    <node id="n6"/>
    <node id="n7"/>
    <node id="n8"/>
    <node id="n9"/>
    <node id="n10"/>
    <edge source="n0" target="n2"/>
    <edge source="n1" target="n2"/>
    <edge source="n2" target="n3"/>
    <edge source="n3" target="n5"/>
    <edge source="n3" target="n4"/>
    <edge source="n4" target="n6"/>
    <edge source="n6" target="n5"/>
    <edge source="n5" target="n7"/>
    <edge source="n6" target="n8"/>
    <edge source="n8" target="n7"/>
    <edge source="n8" target="n9"/>
    <edge source="n8" target="n10"/>
  </graph>
</graphml>
"""

# Let's load the graph
{:ok, graph} = Yog.IO.GraphML.deserialize(xml)

# Export to GDF (GUESS format)
gdf = Yog.IO.GDF.serialize(graph)
IO.puts String.slice(gdf, 0, 300) <> "..."

Kino.Layout.grid([
  Kino.Markdown.new("""
  ```text
  #{gdf}
  ```
  """),
  graph
  |> Yog.Render.DOT.to_dot()
  |> Kino.VizJS.render(height: "600px")
], columns: 2)

Next Steps

Explore the Algorithm Catalog to see everything Yog can do!