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
|
# 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."""
from sqlalchemy.exc import CircularDependencyError
from sqlalchemy import util
__all__ = ['sort', 'sort_as_subsets', 'find_cycles']
def sort_as_subsets(tuples, allitems):
edges = util.defaultdict(set)
for parent, child in tuples:
edges[child].add(parent)
todo = set(allitems)
while todo:
output = set()
for node in list(todo):
if not todo.intersection(edges[node]):
output.add(node)
if not output:
raise CircularDependencyError(
"Circular dependency detected: cycles: %r all edges: %s" %
(find_cycles(tuples, allitems), _dump_edges(edges, True)))
todo.difference_update(output)
yield output
def sort(tuples, allitems):
"""sort the given list of items by dependency.
'tuples' is a list of tuples representing a partial ordering.
"""
for set_ in sort_as_subsets(tuples, allitems):
for s in set_:
yield s
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)
output = set()
while todo:
node = todo.pop()
stack = [node]
while stack:
top = stack[-1]
for node in edges[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
def _dump_edges(edges, reverse):
l = []
for left in edges:
for right in edges[left]:
if reverse:
l.append((right, left))
else:
l.append((left, right))
return repr(l)
|
