Import std.algo.topological

TopologicalSort

std.algo.topological

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.

Examples

// What each build step needs done before it.
Local needs = {"app": ["lib", "assets"], "lib": ["headers"], "assets": [], "headers": []}
Local before = Function(step: String): String[]
    Local after: String[] = []
    For entry In needs
        Local name, needed = entry
        If needed.Contains(step) Then after.Add(name)
    End For
    Return after
End Function

Expect(TopologicalSort(["headers", "assets"], before) == ["headers", "assets", "lib", "app"])

std/algo/topological.fb, line 61

Report an issue with this page or with FutureBlitz on GitHub.