Class StronglyConnectedComponents
LockPrecedenceGraph and is what FE77's
construction-recursion check (E08263) runs on.
Iterative, deliberately. A recursive Tarjan uses one Java frame per node on the deepest path, so a long enough chain of calls or constructions in the program being compiled would overflow the COMPILER's stack.
Successors are asked for lazily, once per node and only for nodes reached from a root. A caller can therefore describe a graph that is never built in full - FE77 materialises each generic parameterisation's construction steps only when a path reaches them.
Self-loops are kept. A single node that calls itself is a cycle (StronglyConnectedComponents.Component.cyclic()); copies
that only reported components of two or more nodes could not see a constructor that constructs its own type.
Nodes must have value equality. The order of the components follows the order of the roots and of each successor collection, so a caller that reports on them should sort what it reports.
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionstatic final recordOne strongly connected component. -
Method Summary
Modifier and TypeMethodDescriptionstatic <N> List<StronglyConnectedComponents.Component<N>> cyclesOf(Collection<N> roots, Function<N, ? extends Collection<N>> successors) Only the components that are cycles.static <N> List<StronglyConnectedComponents.Component<N>> of(Collection<N> roots, Function<N, ? extends Collection<N>> successors) Every strongly connected component reachable from the roots, including the trivial ones.
-
Method Details
-
of
public static <N> List<StronglyConnectedComponents.Component<N>> of(Collection<N> roots, Function<N, ? extends Collection<N>> successors) Every strongly connected component reachable from the roots, including the trivial ones.- Parameters:
roots- where the search starts; every node reachable from them is assigned to exactly one componentsuccessors- the nodes a node has an edge to; asked once per node reached- Returns:
- the components, each with whether it is a cycle
-
cyclesOf
public static <N> List<StronglyConnectedComponents.Component<N>> cyclesOf(Collection<N> roots, Function<N, ? extends Collection<N>> successors) Only the components that are cycles.- See Also:
-