[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
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe: Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------
More information about the users
mailing list