Sort vertices topologically. Layers is a list of lists of
vertices where there are no edges from a layer to an earlier layer. The
predicate top_sort/2
flattens the layers using append/2.
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.
[semidet]ugraph_layers(Graph,
-Layers)