Subject: Re: Infinite tsort loop.
To: None <bachesta@genesis.Data-IO.COM>
From: Charles Hannum <mycroft@duality.gnu.ai.mit.edu>
List: current-users
Date: 11/24/1993 15:16:32
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-)

I've been toying with various ideas of how to short-circuit it and
avoid getting stuck in the NP rathole, but I haven't had time to
implement them yet.


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