Good afternoon,

I've studied the source code for tsort a bit and think I've found a flaw.
Basically, the way tsort works is as follows:

1) Construct a graph from the input data
2) Remove all nodes which no other nodes depend on.
3) If still any nodes left there is a cycle in the graph.  Remove a node
that's part of a cycle.  Goto 2.

Now, the flaw is in the find_cycle part of the program.  The current
algorithm tries to find the longest cycle that a node is part of.  This is
an NP-complete problem and with approx 50 nodes and more than 1000 edges in
the graph (as is the case for libgcc1.a) this *do* take some time.....  And
moreover, the result of this traversal is only used for printing out on
stderr which nodes are part of this cycle, not for determining what node to
remove from the cycle.  I therefore modified the cycle finding algorithm to
just detect a cycle, print it and then remove the node.  This made my
building of the libgcc1.a tractable.  I would like the other persons
(sorry, I don't remember your names) that had problems building various
libraries to try this patch and see if there are any more (old or new) bugs
in it.  Diffs below.  
					-jarle

================================================================
*** /usr/src/usr.bin/tsort/tsort.c	Wed Nov 17 15:25:40 1993
--- tsort.c	Wed Nov 24 17:30:32 1993
***************
*** 278,282 ****
  tsort()
  {
! 	register NODE *n, *next;
  	register int cnt;
  
--- 278,282 ----
  tsort()
  {
! 	register NODE *n, *m, *next;
  	register int cnt;
  
***************
*** 317,320 ****
--- 317,322 ----
  		for (n = graph; n; n = n->n_next)
  			if (!(n->n_flags & NF_ACYCLIC)) {
+ 				for (m=graph; m; m=m->n_next)
+ 					m->n_flags &= ~NF_MARK;
  				if (cnt = find_cycle(n, n, 0, 0)) {
  					register int i;
***************
*** 357,361 ****
  }
  
! /* look for the longest cycle from node from to node to. */
  find_cycle(from, to, longest_len, depth)
  	NODE *from, *to;
--- 359,363 ----
  }
  
! /* look for a path from node from to node to. */
  find_cycle(from, to, longest_len, depth)
  	NODE *from, *to;
***************
*** 384,392 ****
  		} else {
  			len = find_cycle(*np, to, longest_len, depth + 1);
! 			if (len > longest_len)
  				longest_len = len;
  		}
  	}
- 	from->n_flags &= ~NF_MARK;
  	return(longest_len);
  }
--- 386,395 ----
  		} else {
  			len = find_cycle(*np, to, longest_len, depth + 1);
! 			if (len > longest_len) {
  				longest_len = len;
+ 				break;
+ 			}
  		}
  	}
  	return(longest_len);
  }

================================================================
"Beware of bugs in the above code; I have only proved it correct, not
 tried it."
				-- Donald Knuth

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