graph
import "github.com/umbralcalc/stochadex/pkg/graph"Package graph derives the partition dependency graph of a stochadex simulation statically from its configuration, before any step runs.
It exists to answer two questions cheaply and deterministically:
- Will this simulation deadlock? A cycle in the within-step params_from_upstream wiring makes the coordinator’s per-partition goroutines block on each other’s channels forever. InjectCycles finds those cycles up front so a silent hang becomes a clear error.
- What depends on what? Build produces the full dependency graph for documentation and visualisation (see Mermaid / DOT).
Reliability: one edge class is exact, two are hints
The three edge kinds do not have the same relationship to config, and the difference is load-bearing:
- ParamsInject (from params_from_upstream) is engine-enforced wiring. The coordinator builds a channel the consumer blocks on receiving before its Iterate even runs, so the dependency exists whether or not the iteration reads the injected param. These edges are exact — sound and complete — and are the only ones safe to assert on.
- CrossHistory (from params_as_partitions) is declared capacity, not wiring. The actual read lives in iteration code, which config cannot see. It over-reports (a configured partition ref the iteration ignores) and under-reports (a cross-read whose index comes from a plain numeric param or a hard-coded literal, with no params_as_partitions entry). Treat it as a may-read hint for visualisation; do not assert on it.
Self-dependencies are not represented as edges at all: every partition is assumed to read its own state history each step, so a self edge would be universal noise. A partition’s history depth is a property of the node, not a relationship worth drawing.
The graph is built from a ConfigGenerator, not a Settings, because params_as_partitions is flattened into anonymous float params by GenerateConfigs and is unrecoverable afterwards.
Index
type Edge
Edge is a directed dependency: the Target partition depends on the Source.
type Edge struct {
Source, Target int
// SourceName and TargetName are the partition names for the indices above.
SourceName, TargetName string
Kind EdgeKind
// Param is the param key that carries the dependency (the params_from_upstream
// or params_as_partitions key).
Param string
// Window is the maximum readable lag: the source partition's state history
// depth for a CrossHistory edge, 0 for a within-step ParamsInject edge.
Window int
}type EdgeKind
EdgeKind distinguishes the three dependency types between partitions.
type EdgeKind intconst (
// ParamsInject is a within-step dependency declared by params_from_upstream:
// the source's this-step output is piped into the target's params before the
// target iterates. It imposes a computation order and deadlocks if cyclic.
ParamsInject EdgeKind = iota
// CrossHistory is a lag>=1 dependency declared by params_as_partitions: the
// target may read the source partition's previous-step state history.
CrossHistory
)func (EdgeKind) Reliable
func (k EdgeKind) Reliable() boolReliable reports whether this edge kind is derived from engine-enforced wiring (exact) rather than declared capacity (a may-read hint). Only ParamsInject edges are reliable, and only they should be asserted on.
func (EdgeKind) String
func (k EdgeKind) String() stringString returns a stable snake_case label for the edge kind.
type Graph
Graph is the dependency graph of a simulation: partition names in index order plus the derived edges. It is a pure function of the configuration.
type Graph struct {
Names []string
Edges []Edge
}func Build
func Build(gen *simulator.ConfigGenerator) *GraphBuild derives the dependency graph from a ConfigGenerator. It is deterministic — edges are emitted in a stable order (by target index, then kind, then sorted param key) — and performs no simulation run.
func (*Graph) DOT
func (g *Graph) DOT() stringDOT renders the graph in Graphviz DOT for users who want a rendered image (stochadex-graph --format dot … | dot -Tsvg). CrossHistory reads of past state render as differently coloured past-copy nodes, exactly as in Mermaid, so the drawn graph is a DAG (see the Mermaid doc for the rationale).
func (*Graph) HasDeadlock
func (g *Graph) HasDeadlock() boolHasDeadlock reports whether the ParamsInject subgraph contains any cycle, i.e. whether the simulation would deadlock under channel-based execution.
func (*Graph) InjectCycles
func (g *Graph) InjectCycles() [][]intInjectCycles returns the cyclic strongly-connected components of the ParamsInject subgraph, each as a sorted slice of partition indices. A non-empty result means the simulation will deadlock under the default and persistent-worker execution strategies: the within-step params channels form a receive cycle in which no partition can produce the value another is blocked waiting for.
Only ParamsInject edges are considered. A dependency cycle that routes through a lag edge (a CrossHistory read, or a partition’s assumed read of its own history) is safe — the lag consumer reads the previous step’s committed value — and is the documented cycle-breaking pattern, so it is intentionally excluded.
func (*Graph) Mermaid
func (g *Graph) Mermaid() stringMermaid renders the graph as a Mermaid flowchart. Mermaid is chosen as the default because it renders inline in GitHub-flavoured markdown (e.g. a model card) with no external tooling.
Edge styling encodes the reliability distinction from the package doc:
- solid arrow (-->) : ParamsInject, the exact within-step wiring.
- dashed arrow (-.->) : CrossHistory, the may-read hint.
CrossHistory dependencies are reads of a partition’s *past* committed state, not of its live within-step output. So that the rendered graph stays a DAG, such an edge does not point back at the live producer node; instead each producer read this way gets a distinct, differently coloured past-copy node bearing the same name, and the lag edge originates there. Unrolling the one-step lag into its own node means a safe mutual-lag cycle (the documented cycle-breaking pattern) no longer draws as a cycle — only a genuine within-step deadlock does, and those partitions are highlighted so the hazard is visible at a glance.
Self-dependencies are assumed universal and not drawn (see package doc).
Generated by gomarkdoc