Path: utzoo!mnetor!uunet!lll-winken!lll-tis!mordor!sri-spam!sri-unix!quintus!ok
From: ok@quintus.UUCP (Richard A. O'Keefe)
Newsgroups: comp.lang.prolog
Subject: Re: Wierd Topological Sort
Message-ID: <876@cresswell.quintus.UUCP>
Date: 14 Apr 88 07:53:56 GMT
References: <5224@sdcrdcf.UUCP>
Organization: Quintus Computer Systems, Mountain View, CA
Lines: 65

In article <5224@sdcrdcf.UUCP>, markb@sdcrdcf.UUCP (Mark Biggar) writes:
> I have a problem where I need to do a topological sort on the nodes of a
> directed graph.  This would be simple except that the graphs can contain
> cycles.   It is the nature of the problem then each node has only ONE
> edge leaving it, but may have several edges leading to it.  This means
> that any connected subgraph can have at most one cycle in it.  I wish to
> treat these cycles as single nodes in the sorted list.
> 
> So if I have a list of directed edges like:
> 
> [d(e,a),d(b,c),d(f,b),d(a,c),d(d,e),d(c,e)]
> 
> I get the result:
> 
> [[e,a,c],b,f,d]  (or some other permutation that is a valid topological sort)
> 
> The graphs I am working with may have several disjoint pieces (each of which
> may contain a cycle).
> 
There are two parts to the question:  how do you do this at all, and how
do you do it in Prolog.  The Prolog part isn't terribly interesting, there
is code for topological sort and union/find already drifting around.  So
I'll concentrate on the first part.

Such a graph is a sort of forest, except that some of the "trees" have
a ring as their root instead of a single node.

The best method I can think of is to adapt the usual Depth-First-Search
method for determining strongly connected components.

    for Node in nodes(Graph) do visited(Node) := false od
    Order := []
    for Node in nodes(Graph) do if not visited(Node) then
	Stack := []	% all the nodes reachable from Node
	N := Node
	while not visited(N) and there is an arc N->P do
	    visited(N) := true
	    Stack := [N|Stack]
	    N := P
	od
	if visited(N) then
	    %  either we've found a cycle, or a previously processed path
	    if member(N, Stack) then
		%  it's a cycle
		Cycle := []
		repeat Cycle,Stack := [head(Stack)|Cycle], tail(Stack)
		until head(Cycle) = N
		Order := [[Cycle]|Order]
	    fi
	else
	    % we've found a plain root
	    visited(N) := true
	    Stack := [N|Stack]
	fi
	Order := append(Stack, Order)
    fi od
    Order := reverse(Order)

Interestingly enough, we can use ordinary lists for Stack, Cycle, and Order.
If the member(N, Stack) test takes k steps, so what?  It must have taken at
least k steps to make Stack in the first place, so using ordinary member/2
won't spoil the asymptotic efficiency.  The trick is representing visited()
and the collection of arcs.  That's what will make this an O(V.lgV) method
in Prolog (V being the number of vertices) rather than an O(V) method.

Caveat:  I haven't tested this code.