> The real problem, as I discovered a few days ago, is that tsort uses
> the simplest and stupidest possible algorithm to find the cycles in
> the dependency graph.  In the case of libcc1, this algorithm takes so
> long that it's simply not practical.
> 
> Various people I've asked have said the problem of longest cycle is NP
> complete, because it seems analogous to finding a Hamiltonian cycle (a
> cycle which goes through every vertex), which has been proven to be NP
> complete.  Fortunately I am an engineer, so I can ignore that.  B-)

:-)

A friend of me has also looked more closely at the source, and he said that
the only reason tsort tries to find the longest cycle in the graph is so that
it can print the cycle to stderr.  The information about which cycle is
longest is not used in the further processing of the graph (!).  I'm willing
to take his word for it (and a cursory browse of the code seems to prove him
right)...  It would thus seem that a simpler and less costly approach could
be used, such as simply printing the first and best cycle in the graph before
ripping out a node to break the cycle.  This should easily avoid the
NP-completeness problem (no?).

I'm sure my friend will come up with a set of diffs which does exactly
this.  I don't think this will break tsort, and I'm not even sure the end
result is going to be any different than before.  The reported cycles will
however be different from the ones reported previously.

- Havard

------------------------------------------------------------------------------