| Age | Commit message (Collapse) | Author |
|---|
|
|
|
|
|
Approved by jmc@, with minor corrections coming up.
|
|
|
|
|
|
- COMPATIBILITY merge
- macro cleanup
- kill whitespace at EOL
- new sentence, new line
ssh pages ok markus@
|
|
rescinded 22 July 1999. Proofed by myself and Theo.
|
|
|
|
and rescind 3rd licence clause.
|
|
|
|
outside the tree)
|
|
hand editing to make comments line up correctly. Another pass is forthcoming that handles the cases that could not be done automatically.
|
|
|
|
be a single digit. Powered by mantoya@.
millert@ ok.
|
|
|
|
Under some circumstances, trying to find a cycle starting with a given
point can be very time-consuming (probably exponential, as an
implementation of an NP-complete problem), so we lower our expectations,
and just report the first cycle we find, irregardless of which point it
cuts, which is guaranteed to be much faster (quadratic behavior at the
worst--because we won't explore more than a tree out of the graph).
Always find that cycle, even if -q is specified, so that -q is only
`quiet', e.g., does not change the reported result.
Based on a testcase reported by Dragos Ruiu, okay millert@
|
|
|
|
|
|
Another Murphy's law: complicated code always works right the first
time. Stupid dumb details, on the other hand.
Of course we can't share both arrays, as we don't know how they will
grow, duh !
|
|
- nodes without a hint should be fully transparent. The make_transparent
procedure is potentially slow, but in reality, it's very fast.
- don't automatically add an order to un-hinted nodes, so that they are
truely transparent.
Better memory allocation: split the hash of nodes into a single array
instead of duplicating the memory requirements.
Okay Todd.
|
|
will be first. Also, keep order around between hints file and reading
normal pairt, so that this option actually is useful.
|
|
- just warn if hints file holds duplicates. So what ? We sure can't use
uniq to remove those.
- on the other hand, warn in verbose mode if main file holds nodes that
are not in hints file.
Ok millert@
|
|
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@
|
|
|
|
least, this is the impression I get from looking at a lot of Perl docs.
|
|
|
|
|
|
|
|
|
|
netbsd pr#1204
|
|
|
