TopoSortDoc.tioga
Mike Spreitzer, March 14, 1988
Last tweaked by Mike Spreitzer on March 21, 1988 4:02:32 pm PST
TopoSort
CEDAR 7.0 —
TopoSort
Mike Spreitzer
© Copyright 1988 Xerox Corporation. All rights reserved.
Abstract: This package performs topological sorting: given a set of values, and a partial order among those values, it finds a total order consistent with the partial order. The set of values is given as an abstract list, which is put into the total order. The partial order is given by a procedure that compares two list nodes. If the partial order is in fact total, the sort algorithm reduces to the merge-sort used by List.Sort. The list is represented abstractly, and can be singly or doubly linked.
Created by: Mike Spreitzer
Maintained by: Mike Spreitzer <Spreitzer.pa>
Keywords: Topological sort, partial order, total order, list
XEROX  Xerox Corporation
   Palo Alto Research Center
   3333 Coyote Hill Road
   Palo Alto, California 94304

1. TopoSort
See the interface.
For an example client, see TopoSortTest. It keeps a doubly-linked ring, and demonstrates how TopoSort can be used to view that ring as a list and sort it. It also keeps a LIST OF REF ANY, and demonstrates how TopoSort can be used to sort that. The LIST OF REF ANY can also be passed to List.Sort for performance comparisons.