California Road Network Analysis with Zog ⚡

Mix.install([
  # {:zog, "~> 0.6.0"},
  {:zog, path: Path.expand("~/repos/elixir/zog")},
  {:kino, "~> 0.12"}
])

1. Overview & Data Ingestion

In this notebook, we analyze the California Road Network dataset from the Stanford Network Analysis Project (SNAP). This real-world transport network contains 1,965,206 intersections (nodes) and 5,533,214 roads (edges).

First, let's download and decompress the dataset:

{:ok, txt_path} = Zog.Dataset.fetch_snap(:ca_roads)

Kino.Markdown.new("""
> **Dataset Ready**: `#{txt_path}` (~18 MB uncompressed edge list).
""")

2. Zero-Copy Ingestion: The ResourceGraph Pattern

In traditional BEAM graph libraries, loading 2 million nodes and 5.5 million edges into Elixir maps or tuples consumes 1.5–2 GB of heap memory and triggers frequent Garbage Collection (GC) pauses.

With Zog:

1. Direct Native Parsing: The edge list is parsed directly in Zig (ArrayGraph SoA layout).
2. BEAM Heap Isolation: The graph is stored in native C-allocator memory outside the Erlang process heap.
3. Integer Labels: With integer_labels: true, node IDs map directly to contiguous u32 array indices.

alias Zog.IO, as: ZogIO
alias Zog.ResourceGraph

# Track BEAM memory before loading
beam_mem_before = :erlang.memory(:total)

{time_load_micro, graph} = :timer.tc(fn -> 
  ZogIO.load(txt_path, directed: false, integer_labels: true)
end)

beam_mem_after = :erlang.memory(:total)
beam_mem_delta_mb = (beam_mem_after - beam_mem_before) / (1024 * 1024)
load_seconds = time_load_micro / 1_000_000

node_count = ResourceGraph.node_count(graph)
edge_count = ResourceGraph.edge_count(graph)
undirected_edges = div(edge_count, 2)
exact_status = fn actual, expected ->
  if actual == expected, do: "✓ Exact Match", else: "⚠ Expected #{expected}"
end

Kino.Markdown.new("""
### ⚡ Graph Ingestion Summary
- **Nodes (Intersections)**: `#{node_count}` *(#{exact_status.(node_count, 1_965_206)})*
- **Undirected Edges**: `#{undirected_edges}` *(#{exact_status.(undirected_edges, 2_766_607)})*
- **Directed Half-Edges**: `#{edge_count}`
- **Native Load Time**: **#{Float.round(load_seconds, 2)} seconds**
- **BEAM Heap Growth**: **#{Float.round(beam_mem_delta_mb, 2)} MB** *(virtually zero heap footprint!)*
""")

3. Weakly Connected Components (WCC)

Is the California road network fully connected, or are there isolated components (such as private roads or islands)? Let's compute connected components in native memory using raw: true to return flat integer labels:

{time_wcc_micro, wcc_assignments} = :timer.tc(fn -> 
  ResourceGraph.weakly_connected_components(graph, raw: true) 
end)

wcc_seconds = time_wcc_micro / 1_000_000
frequencies = Enum.frequencies(wcc_assignments)
num_components = map_size(frequencies)

# Sort top 10 largest components
top_components =
  frequencies
  |> Enum.sort_by(fn {_, count} -> count end, :desc)
  |> Enum.take(10)
  |> Enum.with_index(1)
  |> Enum.map(fn {{comp_id, count}, rank} ->
    %{
      "Rank" => rank,
      "Component ID" => comp_id,
      "Intersections" => count,
      "% of Network" => "#{Float.round(count / node_count * 100, 2)}%"
    }
  end)

Kino.Layout.grid([
  Kino.Markdown.new("""
  **WCC Execution Time**: `#{Float.round(wcc_seconds, 3)}s`  
  **Total Components Found**: `#{num_components}`
  """),
  Kino.DataTable.new(top_components, name: "Largest Connected Components")
], columns: 1)

4. Interactive Route Planning (Dijkstra)

Because the graph is already cached in native memory, shortest-path queries execute in milliseconds.

Use the controls below to select any two intersection IDs (from 0 to 1,965,205) to route across California:

start_input = Kino.Input.number("Start Intersection ID", default: 0)
goal_input = Kino.Input.number("Destination Intersection ID", default: 100_000)

Kino.Layout.grid([start_input, goal_input], columns: 2)

start_value = Kino.Input.read(start_input)
goal_value = Kino.Input.read(goal_input)
whole_number? = fn value -> is_integer(value) or (is_float(value) and value == trunc(value)) end

cond do
  not whole_number?.(start_value) or not whole_number?.(goal_value) ->
    Kino.Markdown.new("⚠️ Please enter whole-number intersection IDs.")

  start_value < 0 or start_value >= node_count or goal_value < 0 or goal_value >= node_count ->
    Kino.Markdown.new("⚠️ Please enter intersection IDs between `0` and `#{node_count - 1}`.")

  true ->
    start_node = trunc(start_value)
    goal_node = trunc(goal_value)

    {time_dijkstra_micro, result} =
      :timer.tc(fn ->
        ResourceGraph.dijkstra(graph, start_node, goal_node, raw: true)
      end)

    case result do
      {:ok, {path, total_hops}} ->
        route_rows =
          path
          |> Enum.with_index()
          |> Enum.take(20)
          |> Enum.map(fn {node_id, step} ->
            %{"Step" => step, "Intersection ID" => node_id}
          end)

        Kino.Layout.grid(
          [
            Kino.Markdown.new("""
            ### ✅ Route Found!
            - **Query Time**: **#{Float.round(time_dijkstra_micro / 1_000, 2)} ms**
            - **Total Hops (Road Segments)**: **#{total_hops}**
            - **Total Route Nodes**: `#{length(path)}`
            """),
            Kino.DataTable.new(route_rows, name: "First 20 Intersections on Route")
          ],
          columns: 1
        )

      {:error, :no_path} ->
        Kino.Markdown.new("""
        > ⚠️ **No Path**: Node `#{start_node}` and Node `#{goal_node}` belong to disconnected components!
        """)
    end
end

5. Identifying Highway Hubs (Centrality Analysis)

Which intersections are the most critical transit hubs in California? We can run PageRank directly across all 2 million nodes in native memory to discover the highest-flow intersections:

{time_pr_micro, pr_scores} = :timer.tc(fn ->
  ResourceGraph.pagerank(graph, raw: true, max_iterations: 25)
end)

top_hubs =
  pr_scores
  |> Stream.with_index()
  |> Enum.sort_by(fn {score, _node_id} -> score end, :desc)
  |> Enum.take(10)
  |> Enum.with_index(1)
  |> Enum.map(fn {{score, node_id}, rank} ->
    %{
      "Rank" => rank,
      "Intersection ID" => node_id,
      "PageRank Score" => Float.round(score, 6)
    }
  end)

Kino.Layout.grid([
  Kino.Markdown.new("""
  **PageRank Runtime**: `#{Float.round(time_pr_micro / 1_000_000, 2)}s` (25 iterations across 2M nodes)
  """),
  Kino.DataTable.new(top_hubs, name: "Top 10 California Transit Hubs")
], columns: 1)

6. Regional Partitioning (Community Detection)

Road networks naturally cluster into geographic and metropolitan regions. Using Label Propagation, we can partition the entire state of California into regional transit zones in under a few seconds:

{time_lpa_micro, communities} = :timer.tc(fn ->
  ResourceGraph.label_propagation(graph, raw: true, max_iterations: 20)
end)

comm_sizes =
  communities
  |> Enum.frequencies()
  |> Enum.sort_by(fn {_, count} -> count end, :desc)
  |> Enum.take(10)
  |> Enum.with_index(1)
  |> Enum.map(fn {{comm_id, count}, rank} ->
    %{
      "Rank" => rank,
      "Community Zone ID" => comm_id,
      "Intersections" => count,
      "% of California" => "#{Float.round(count / node_count * 100, 2)}%"
    }
  end)

Kino.Layout.grid([
  Kino.Markdown.new("""
  **Label Propagation Runtime**: `#{Float.round(time_lpa_micro / 1_000_000, 2)}s`  
  **Total Regional Communities**: `#{map_size(Enum.frequencies(communities))}`
  """),
  Kino.DataTable.new(comm_sizes, name: "Top 10 Largest Regional Zones")
], columns: 1)

7. Triangle Counting (Local Triadic Closure)

In social networks, friends of friends are usually friends, producing massive numbers of triangles. In planar road networks, right angles and grid intersections dominate, so 3-cycles (triangles) are relatively sparse:

{time_tri_micro, triangles} = :timer.tc(fn -> 
  ResourceGraph.triangle_count(graph) 
end)

Kino.Markdown.new("""
### 📐 Triangle Count
- **Triangles Found**: **#{triangles}** *(#{exact_status.(triangles, 120_676)})*
- **Calculation Time**: **#{Float.round(time_tri_micro / 1_000_000, 3)}s**
""")

8. Clean Up Native Memory

Always free native resources when your analysis session is finished:

ResourceGraph.destroy(graph)

Kino.Markdown.new("""
> ✨ **Cleanup Complete**: Native memory allocated for the 2M-node graph has been safely released back to the OS.
""")