[mercury-users] relation.m: difference between dfsrev/2 and atsort/2

Nicholas Nethercote njn at csse.unimelb.edu.au
Thu Jun 1 22:13:49 AEST 2006

```Hi,

I'm looking at the relation.m module, thinking about using it for
topologically sorting Zinc code.

I don't understand the difference between dfsrev/2 and atsort/2.  For
dfsrev/2 we have this:

% relation.dfs(Rel, Dfs) is true if Dfs is a depth-first sorting of Rel,
% i.e. a list of the nodes in Rel such that it contains all elements
% in the relation and all the children of a node are placed in the list
% before the parent.
%
:- func relation.dfs(relation(T)) = list(relation_key).
:- pred relation.dfs(relation(T)::in, list(relation_key)::out) is det.

% relation.dfsrev(Rel, DfsRev) is true if DfsRev is a reverse
% depth-first sorting of Rel.  ie DfsRev is the reverse of Dfs
% from relation.dfs/2.
%
:- func relation.dfsrev(relation(T)) = list(relation_key).
:- pred relation.dfsrev(relation(T)::in, list(relation_key)::out) is det.

That's describes exactly what I thought a topological sort is.  If Rel is
cyclic, how can dfs/2 or dfsrev/2 succeed?

Then we have this:

% relation.tsort(R, TS) is true if TS is a topological sorting of R.
% It fails if R is cyclic.
%
:- pred relation.tsort(relation(T)::in, list(T)::out) is semidet.

Can anyone explain the difference?  Thanks.

Nick
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au