Traversals & Pathfinding

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

Introduction

Graph traversal and pathfinding are at the heart of graph theory. Whether you are searching for a specific node, ordering tasks by priority, or finding the fastest route between two cities, Yog provides optimized, idiomatic tools for the job.

Basic Traversals: BFS and DFS

Systematic exploration of a graph comes in two main flavors:

• Breadth-First Search (BFS): Explores neighbors level-by-level. Ideal for finding the shortest path in unweighted graphs.
• Depth-First Search (DFS): Goes as deep as possible before backtracking. Great for cycle detection and topological sorting.

# Create a simple tree-like graph
g = Yog.from_edges(:undirected, [
    {1, 2, 1}, {1, 3, 1},
    {2, 4, 1}, {2, 5, 1},
    {3, 6, 1}, {3, 7, 1}
  ])

# BFS Order
IO.inspect(Yog.Traversal.walk(g, 1, :breadth_first), label: "BFS Order")

# DFS Order
IO.inspect(Yog.Traversal.walk(g, 1, :depth_first), label: "DFS Order")

Topological Sort (Task Ordering)

Topological sort is used to order a Directed Acyclic Graph (DAG) such that for every directed edge $u \to v$, node $u$ comes before $v$. This is perfect for build systems or project management.

tasks = Yog.from_edges(:directed, [
    {"Design", "Code", 1},
    {"Design", "Tests", 1},
    {"Code", "Review", 1},
    {"Tests", "Review", 1},
    {"Review", "Deploy", 1}
  ])

case Yog.Traversal.topological_sort(tasks) do
  {:ok, order} -> IO.inspect(order, label: "Execution Order")
  {:error, :contains_cycle} -> IO.puts "Error: Circular dependency detected!"
end

Pathfinding: Dijkstra and A*

When your edges have weights (like distance, time, or cost), you need more sophisticated algorithms.

Dijkstra’s Algorithm

The gold standard for single-source shortest paths with non-negative weights.

map = Yog.from_edges(:undirected, [
    {:london, :paris, 2},
    {:paris, :berlin, 5},
    {:london, :berlin, 10},
    {:berlin, :rome, 6},
    {:paris, :rome, 12}
  ])

{:ok, path} = Yog.Pathfinding.shortest_path(in: map, from: :london, to: :rome)

IO.puts "Shortest distance from London to Rome: #{path.weight}"
IO.inspect(path.nodes, label: "Route")

A* (Heuristic Search)

A* uses a heuristic to “guide” the search towards the goal, making it much faster for coordinate-based graphs.

# Create a small grid graph
grid = Yog.Builder.GridGraph.new(5, 5)
graph = Yog.Builder.GridGraph.to_graph(grid)

# Manhattan distance heuristic
heuristic = fn node, goal ->
  {r1, c1} = Yog.Builder.GridGraph.id_to_coord(grid, node)
  {r2, c2} = Yog.Builder.GridGraph.id_to_coord(grid, goal)
  abs(r1 - r2) + abs(c1 - c2)
end

start = Yog.Builder.GridGraph.coord_to_id(grid, 0, 0)
goal = Yog.Builder.GridGraph.coord_to_id(grid, 4, 4)

{:ok, path} = Yog.Pathfinding.a_star(in: graph, from: start, to: goal, heuristic: heuristic)

IO.puts "A* path length: #{path.weight}"
IO.inspect(path.nodes, label: "Path nodes")

Bellman-Ford (Negative Weights)

Dijkstra fails with negative edge weights. Bellman-Ford handles them correctly.

# A graph with a negative edge
g = Yog.from_edges(:directed, [
    {:s, :a, 5},
    {:s, :b, 4},
    {:a, :c, 3},
    {:b, :a, -6},  # Negative edge!
    {:c, :b, 2}
  ])

{:ok, distances} = Yog.Pathfinding.BellmanFord.shortest_path(in: g, from: :s)
IO.inspect(distances, label: "Shortest distances from S")

All-Pairs Shortest Paths (Floyd-Warshall)

Sometimes you need to know the distance between every possible pair of nodes. Floyd-Warshall is the classic solution for this.

g = Yog.from_edges(:directed, [
    {1, 2, 3}, {2, 3, 2}, {1, 3, 10}
  ])

# Returns a nested map %{from => %{to => distance}}
{:ok, distances} = Yog.Pathfinding.floyd_warshall(in: g)

IO.inspect(distances[1][3], label: "Distance from 1 to 3")
IO.inspect(distances[2][1], label: "Distance from 2 to 1 (no path = :infinity)")

Visualizing the Result

Let’s combine everything: find a path and visualize it using Kino.VizJS.

g = Yog.from_edges(:undirected, [
    {:a, :b, 1}, {:b, :c, 2}, {:c, :d, 1},
    {:a, :c, 5}, {:b, :d, 10}
  ])

{:ok, path} = Yog.Pathfinding.shortest_path(in: g, from: :a, to: :d)

path_options = Yog.Render.DOT.path_to_options(path)

# Highlight path nodes in the DOT output
dot = Yog.Render.DOT.to_dot(g, path_options)

Kino.VizJS.render(dot)

Summary

Yog covers all your traversal and pathfinding needs:

1. Linear traversals (BFS/DFS) for structure exploration.
2. Structural sorting (Topological Sort) for DAGs.
3. Weighted pathfinding (Dijkstra, A*, Bellman-Ford).
4. All-pairs distance (Floyd-Warshall, Johnson’s).

Next, try exploring Community Detection to see how nodes group together!