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