Method sccs

analysis/stratification.go:136–180

()

type Nodeset map[ast.PredicateSym]struct{}

func (dep depGraph) sccs() []Nodeset {
	// Kosaraju's algorithm
	// Forward pass.
	S := make(nodelist, 0, len(dep)) // postorder stack
	seen := make(Nodeset)
	var visit func(node ast.PredicateSym)
	visit = func(node ast.PredicateSym) {
		if _, ok := seen[node]; !ok {
			seen[node] = struct{}{}
			for e := range dep[node] {
				visit(e)
			}
			S = append(S, node)
		}
	}
	for node := range dep {
		visit(node)
	}

	// Reverse pass.
	rev := dep.transpose()
	var scc Nodeset
	seen = make(Nodeset)
	var rvisit func(node ast.PredicateSym)
	rvisit = func(node ast.PredicateSym) {
		if _, ok := seen[node]; !ok {
			seen[node] = struct{}{}
			scc[node] = struct{}{}
			for e := range rev[node] {
				rvisit(e)
			}
		}
	}
	var sccs []Nodeset
	for len(S) > 0 {
		top := S[len(S)-1]
		S = S[:len(S)-1] // pop
		if _, ok := seen[top]; !ok {
			scc = make(Nodeset)
			rvisit(top)
			sccs = append(sccs, scc)
		}
	}
	return sccs
}

// sortResult sorts the strata topologically (ignoring cycles).
func (dep depGraph) sortResult(strata []Nodeset, predToStratumMap map[ast.PredicateSym]int) ([]Nodeset, map[ast.PredicateSym]int) {