Fixpoint3.PrecedenceGraph
PrecedenceGraph contains a graph module which is used to compute a stratification
of a Datalog program. The stratification is based on a topological sort
of the strongly connected components (SCC) of the precedence graph.
The topological sort describes is a legal stratification of the Datalog program.
A PseudoStratum is a group of mutually independent, consecutive strata, each
represented by a unique SCC in the topological order.
Type Aliases
type alias PseudoStratum = List[Set[Vertex]]
SourceA PseudoStratum is an unordered list of strata without dependencies between them.
type alias Vertex = Int32
SourceDefinitions
def getPseudoStrata(g: MutGraph[r]): List[PseudoStratum] \ r
SourceReturns a list of the pseudostrata of g.
For example, the graph given by the edges
1 -> 2
2 -> 3
3 -> 2
4 -> 3
would produce three SCCs: {2, 3}, {1}, and {4}. A topological sort of the
condensation graph gives the ordering [{1}, {4}, {2, 3}]. Since the components
{1} and {4} have no dependencies between them and are adjacent in the ordering,
they are merged into the same pseudostratum [{1}, {4}]. Thus, the list of
pseudostrata is [[{1}, {4}], {2, 3}].