These predicates fail if Graph is cyclic. If Graph is not connected, the sub-graphs are individually sorted, where the root of each subgraph is in the first layer, the nodes connected to the roots in the second, etc.

?- top_sort([1-[2], 2-[3], 3-[]], L).
L = [1, 2, 3]

Compatibility

- The original version of this library provided top_sort/3 as a difference list version of top_sort/2. We removed this because the argument order was non-standard. Fixing causes hard to debug compatibility issues while we expect top_sort/3 was rarely used. A backward compatible top_sort/3 can be defined as

top_sort(Graph, Tail, Sorted) :-
    top_sort(Graph, Sorted0),
    append(Sorted0, Tail, Sorted).

The original version returned all vertices in a layer in reverse order. The current one returns them in standard order of terms, i.e., each layer is an ordered set.

- ugraph_layers/2 is a SWI-Prolog specific addition to this library.