CVS log for src/usr.bin/tsort/tsort.c

Up to [local] / src / usr.bin / tsort

Request diff between arbitrary revisions

Default branch: MAIN
Current tag: OPENBSD_3_0_BASE

Revision 1.10 / (download) - annotate - [select for diffs], Sat Jul 14 14:18:50 2001 UTC (22 years, 11 months ago) by espie
Branch: MAIN
CVS Tags: OPENBSD_3_0_BASE, OPENBSD_3_0
Changes since 1.9: +20 -16 lines
Diff to previous 1.9 (colored)

Fix cycle detection.
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@

This form allows you to request diff's between any two revisions of a file. You may select a symbolic revision name using the selection box or you may type in a numeric name using the type-in text box.