Class StronglyConnectedComponents<N>

java.lang.Object

org.ek9lang.compiler.support.StronglyConnectedComponents<N>

Type Parameters:

N - the type of a node

All Implemented Interfaces:

BiFunction<Collection<N>, Function<N, ? extends Collection<N>>, List<StronglyConnectedComponents.Component<N>>>

public final class StronglyConnectedComponents<N>
extends Object
implements BiFunction<Collection<N>, Function<N, ? extends Collection<N>>, List<StronglyConnectedComponents.Component<N>>>

THE strongly connected components of a directed graph (Tarjan, 1972) - use this wherever a phase needs the cycles of a graph, never a private copy. It replaced the recursive copy in 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.

Hold one, typed by the node: new StronglyConnectedComponents<NodeId>(). Only the cycles: GraphCycles.

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static final record	StronglyConnectedComponents.Component<M>	One strongly connected component.

Constructor Summary

Constructors

Constructor	Description
StronglyConnectedComponents()

Method Summary

Modifier and Type	Method	Description
List<StronglyConnectedComponents.Component<N>>	apply(Collection<N> roots, Function<N, ? extends Collection<N>> successors)	Every strongly connected component reachable from the roots, including the trivial ones.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface BiFunction

andThen

Constructor Details

StronglyConnectedComponents

public StronglyConnectedComponents()

Method Details

apply

public List<StronglyConnectedComponents.Component<N>> apply(Collection<N> roots,
 Function<N, ? extends Collection<N>> successors)

Every strongly connected component reachable from the roots, including the trivial ones.

Specified by:

apply in interface BiFunction<Collection<N>, Function<N, ? extends Collection<N>>, List<StronglyConnectedComponents.Component<N>>>

Parameters:

roots - where the search starts; every node reachable from them is assigned to exactly one component

successors - the nodes a node has an edge to; asked once per node reached

Returns:

the components, each with whether it is a cycle