[_CDCSL_93-16_]<1>Cedar>release>TopoSort>TopoSortDoc.tioga~

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 — FOR INTERNAL XEROX USE ONLY

TopoSort

Mike Spreitzer

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

For Internal Xerox Use Only

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.