← Back to branch summary

~ubuntu-branches/debian/sid/sqlalchemy/sid

« back to all changes in this revision

Viewing changes to lib/sqlalchemy/util/topological.py

  • Committer: Bazaar Package Importer
  • Author(s): Piotr Ożarowski
  • Date: 2011-10-18 00:02:50 UTC
  • mfrom: (1.4.16 upstream)
  • Revision ID: james.westby@ubuntu.com-20111018000250-prowqcleosluapxg
Tags: 0.7.3-2
http://bugs.debian.org/645697
remove build-indep from build target's dependencies (closes: 645697)

Show diffs side-by-side

added added

removed removed

Lines of Context:
lib/sqlalchemy/util/topological.py
28
28
 
29
29
        if not output:
30
30
            raise CircularDependencyError(
31
 
                    "Circular dependency detected",
 
31
                    "Circular dependency detected.",
32
32
                    find_cycles(tuples, allitems), 
33
33
                    _gen_edges(edges)
34
34
                )
48
48
 
49
49
def find_cycles(tuples, allitems):
50
50
    # straight from gvr with some mods
51
 
    todo = set(allitems)
52
51
 
53
52
    edges = util.defaultdict(set)
54
53
    for parent, child in tuples:
55
54
        edges[parent].add(child)
 
55
    nodes_to_test = set(edges)
56
56
 
57
57
    output = set()
58
58
 
59
 
    while todo:
60
 
        node = todo.pop()
 
59
    # we'd like to find all nodes that are 
 
60
    # involved in cycles, so we do the full
 
61
    # pass through the whole thing for each
 
62
    # node in the original list.
 
63
 
 
64
    # we can go just through parent edge nodes.
 
65
    # if a node is only a child and never a parent,
 
66
    # by definition it can't be part of a cycle.  same
 
67
    # if it's not in the edges at all.
 
68
    for node in nodes_to_test:
61
69
        stack = [node]
 
70
        todo = nodes_to_test.difference(stack)
62
71
        while stack:
63
72
            top = stack[-1]
64
73
            for node in edges[top]: