scc

type CSR ¶

type CSR struct {
	N           int
	Row         []int // len N+1
	Col         []int // len = m, m = Row[N]
	TRow        []int // len N+1
	TCol        []int // len = m, m = TRow[N]
	IdxToNodeID []int // len N
}

CSR is a compact adjacency for G and its transpose Gᵗ. Indices are 0..N-1; IdxToNodeID maps back to the original node IDs.

Invariants (validated by validateCSR):

• len(Row) == N+1; Row[0] == 0; Row is non-decreasing; Row[N] == len(Col)
• len(TRow) == N+1; TRow[0] == 0; TRow is non-decreasing; TRow[N] == len(TCol)
• 0 <= Col[p] < N for all p; 0 <= TCol[p] < N for all p
• len(IdxToNodeID) == N; NodeIDToIdx[IdxToNodeID[i]] == i for all i
• For each v, (TRow[v+1]-TRow[v]) equals the number of occurrences of v in Col (transpose degree matches inbound counts)

type Metrics ¶ added in v0.3.51

type Metrics struct {
	Nodes          int
	Edges          int
	Components     int
	Peeled         int
	MasksProcessed int
	MasksPushed    int
	BFScalls       int
	Duration       time.Duration
	MaxWorkers     int
	Deterministic  bool
}

Metrics captures a few summary counters for a condense run.

func CondenseFWBW(ctx context.Context, src Source, opts Options) ([][]int, *Metrics)

type Options ¶

type Options struct {
	MaxWorkers    int
	Deterministic bool
}

Options controls SCC execution.

MaxWorkers bounds BFS concurrency per level. Deterministic toggles stable CSR index assignment and neighbor ordering.

func DefaultOptions() Options

type Source ¶ added in v0.3.51

type Source interface {
	ForEachNode(fn func(id int) bool)
	ForEachEdgeFrom(src int, fn func(dst int) bool)
}

Source is a minimal read-only graph provider used to build CSR without materializing an intermediate adjacency map. It must enumerate all nodes (including isolated nodes) and for each node provide its unique outgoing destinations.