bachesta@genesis.Data-IO.COM writes:
> Jarle,

> To answer your question about the cycle being printed out here
> is a tsort output sample. The list is much longer. If I'm reading
> the output correctly it is not printing the name of the node which
> causes the cycle, but simply the node in topgraphical order.
> 	

[ list of tsort messages deleted ].

I will try to make things a bit clearer.  tsort uses two outport streams,
stdout and stderr, as most/many Unix programs do.  Now, the stdout stream
contains the resulting toplogical order (really a total ordering of a
partially ordered set).  If the input data is without cyclic dependencies
this is all there is to it.  However, if there are cyclic dependencies in
the data, as is the case for libgcc1.a, tsort will need to break/remove
some of the dependencies in order to create a total ordering.  Whenever
tsort does this it prints "Cycle in data:" to the stderr stream, followed
by the names of the nodes that are in the detected cycle.  The problem with
the original version is that it tries to find the longest cycle that a
given node is part of (NP-complete problem).  So the list you posted in
your message is one cycle that will be broken by tsort.  To break the
cycle, tsort will remove all dependencies to the last nodename that is
printed out in the list, and then this node can be removed and tsort can
continue with the first strategy again (see the code).

Hope this made it a bit clearer.  If you're really interested you should
study the code.  If anyone has some good ideas about cycle-breaking
heuristics that would cause fewer cycle breakings for a given problem,
well, the source is there.... :-)

					-jarle
----
"Never write it in C if you can do it in `awk';
 Never do it in `awk' if `sed' can handle it; Never use `sed' when `tr'
 can do the job; Never invoke `tr' when `cat' is sufficient; Avoid
 using `cat' whenever possible"
				-- Taylor's Laws of Programming

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