Import std.algo.topological
std.algo.topological
TopologicalSort and FindCycle: an order of nodes where each comes before the nodes it leads to, as build steps, dependencies, and a tech tree need, and the cycle that keeps there from being one. The graph is the nodes given and every node their successors reach.
std/algo/topological.fb
Functions
TopologicalSort
function
Public Function TopologicalSort<N: Hashable>(nodes: N[], successors: Func(N): N[]): N[]?The nodes, and every node their successors reach, in an order where each comes before its
successors, or Null where they make a cycle, which FindCycle gives. Of the nodes that could
come next, the earliest goes first, by where it is in the nodes given, or past them, in the
order the rest were reached, which gives the least such order by those places; nodes that
nothing leads to keep the order they were given in.
FindCycle
function
Public Function FindCycle<N: Hashable>(nodes: N[], successors: Func(N): N[]): N[]?A cycle among the nodes and what their successors reach, its nodes in the order they lead to
each other, each once, or Null when there's none. It's the first that depth-first search meets,
going from the nodes given in their order: a node that's its own successor is a cycle of one.
Report an issue with this page or with FutureBlitz on GitHub.