- Fixed bug in unit of work whereby detection of

    "cycles" among classes in highly interlinked patterns
    would not produce a deterministic
    result; thereby sometimes missing some nodes that
    should be considered cycles and causing further
    issues down the road.  Note this bug is in 0.6
    also; not backported at the moment.
    [ticket:2282]

1 files changed, 12 insertions, 3 deletions

diff --git a/lib/sqlalchemy/util/topological.py b/lib/sqlalchemy/util/topological.py
index 8f3406472..ba68b7136 100644
--- a/lib/sqlalchemy/util/topological.py
+++ b/lib/sqlalchemy/util/topological.py
@@ -48,17 +48,26 @@ def sort(tuples, allitems):
 
 def find_cycles(tuples, allitems):
     # straight from gvr with some mods
-    todo = set(allitems)
 
     edges = util.defaultdict(set)
     for parent, child in tuples:
         edges[parent].add(child)
+    nodes_to_test = set(edges)
 
     output = set()
 
-    while todo:
-        node = todo.pop()
+    # we'd like to find all nodes that are 
+    # involved in cycles, so we do the full
+    # pass through the whole thing for each
+    # node in the original list.
+
+    # we can go just through parent edge nodes.
+    # if a node is only a child and never a parent,
+    # by definition it can't be part of a cycle.  same
+    # if it's not in the edges at all.
+    for node in nodes_to_test:
         stack = [node]
+        todo = nodes_to_test.difference(stack)
         while stack:
             top = stack[-1]
             for node in edges[top]: