Documentation
¶
Overview ¶
Package scc provides a parallel FW–BW SCC condensation for directed graphs, adapted for Baton’s entitlement graph. It builds an immutable CSR + transpose, runs reachability-based SCC (with parallel BFS and parallel recursion), and returns components as groups of your original node IDs.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func CondenseFWBWGroupsFromAdj ¶
CondenseFWBWGroupsFromAdj runs parallel FW–BW SCC on adj and returns only the component groups as slices of original node IDs. This avoids building the idToComp map when callers don't need it.
Types ¶
type CSR ¶
type CSR struct {
N int
Row []int // len N+1
Col []int // len = m
TRow []int // len N+1
TCol []int // len = m
IdxToNodeID []int
NodeIDToIdx map[int]int
}
CSR is a compact adjacency for G and its transpose Gᵗ. Indices are 0..N-1; IdxToNodeID maps back to the original node IDs.
type Options ¶
type Options struct {
// MaxWorkers bounds concurrency for BFS/recursion. Defaults to GOMAXPROCS.
MaxWorkers int
// EnableTrim peels vertices with min(in,out)==0 before FW–BW (usually beneficial).
EnableTrim bool
// SmallCutoff size below which we switch to a simpler (sequential) routine.
// You can later swap this to Tarjan for tiny subgraphs.
SmallCutoff int
// Deterministic maps node IDs to CSR indices in sorted order (recommended).
Deterministic bool
}
Options controls parallel SCC execution.
Source Files
Click to show internal directories.
Click to hide internal directories.