README
¶
Example 12 — Build-dependency order and cycle detection
What it demonstrates
Modelling a software build-dependency graph as a directed graph, deriving
a valid build order with search.TopologicalSort (Kahn's algorithm) and
verifying it against the topological-order validity invariant, then
detecting a circular dependency with search.TarjanSCC after a back-edge
is injected.
Domain / scenario
A realistic, seeded, scale-parametrised module dependency graph. Each
directed edge (a, b) reads "a depends on b", so b must be built
before a. Modules are partitioned into -layers layers and a module in
layer k draws a few distinct dependencies from layers strictly below it
([0, k)). Layer 0 modules are leaves — the foundation libraries with no
dependencies. The strict layering is what guarantees acyclicity: along any
dependency path the layer index strictly decreases, so no directed cycle
can form and TopologicalSort always succeeds.
The layer widths follow a pyramid (widest at the leaves, controlled by
-pyramid-base), apportioned with a floor pass so every layer is
non-empty and the per-layer counts sum exactly to -modules. A single
dependency chain is planted from the top layer down to layer 0, so the
graph always has a known longest chain and a known forward path to close
into a cycle.
The first stage derives the build order for this acyclic graph and
verifies it. The second stage injects a back-edge from the bottom of the
planted chain to its top, closing a circular dependency; TopologicalSort
then fails with ErrCycle, and TarjanSCC reports the single strongly
connected component that contains the cycle.
How to run
go run ./examples/12_build_dependency # small deterministic default
go run ./examples/12_build_dependency -modules 1000000 -layers 40 -seed 7 # observable-scale run
Scale and flags
| Flag | Meaning | Default | Large example |
|---|---|---|---|
-modules |
number of module nodes | 5000 |
1000000 |
-layers |
number of dependency layers (>= 2) |
12 |
40 |
-deps-min |
minimum dependencies a non-leaf module requests | 1 |
1 |
-deps-max |
maximum dependencies a non-leaf module requests | 5 |
8 |
-pyramid-base |
layer-width growth toward the leaves (>= 1) |
1.6 |
2.0 |
-seed |
RNG seed (fixes the deterministic data shape) | 1 |
7 |
-modules must be at least -layers so every layer holds at least one
module; the configuration is rejected otherwise, once, at the boundary.
Expected output
config.modules=5000
config.layers=12
config.deps=[1,5]
config.seed=1
nodes.modules=5000
edges.dependencies=9265
dag.layers=12
topo.order_valid=true
topo.modules_ordered=4927
dag.longest_chain=12
cycle.detected=true
cycle.scc_count=1
cycle.scc_size=14
The bare lines above are the deterministic facts the regression test
pins for the default seed. Interleaved with them, the program also prints
volatile telemetry prefixed with # , which varies per run and per
machine:
# build.elapsed=2.69ms
# build.node_rate=1858592 nodes/s
# topo.elapsed=108µs
# tarjan.elapsed=215µs
# mem.heap_alloc=1.25 MiB
topo.modules_ordered is below nodes.modules because TopologicalSort
omits modules that have no edges (leaves that nothing depends on).
cycle.scc_size is reported empirically rather than predicted: the
injected back-edge always closes the planted chain (>= layers modules),
but the resulting strongly connected component may absorb a few extra
modules whenever a random edge created a second forward path between two
chain modules. It is reproducible for a fixed seed.
Evidence it collects
From the graph structures / search dimension of the evidence taxonomy:
- Wall-clock per algorithm —
# topo.elapsedand# tarjan.elapsedisolateTopologicalSortandTarjanSCCfrom generation cost. - DAG statistics — nodes, edges, layers, and the longest dependency
chain (
dag.longest_chain), which is the build's critical-path depth. - Build throughput and live heap —
# build.*_rateand# mem.*.
When scaling up, watch the two algorithm latencies grow roughly linearly
in V + E while generation stays the dominant cost, and watch
dag.longest_chain track -layers.
Key APIs
graph/adjlist.New/AdjList.AddEdge/AdjList.AddNode— build the mutable directed dependency graph.graph/adjlist.AdjList.Mapper/graph.Mapper.Lookup/graph.Mapper.Resolve— translate between module names and compactNodeIDs.graph/csr.BuildFromAdjList— freeze the builder into an immutable CSR snapshot for analytics.search.TopologicalSortCtx/search.ErrCycle— derive a build order, or fail when the graph has a cycle.search.TarjanSCCCtx— find the strongly connected components; a component of size > 1 is a cycle.
Further reading
search— traversal and path-finding package documentationgraph/csr— the immutable CSR snapshot used as the query surfacegraph/adjlist— the mutable adjacency-list builder- Example 01 — Basic shortest paths — the minimal build → snapshot → query flow
- Example 26 — Social-scale benchmark — the reference end state for the examples standard
- docs/examples-standard.md — the standard every example follows
Documentation
¶
Overview ¶
Example 12_build_dependency — model a software build-dependency graph, derive a valid build order with search.TopologicalSort (Kahn's algorithm), and detect a circular dependency with search.TarjanSCC.
It generates a realistic, seeded, scale-parametrised build graph: a layered module DAG in which every module depends on a few modules in strictly lower layers. That layering is what guarantees acyclicity — along any dependency path the layer index strictly decreases, so no directed cycle can form and TopologicalSort always succeeds. The example then exercises the two algorithms it teaches and reports both the deterministic shape of the data and the volatile telemetry — wall-clock and live heap — that make it a benchmark rather than a demonstration.
Model ¶
module mNNNN // one node per module (a)-[depends-on]->(b) // edge a->b: a depends on b
Edge direction reads "a depends on b", so b must be built before a. Modules are partitioned into L layers; a module in layer k draws a few distinct dependencies from layers strictly below it ([0, k)). Layer 0 modules are leaves (no dependencies — the foundation libraries). The layer widths follow a pyramid (widest at the leaves), apportioned with a floor pass so every layer is non-empty and the counts sum exactly to the requested module total. A single dependency chain is planted from the top layer down to layer 0 so the graph always has a known longest chain and a known forward path to close into a cycle.
Two stages ¶
Build order. The DAG is frozen into a CSR snapshot and sorted with search.TopologicalSort. The result is verified in-code against the validity invariant — for every edge u->v the source precedes the destination in the order — and the build order (dependencies first) is the reverse of that linear extension. The longest dependency chain (the build's critical-path depth) is computed by a linear-time DP over the topological order.
Cycle detection. A back-edge from the bottom of the planted chain to its top is injected, closing a circular dependency. search.TopologicalSort then fails with search.ErrCycle, and search.TarjanSCC reports the single strongly connected component that contains the cycle. Because the input was a DAG (whose every SCC is a singleton), the injected back-edge produces exactly one component of size greater than one, and that component contains both endpoints of the back-edge.
Scale ¶
Run with no flags, the example builds a small deterministic default (a few thousand modules) that the regression test pins. Every dimension is a flag, so the same binary scales up to where the algorithms' cost is observable:
go run ./examples/12_build_dependency -modules 1000000 -layers 40 -seed 7
The deterministic data shape is reproducible for a fixed -seed; only the telemetry (lines prefixed with "# ") varies between runs and machines.
Why CSR ¶
TopologicalSort and TarjanSCC are read-only analytics, so the graph is built once in a mutable adjlist.AdjList and then frozen into an immutable csr.CSR snapshot — the lock-free, cache-friendly surface the search package runs against. This is the canonical build -> snapshot -> query flow; persistence is orthogonal to what this example measures and is demonstrated by examples 04, 17, 24 and 25.
Source Files