Topological Ordering of a Graph
/* Depth-first topological ordering of a directed graph with no cycles. */
/* The absence of cycles is not checked. The graph is defined by n/1 */
/* and graph/2. */
top_sort(Ts):-
n(NumberOfVertices),
top_sort_1(0, NumberOfVertices, [], Ts).
top_sort_1(NumberOfVertices, NumberOfVertices, Ts, Ts):-!.
top_sort_1(Vertex, NumberOfVertices, Ts0, Ts):-
Vertex1 is Vertex + 1,
top_sort_2([Vertex], [], Ts1),
union(Ts1, Ts0, Ts2),
top_sort_1(Vertex1, NumberOfVertices, Ts2, Ts).
top_sort_2([], Ts, Ts).
top_sort_2([Vertex|Vertices], Ts0, Ts):-
graph(Vertex, Successors),
top_sort_2(Successors, Ts0, Ts1),
union([Vertex|Ts0], Ts1, Ts2),
top_sort_2(Vertices, Ts2, Ts).
/* union(Xs, Ys, Zs) is true if Zs is the list of the set of elements in */
/* the union of the sets of elements in lists Xs and Ys. */
union([], Ys, Ys).
union([X|Xs], Ys, Zs):-member(X, Ys), !, union(Xs, Ys, Zs).
union([X|Xs], Ys, [X|Zs]):-union(Xs, Ys, Zs).
/* Example: The solution found by top_sort/1 is [9,6,3,4,8,2,0,5,1,7] */
/* The number of vertices in the graph */
n(10).
/* The edges from each vertex in the graph */
graph(0, [1, 5]).
graph(1, [7]).
graph(2, []).
graph(3, [2, 4, 7, 8]).
graph(4, [8]).
graph(5, []).
graph(6, [0, 1, 2]).
graph(7, []).
graph(8, [7]).
graph(9, [4]).
LPA Index
Home Page