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

[Nicholas Nethercote]

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