Path: utzoo!mnetor!uunet!husc6!mailrus!ames!ucsd!sdcsvax!ucsdhub!hp-sdd!hplabs!sdcrdcf!markb
From: markb@sdcrdcf.UUCP (Mark Biggar)
Newsgroups: comp.lang.prolog
Subject: Wierd Topological Sort
Message-ID: <5224@sdcrdcf.UUCP>
Date: 12 Apr 88 19:18:53 GMT
Reply-To: markb@sdcrdcf.UUCP (Mark Biggar)
Organization: Unisys - System Development Group, Santa Monica
Lines: 21

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).

Mark Biggar
{allegra,burdvax,cbosgd,hplabs,ihnp4,akgua,sdcsvax}!sdcrdcf!markb
markb@rdcf.sm.unisys.com