10_dimacs9_routing

Example 10 — DIMACS 9 routing

What it demonstrates

Building a synthetic road-network graph with the DIMACS 9 benchmark harness, freezing it into an immutable CSR snapshot, and running a concrete single-source shortest-paths query (search.Dijkstra) over it. It reads back the shortest distance and reconstructs the route, then prints an environment-dependent latency summary from the harness.

Domain / scenario

A small synthetic road network generated by dimacs9.Synthetic. Every vertex points to its next-numbered neighbours with int64 edge weights derived deterministically from the endpoint indices, so the graph — and therefore every shortest path over it — is identical on every run. The fixed inputs (vertices = 12, edges = 30) yield a 12-node, 24-edge directed graph (average out-degree 2). The query is anchored at node 0 and routed to node 11; the shortest route is the multi-hop path 0 -> 1 -> 2 -> 3 -> 11 (hop weights 1 + 20 + 39 + 95 = 155), not a single direct edge.

How to run

go run ./examples/10_dimacs9_routing

Expected output

The graph size, path, and distance are deterministic. The latency lines (p50/p95/p99) are wall-clock measurements and vary from run to run and machine to machine — a representative run looks like:

Graph:  12 nodes, 24 edges
SSSP:   node 0 -> node 11
  distance: 155
  path:     0 -> 1 -> 2 -> 3 -> 11
Latency (environment-dependent, not a regression baseline):
  p50: 1.041µs
  p95: 1.5µs
  p99: 2.083µs

Key APIs

• bench/dimacs9.Synthetic — generate the deterministic synthetic road-network adjacency list.
• bench/dimacs9.Run / bench/dimacs9.Report.Percentile — run the query workload and read back latency percentiles.
• graph/csr.BuildFromAdjList — freeze the builder into an immutable CSR snapshot; CSR.Order / CSR.Size report the node and edge counts.
• graph/adjlist.AdjList.Mapper — translate between node values and compact NodeIDs (Lookup, Resolve).
• search.Dijkstra — single-source shortest paths over non-negative weights.
• search.Distances.Distance / search.Distances.Path — read back the cost and reconstruct the route.

Further reading

• bench/dimacs9 — the DIMACS 9 benchmark harness
• search — traversal and path-finding package documentation
• graph/csr — the immutable CSR snapshot used as the query surface
• Example 01 — basic shortest paths — the minimal Dijkstra flow this example builds on
• docs/examples-standard.md — the standard every example follows