diff options
author | Marc Espie <espie@cvs.openbsd.org> | 2001-03-26 22:53:34 +0000 |
---|---|---|
committer | Marc Espie <espie@cvs.openbsd.org> | 2001-03-26 22:53:34 +0000 |
commit | 60ea328912452bb904fc34be01f64367de8fe8b3 (patch) | |
tree | 3a4743094e1fef5ac26efb7c9c1b9af4d6a1c1a5 /usr.bin/less | |
parent | 0ed499a8c4ed0e7ef2f74d6e681f98b82cce5028 (diff) |
Replacement for original tsort.
The old code suffers from a few defects:
- it does not even implement the standard optimal topological sort
algorithm. It's much slower.
- its longest cycle computation is completely bogus.
This is clean-slate code, that does implement the actual standard optimal
topological sort, together with a correct graph traversal to find longest
cycles.
It does also feature a `stable tsort' mode, where it uses a heap to yield
the least disturbed permutation of input nodes that satisfies the ordering
constraints (in particular, try tsort -f).
Thanks to the nature of the problem, the actual output won't exactly match
the old one, but it does pass the regression suite (and it is a topological
sorter).
Ok millert@
Diffstat (limited to 'usr.bin/less')
0 files changed, 0 insertions, 0 deletions