-
Committer:
John Arbash Meinel
-
Date:
2009-08-13 21:30:07 UTC
-
mfrom:
(4577.3.2 1.18-topo_sort)
-
mto:
This revision was merged to the branch mainline in
revision
4629.
-
Revision ID:
john@arbash-meinel.com-20090813213007-4wqkou02fo0tegay
Bring in the optimized tsort code.
It turns out we needed a way to detect that there was graph cycles.
The easiest way to do it, is by noticing that we end up with a node
that has no gdfo. That means it has a parent that was not reached
before the child was reached, when walking from nodes with no known parents.
I'm 90% sure that this is correct, but arguably it should be detected
when creating the KnownGraph, and not during topo_sort.