How-To: Multigraphs & Edge Collapsing

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

Introduction

A Multigraph allows multiple (parallel) edges between the same pair of nodes. This is common in transport networks (multiple flights between two cities) or social networks (multiple types of interactions).

While Yog supports multigraphs natively via Yog.Multi, many classic algorithms (like Dijkstra or Max-Flow) are optimized for Simple Graphs. To bridge this gap, Yog allows you to “collapse” parallel edges into a single edge using a custom strategy.

Creating a Multigraph

alias Yog.Multi

# Create an undirected multigraph
mg = Multi.undirected()
  |> Multi.add_node(:london, nil)
  |> Multi.add_node(:paris, nil)

# Add multiple edges (parallel edges)
# add_edge returns {graph, edge_id}
{mg, e1} = Multi.add_edge(mg, :london, :paris, 100) # Flight
{mg, e2} = Multi.add_edge(mg, :london, :paris, 50)  # Train
{mg, e3} = Multi.add_edge(mg, :london, :paris, 300) # Ferry

IO.puts "Total edges: #{Multi.size(mg)}"
IO.inspect Multi.edges_between(mg, :london, :paris), label: "Edges between London and Paris"

Visualizing Multigraphs

Yog can render multigraphs with both DOT and Mermaid, showing parallel edges as distinct lines.

# DOT rendering (rich, customizable)
dot = Yog.Multi.DOT.to_dot(mg)
Kino.VizJS.render(dot)

# Mermaid rendering (great for docs)
mermaid = Yog.Multi.Mermaid.to_mermaid(mg)
IO.puts(mermaid)

Styled Multigraph Rendering

# Render with per-edge styling
opts = %{
  Yog.Multi.DOT.default_options()
  | edge_attributes: fn _from, _to, edge_id, weight ->
      color =
        cond do
          weight == 50 -> "#10b981"  # Train (fastest)
          weight == 100 -> "#3b82f6" # Flight
          true -> "#f59e0b"          # Ferry
        end
      [{:color, color}, {:penwidth, 2}]
    end
}

Kino.VizJS.render(Yog.Multi.DOT.to_dot(mg, opts))

Building Multigraphs Incrementally

Use Yog.Builder.Live with sync_multi/2 to build multigraphs incrementally.

builder =
  Yog.Builder.Live.new()
  |> Yog.Builder.Live.add_edge("A", "B", 10)
  |> Yog.Builder.Live.add_edge("A", "B", 20)
  |> Yog.Builder.Live.add_edge("B", "C", 5)

{builder, multi} = Yog.Builder.Live.sync_multi(builder, Yog.Multi.directed())
IO.puts("After first sync: #{Multi.order(multi)} nodes, #{Multi.size(multi)} edges")

# Add more parallel edges incrementally
builder = Yog.Builder.Live.add_edge(builder, "A", "B", 30)
{_builder, multi} = Yog.Builder.Live.sync_multi(builder, multi)
IO.puts("After second sync: #{Multi.order(multi)} nodes, #{Multi.size(multi)} edges")

# Query parallel edges
IO.inspect Multi.edges_between(multi, 0, 1), label: "Edges A -> B"

Collapsing Strategies

To run a shortest-path algorithm, we might only care about the cheapest or fastest option. We can collapse the multigraph into a simple graph.

1. Keep Minimum (Shortest Path)

When finding the shortest path, we usually want to keep only the edge with the smallest weight.

# Collapse keeping the minimum weight
g_min = Multi.to_simple_graph(mg, fn a, b -> min(a, b) end)

IO.puts "Simple Graph Edge Weight: #{Yog.Model.edge_weight(g_min, :london, :paris)}"
# Should be 50

2. Keep Maximum (Throughput)

In some scenarios, you might want to know the maximum capacity of any single link.

g_max = Multi.to_simple_graph(mg, fn a, b -> max(a, b) end)

IO.puts "Simple Graph Edge Weight: #{Yog.Model.edge_weight(g_max, :london, :paris)}"
# Should be 300

3. Sum Weights (Total Capacity)

For Max-Flow problems, you often want to sum the capacities of all parallel links.

g_sum = Multi.to_simple_graph(mg, fn a, b -> a + b end)

IO.puts "Simple Graph Edge Weight: #{Yog.Model.edge_weight(g_sum, :london, :paris)}"
# Should be 450 (100 + 50 + 300)

Running Algorithms

Once collapsed, you can use any standard Yog algorithm.

# 1. Create a complex multigraph
mg = Multi.undirected()
  |> Multi.add_node(:a, nil)
  |> Multi.add_node(:b, nil)
  |> Multi.add_node(:c, nil)
  # Parallel edges between A and B
  |> (fn g -> {g, _} = Multi.add_edge(g, :a, :b, 10); g end).()
  |> (fn g -> {g, _} = Multi.add_edge(g, :a, :b, 5); g end).()
  # Single edge between B and C
  |> (fn g -> {g, _} = Multi.add_edge(g, :b, :c, 2); g end).()

# 2. Collapse for shortest path
simple_g = Multi.to_simple_graph(mg, &min/2)

# 3. Solve!
{:ok, path} = Yog.Pathfinding.shortest_path(in: simple_g, from: :a, to: :c)

IO.inspect(path.nodes, label: "Shortest Path Nodes")
IO.puts "Total Weight: #{path.weight}" # Should be 7 (5 + 2)

Multigraph Algorithms

Some algorithms work directly on multigraphs without collapsing.

Eulerian Circuits and Paths

# Build a multigraph that has an Eulerian circuit
mg = Multi.undirected()
  |> Multi.add_node(:a, nil)
  |> Multi.add_node(:b, nil)
  |> Multi.add_node(:c, nil)
  |> (fn g -> {g, _} = Multi.add_edge(g, :a, :b, 1); g end).()
  |> (fn g -> {g, _} = Multi.add_edge(g, :a, :b, 2); g end).()
  |> (fn g -> {g, _} = Multi.add_edge(g, :b, :c, 3); g end).()
  |> (fn g -> {g, _} = Multi.add_edge(g, :b, :c, 4); g end).()

IO.puts("Has Eulerian circuit? #{Multi.has_eulerian_circuit?(mg)}")

if Multi.has_eulerian_circuit?(mg) do
  circuit = Multi.find_eulerian_circuit(mg)
  IO.inspect(circuit, label: "Eulerian Circuit")
end

Traversals

# BFS and DFS work on multigraphs too
IO.inspect(Multi.bfs(mg, :a), label: "BFS from A")
IO.inspect(Multi.dfs(mg, :a), label: "DFS from A")

Summary

Multigraphs are powerful for modeling, but simple graphs are often better for analysis.

• Use Yog.Multi to capture the full complexity of your data.
• Use Yog.Builder.Live.sync_multi/2 to build multigraphs incrementally.
• Use Yog.Multi.DOT and Yog.Multi.Mermaid to visualize parallel edges.
• Use to_simple_graph/2 to prepare your data for algorithms.
• Choose your combine function (min, max, sum) based on the problem you are solving.

Next, explore Customizing Visualizations to see how to render these parallel edges!