Documentation
¶
Overview ¶
Package graph provides Go-side fast paths for graph algorithms used by the (wile algebra graph) Scheme library.
The kernels here are pure Go and operate on integer-indexed nodes. The Scheme library is responsible for translating between Scheme node identifiers (any equal?-comparable value) and integer indices.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func CondenseSCC ¶
CondenseSCC reduces a directed graph to its DAG of strongly-connected components. Returns the SCC decomposition and the edge list of the condensed graph.
For each original edge (u, v) where SCC[u] != SCC[v], emits the condensed edge (SCC[u], SCC[v]). Within-SCC edges (SCC[u] == SCC[v]) are dropped — by construction the condensed graph is acyclic.
Multi-edges in the condensation are preserved: if two distinct original edges (u1, v1) and (u2, v2) both satisfy SCC[u1]==SCC[u2]==c and SCC[v1]==SCC[v2]==d with c != d, both emit a condensed edge (c, d). They contribute two distinct inter-SCC paths and downstream path counting must reflect that.
Returns (nil, nil, err) if ComputeSCC fails (input validation failure).
func CountPathsInDAG ¶
CountPathsInDAG computes the number of distinct paths from `source` to each node in a directed acyclic graph. Returns a slice indexed by node, where counts[v] is the number of paths from source to v as a *big.Int. Nodes unreachable from source have count 0.
Returns nil if the subgraph reachable from `source` contains a cycle. Cycles unreachable from `source` are ignored.
Algorithm: DFS from source produces a reverse-postorder, which is a valid topological order of the reachable subgraph. Cycle detection via gray-state tracking. Counts are then propagated in topological order with a single forward pass — each reachable edge relaxed exactly once. The per-edge step is the monotone in-place addition (`counts[v].Add(counts[v], counts[u])`), which is the kernel that future Σ-semiring DAG variants will inherit.
Why topological order and not worklist Bellman-Ford: the counting semiring's + is not idempotent. A worklist that re-propagates a node's full current count when the node is re-popped over-counts (the node's count grows monotonically as predecessors settle, and each pop sends the full new value forward — adding to whatever was already sent). Topological-order processing visits each node exactly once after its count has settled.
Types ¶
type CyclicCountResult ¶
type CyclicCountResult struct {
*SCCResult
// CountsBySCC[c] is the number of distinct paths in the condensed
// DAG from SCC[source] to SCC c. Semantics by SCC kind:
//
// Trivial SCC (NonTrivial[c] == false): single node, no within-SCC
// paths. CountsBySCC[c] is the exact number of paths from
// source to that node in the original graph.
//
// Non-trivial SCC (NonTrivial[c] == true): contains a cycle.
// Within-SCC path counts are infinite, so CountsBySCC[c] is the
// "entry count" — the number of distinct paths from SCC[source]
// that reach this SCC via some entry point in the condensed
// DAG. Callers should propagate the NonTrivial flag so users
// understand the semantic shift.
CountsBySCC []*big.Int
}
CyclicCountResult is the result of CountPathsCyclic. Unlike CountPathsInDAG which returns counts indexed by node, this returns counts indexed by SCC plus the SCC map (via the embedded *SCCResult) so callers can project back to per-node answers.
The embedded *SCCResult gives `result.SCC`, `result.NumSCCs`, and `result.NonTrivial` directly (promoted fields). All three exported slices (SCC, NonTrivial, CountsBySCC) alias kernel-internal storage — callers MUST treat them as read-only. Mutation will silently corrupt any downstream computation that re-reads them.
func CountPathsCyclic ¶
func CountPathsCyclic(numNodes int, edges []Edge, source int) (*CyclicCountResult, error)
CountPathsCyclic computes path counts on an arbitrary directed graph by SCC-condensing it and running the monotone kernel on the resulting DAG. Returns counts per SCC, not per node. For acyclic input this is equivalent to CountPathsInDAG with one extra SCC pass of overhead; callers that know their input is acyclic should prefer CountPathsInDAG directly.
Returns ErrInvalidArgument if numNodes <= 0, source is out of range, or any edge references an out-of-range node.
type Edge ¶
type Edge struct {
U, V int
}
Edge represents a directed edge from U to V with unit weight (for path counting). Multiple edges between the same pair of nodes are allowed and each contributes a distinct path.
type SCCResult ¶
type SCCResult struct {
// SCC[v] is the component ID of node v. 0 <= SCC[v] < NumSCCs.
SCC []int
// NumSCCs is the number of distinct components.
NumSCCs int
// NonTrivial[c] is true iff component c contains a cycle: either
// it has more than one node, or it is a single node with a
// self-loop. A trivial SCC is a single node with no self-loop.
NonTrivial []bool
}
SCCResult describes the strongly-connected-component decomposition of a directed graph. Components are numbered 0..NumSCCs-1 in reverse topological order of the condensation: SCC 0 has no incoming inter-SCC edges (a "root" in the condensation); SCC NumSCCs-1 has no outgoing inter-SCC edges (a "leaf"). Equivalently, for every condensed edge (c, d) with c != d, c < d.
The exported slices (SCC, NonTrivial) alias kernel-internal storage — callers MUST treat them as read-only. Mutation will silently corrupt any downstream computation that re-reads them (CondenseSCC, CountPathsCyclic).
Source Files