1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
# topological.py
# Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010 Michael Bayer mike_mp@zzzcomputing.com
#
# This module is part of SQLAlchemy and is released under
# the MIT License: http://www.opensource.org/licenses/mit-license.php
"""Topological sorting algorithms.
The topological sort is an algorithm that receives this list of
dependencies as a *partial ordering*, that is a list of pairs which
might say, *X is dependent on Y*, *Q is dependent on Z*, but does not
necessarily tell you anything about Q being dependent on X. Therefore,
its not a straight sort where every element can be compared to
another... only some of the elements have any sorting preference, and
then only towards just some of the other elements. For a particular
partial ordering, there can be many possible sorts that satisfy the
conditions.
"""
from sqlalchemy.exc import CircularDependencyError
from sqlalchemy import util
__all__ = ['sort']
class _EdgeCollection(object):
"""A collection of directed edges."""
def __init__(self):
self.parent_to_children = util.defaultdict(set)
self.child_to_parents = util.defaultdict(set)
def add(self, edge):
"""Add an edge to this collection."""
parentnode, childnode = edge
self.parent_to_children[parentnode].add(childnode)
self.child_to_parents[childnode].add(parentnode)
def has_parents(self, node):
return node in self.child_to_parents and bool(self.child_to_parents[node])
def edges_by_parent(self, node):
if node in self.parent_to_children:
return [(node, child) for child in self.parent_to_children[node]]
else:
return []
def outgoing(self, node):
"""an iterable returning all nodes reached via node's outgoing edges"""
return self.parent_to_children[node]
def get_parents(self):
return self.parent_to_children.keys()
def pop_node(self, node):
"""Remove all edges where the given node is a parent.
Return the collection of all nodes which were children of the
given node, and have no further parents.
"""
children = self.parent_to_children.pop(node, None)
if children is not None:
for child in children:
self.child_to_parents[child].remove(node)
if not self.child_to_parents[child]:
yield child
def __iter__(self):
for parent, children in self.parent_to_children.iteritems():
for child in children:
yield (parent, child)
def __repr__(self):
return repr(list(self))
def sort(tuples, allitems):
"""sort the given list of items by dependency.
'tuples' is a list of tuples representing a partial ordering.
"""
edges = _EdgeCollection()
nodes = set(allitems)
for t in tuples:
nodes.update(t)
edges.add(t)
queue = []
for n in nodes:
if not edges.has_parents(n):
queue.append(n)
output = []
while nodes:
if not queue:
raise CircularDependencyError("Circular dependency detected: %r" % edges)
node = queue.pop()
output.append(node)
nodes.remove(node)
for childnode in edges.pop_node(node):
queue.append(childnode)
return output
def find_cycles(tuples, allitems):
# straight from gvr with some mods
todo = set(allitems)
edges = _EdgeCollection()
for t in tuples:
todo.update(t)
edges.add(t)
output = set()
while todo:
node = todo.pop()
stack = [node]
while stack:
top = stack[-1]
for node in edges.outgoing(top):
if node in stack:
cyc = stack[stack.index(node):]
todo.difference_update(cyc)
output.update(cyc)
if node in todo:
stack.append(node)
todo.remove(node)
break
else:
node = stack.pop()
return output
|
