3408
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
1 |
# topsort - dependency (topological) sorting and cycle finding functions
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
2 |
# Copyright (C) 2007 RADLogic
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
3 |
#
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
4 |
# This library is free software; you can redistribute it and/or
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
5 |
# modify it under the terms of the GNU Lesser General Public
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
6 |
# License as published by the Free Software Foundation;
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
7 |
# version 2.1 of the License.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
8 |
#
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
9 |
# This library is distributed in the hope that it will be useful,
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
10 |
# but WITHOUT ANY WARRANTY; without even the implied warranty of
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
11 |
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
12 |
# Lesser General Public License for more details.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
13 |
#
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
14 |
# See http://www.fsf.org/licensing/licenses/lgpl.txt for full license text.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
15 |
"""Provide toplogical sorting (i.e. dependency sorting) functions.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
16 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
17 |
The topsort function is based on code posted on Usenet by Tim Peters.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
18 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
19 |
Modifications:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
20 |
- added doctests
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
21 |
- changed some bits to use current Python idioms
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
22 |
(listcomp instead of filter, +=/-=, inherit from Exception)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
23 |
- added a topsort_levels version that ports items in each dependency level
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
24 |
into a sub-list
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
25 |
- added find_cycles to aid in cycle debugging
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
26 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
27 |
Run this module directly to run the doctests (unittests).
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
28 |
Make sure they all pass before checking in any modifications.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
29 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
30 |
Requires Python >= 2.2
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
31 |
(For Python 2.2 also requires separate sets.py module)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
32 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
33 |
This requires the rad_util.py module.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
34 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
35 |
"""
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
36 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
37 |
# Provide support for Python 2.2*
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
38 |
from __future__ import generators
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
39 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
40 |
__version__ = '$Revision: 0.9 $'
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
41 |
__date__ = '$Date: 2007/03/27 04:15:26 $'
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
42 |
__credits__ = '''Tim Peters -- original topsort code
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
43 |
Tim Wegener -- doctesting, updating to current idioms, topsort_levels,
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
44 |
find_cycles
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
45 |
'''
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
46 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
47 |
# Make Python 2.3 sets look like Python 2.4 sets.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
48 |
try:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
49 |
set
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
50 |
except NameError:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
51 |
from sets import Set as set
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
52 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
53 |
from rad_util import is_rotated
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
54 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
55 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
56 |
class CycleError(Exception):
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
57 |
"""Cycle Error"""
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
58 |
pass
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
59 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
60 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
61 |
def topsort(pairlist):
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
62 |
"""Topologically sort a list of (parent, child) pairs.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
63 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
64 |
Return a list of the elements in dependency order (parent to child order).
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
65 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
66 |
>>> print topsort( [(1,2), (3,4), (5,6), (1,3), (1,5), (1,6), (2,5)] )
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
67 |
[1, 2, 3, 5, 4, 6]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
68 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
69 |
>>> print topsort( [(1,2), (1,3), (2,4), (3,4), (5,6), (4,5)] )
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
70 |
[1, 2, 3, 4, 5, 6]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
71 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
72 |
>>> print topsort( [(1,2), (2,3), (3,2)] )
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
73 |
Traceback (most recent call last):
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
74 |
CycleError: ([1], {2: 1, 3: 1}, {2: [3], 3: [2]})
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
75 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
76 |
"""
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
77 |
num_parents = {} # element -> # of predecessors
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
78 |
children = {} # element -> list of successors
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
79 |
for parent, child in pairlist:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
80 |
# Make sure every element is a key in num_parents.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
81 |
if not num_parents.has_key( parent ):
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
82 |
num_parents[parent] = 0
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
83 |
if not num_parents.has_key( child ):
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
84 |
num_parents[child] = 0
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
85 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
86 |
# Since child has a parent, increment child's num_parents count.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
87 |
num_parents[child] += 1
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
88 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
89 |
# ... and parent gains a child.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
90 |
children.setdefault(parent, []).append(child)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
91 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
92 |
# Suck up everything without a parent.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
93 |
answer = [x for x in num_parents.keys() if num_parents[x] == 0]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
94 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
95 |
# For everything in answer, knock down the parent count on its children.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
96 |
# Note that answer grows *in* the loop.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
97 |
for parent in answer:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
98 |
del num_parents[parent]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
99 |
if children.has_key( parent ):
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
100 |
for child in children[parent]:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
101 |
num_parents[child] -= 1
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
102 |
if num_parents[child] == 0:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
103 |
answer.append( child )
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
104 |
# Following "del" isn't needed; just makes
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
105 |
# CycleError details easier to grasp.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
106 |
del children[parent]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
107 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
108 |
if num_parents:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
109 |
# Everything in num_parents has at least one child ->
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
110 |
# there's a cycle.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
111 |
raise CycleError(answer, num_parents, children)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
112 |
return answer
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
113 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
114 |
def topsort_levels(pairlist):
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
115 |
"""Topologically sort a list of (parent, child) pairs into depth levels.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
116 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
117 |
This returns a generator.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
118 |
Turn this into a an iterator using the iter built-in function.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
119 |
(if you iterate over the iterator, each element gets generated when
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
120 |
it is asked for, rather than generating the whole list up-front.)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
121 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
122 |
Each generated element is a list of items at that dependency level.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
123 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
124 |
>>> dependency_pairs = [(1,2), (3,4), (5,6), (1,3), (1,5), (1,6), (2,5)]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
125 |
>>> for level in iter(topsort_levels( dependency_pairs )):
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
126 |
... print level
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
127 |
[1]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
128 |
[2, 3]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
129 |
[4, 5]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
130 |
[6]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
131 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
132 |
>>> dependency_pairs = [(1,2), (1,3), (2,4), (3,4), (5,6), (4,5)]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
133 |
>>> for level in iter(topsort_levels( dependency_pairs )):
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
134 |
... print level
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
135 |
[1]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
136 |
[2, 3]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
137 |
[4]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
138 |
[5]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
139 |
[6]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
140 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
141 |
>>> dependency_pairs = [(1,2), (2,3), (3,4), (4, 3)]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
142 |
>>> try:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
143 |
... for level in iter(topsort_levels( dependency_pairs )):
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
144 |
... print level
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
145 |
... except CycleError, exc:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
146 |
... print 'CycleError:', exc
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
147 |
[1]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
148 |
[2]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
149 |
CycleError: ({3: 1, 4: 1}, {3: [4], 4: [3]})
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
150 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
151 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
152 |
The cycle error should look like.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
153 |
CycleError: ({3: 1, 4: 1}, {3: [4], 4: [3]})
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
154 |
# todo: Make the doctest more robust (i.e. handle arbitrary dict order).
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
155 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
156 |
"""
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
157 |
num_parents = {} # element -> # of predecessors
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
158 |
children = {} # element -> list of successors
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
159 |
for parent, child in pairlist:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
160 |
# Make sure every element is a key in num_parents.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
161 |
if not num_parents.has_key( parent ):
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
162 |
num_parents[parent] = 0
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
163 |
if not num_parents.has_key( child ):
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
164 |
num_parents[child] = 0
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
165 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
166 |
# Since child has a parent, increment child's num_parents count.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
167 |
num_parents[child] += 1
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
168 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
169 |
# ... and parent gains a child.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
170 |
children.setdefault(parent, []).append(child)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
171 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
172 |
return topsort_levels_core(num_parents, children)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
173 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
174 |
def topsort_levels_core(num_parents, children):
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
175 |
"""Topologically sort a bunch of interdependent items based on dependency.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
176 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
177 |
This returns a generator.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
178 |
Turn this into a an iterator using the iter built-in function.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
179 |
(if you iterate over the iterator, each element gets generated when
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
180 |
it is asked for, rather than generating the whole list up-front.)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
181 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
182 |
Each generated element is a list of items at that dependency level.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
183 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
184 |
>>> list(topsort_levels_core(
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
185 |
... {1: 0, 2: 1, 3: 1, 4: 1, 5: 2, 6: 2},
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
186 |
... {1: [2, 3, 5, 6], 2: [5], 3: [4], 4: [], 5: [6]}))
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
187 |
[[1], [2, 3], [4, 5], [6]]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
188 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
189 |
>>> list(topsort_levels_core(
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
190 |
... {1: 0, 2: 2, 3: 1},
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
191 |
... {1: [2], 2: [3], 3: [2]}))
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
192 |
Traceback (most recent call last):
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
193 |
CycleError: ({2: 1, 3: 1}, {2: [3], 3: [2]})
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
194 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
195 |
This function has a more complicated interface than topsort_levels,
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
196 |
but is useful if the data is easier to generate in this form.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
197 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
198 |
Arguments:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
199 |
num_parents -- key: item, value: number of parents (predecessors)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
200 |
children -- key: item, value: list of children (successors)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
201 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
202 |
"""
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
203 |
while 1:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
204 |
# Suck up everything without a predecessor.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
205 |
level_parents = [x for x in num_parents.keys() if num_parents[x] == 0]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
206 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
207 |
if not level_parents:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
208 |
break
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
209 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
210 |
# Offer the next generated item,
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
211 |
# which is a list of the items at this dependency level.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
212 |
yield level_parents
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
213 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
214 |
# For everything item in this level,
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
215 |
# decrement the parent count,
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
216 |
# since we have accounted for its parent.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
217 |
for level_parent in level_parents:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
218 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
219 |
del num_parents[level_parent]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
220 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
221 |
if children.has_key(level_parent):
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
222 |
for level_parent_child in children[level_parent]:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
223 |
num_parents[level_parent_child] -= 1
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
224 |
del children[level_parent]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
225 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
226 |
if num_parents:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
227 |
# Everything in num_parents has at least one child ->
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
228 |
# there's a cycle.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
229 |
raise CycleError(num_parents, children)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
230 |
else:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
231 |
# This is the end of the generator.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
232 |
raise StopIteration
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
233 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
234 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
235 |
def find_cycles(parent_children):
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
236 |
"""Yield cycles. Each result is a list of items comprising a cycle.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
237 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
238 |
Use a 'stack' based approach to find all the cycles.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
239 |
This is a generator, so yields each cycle as it finds it.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
240 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
241 |
It is implicit that the last item in each cycle list is a parent of the
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
242 |
first item (thereby forming a cycle).
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
243 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
244 |
Arguments:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
245 |
parent_children -- parent -> collection of children
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
246 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
247 |
Simplest cycle:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
248 |
>>> cycles = list(find_cycles({'A': ['B'], 'B': ['A']}))
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
249 |
>>> len(cycles)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
250 |
1
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
251 |
>>> cycle = cycles[0]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
252 |
>>> cycle.sort()
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
253 |
>>> print cycle
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
254 |
['A', 'B']
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
255 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
256 |
Simplest cycle with extra baggage at the start and the end:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
257 |
>>> cycles = list(find_cycles(parent_children={'A': ['B'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
258 |
... 'B': ['C'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
259 |
... 'C': ['B', 'D'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
260 |
... 'D': [],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
261 |
... }))
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
262 |
>>> len(cycles)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
263 |
1
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
264 |
>>> cycle = cycles[0]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
265 |
>>> cycle.sort()
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
266 |
>>> print cycle
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
267 |
['B', 'C']
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
268 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
269 |
Double cycle:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
270 |
>>> cycles = list(find_cycles(parent_children={'A': ['B'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
271 |
... 'B': ['C1', 'C2'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
272 |
... 'C1': ['D1'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
273 |
... 'D1': ['E1'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
274 |
... 'E1': ['D1'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
275 |
... 'C2': ['D2'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
276 |
... 'D2': ['E2'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
277 |
... 'E2': ['D2'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
278 |
... }))
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
279 |
>>> len(cycles)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
280 |
2
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
281 |
>>> for cycle in cycles:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
282 |
... cycle.sort()
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
283 |
>>> cycles.sort()
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
284 |
>>> cycle1 = cycles[0]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
285 |
>>> cycle1.sort()
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
286 |
>>> print cycle1
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
287 |
['D1', 'E1']
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
288 |
>>> cycle2 = cycles[1]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
289 |
>>> cycle2.sort()
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
290 |
>>> print cycle2
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
291 |
['D2', 'E2']
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
292 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
293 |
Simple cycle with children not specified for one item:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
294 |
# todo: Should this barf instead?
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
295 |
>>> cycles = list(find_cycles(parent_children={'A': ['B'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
296 |
... 'B': ['A'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
297 |
... 'C': ['D']}))
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
298 |
>>> len(cycles)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
299 |
1
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
300 |
>>> cycle = cycles[0]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
301 |
>>> cycle.sort()
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
302 |
>>> print cycle
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
303 |
['A', 'B']
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
304 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
305 |
Diamond cycle
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
306 |
>>> cycles = list(find_cycles(parent_children={'A': ['B1', 'B2'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
307 |
... 'B1': ['C'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
308 |
... 'B2': ['C'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
309 |
... 'C': ['A', 'B1']}))
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
310 |
>>> len(cycles)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
311 |
3
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
312 |
>>> sorted_cycles = []
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
313 |
>>> for cycle in cycles:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
314 |
... cycle = list(cycle)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
315 |
... cycle.sort()
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
316 |
... sorted_cycles.append(cycle)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
317 |
>>> sorted_cycles.sort()
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
318 |
>>> for cycle in sorted_cycles:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
319 |
... print cycle
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
320 |
['A', 'B1', 'C']
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
321 |
['A', 'B2', 'C']
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
322 |
['B1', 'C']
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
323 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
324 |
Hairy case (order can matter if something is wrong):
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
325 |
(Note order of B and C in the list.)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
326 |
>>> cycles = list(find_cycles(parent_children={
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
327 |
... 'TD': ['DD'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
328 |
... 'TC': ['DC'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
329 |
... 'DC': ['DQ'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
330 |
... 'C': ['DQ'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
331 |
... 'DQ': ['IA', 'TO'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
332 |
... 'IA': ['A'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
333 |
... 'A': ['B', 'C'],
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
334 |
... }))
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
335 |
>>> len(cycles)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
336 |
1
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
337 |
>>> cycle = cycles[0]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
338 |
>>> cycle.sort()
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
339 |
>>> print cycle
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
340 |
['A', 'C', 'DQ', 'IA']
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
341 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
342 |
"""
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
343 |
cycles = []
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
344 |
visited_nodes = set()
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
345 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
346 |
for parent in parent_children:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
347 |
if parent in visited_nodes:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
348 |
# This node is part of a path that has already been traversed.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
349 |
continue
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
350 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
351 |
paths = [[parent]]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
352 |
while paths:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
353 |
path = paths.pop()
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
354 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
355 |
parent = path[-1]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
356 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
357 |
try:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
358 |
children = parent_children[parent]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
359 |
except KeyError:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
360 |
continue
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
361 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
362 |
for child in children:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
363 |
# Keeping a set of the path nodes, for O(1) lookups at the
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
364 |
# expense of more memory and complexity, actually makes speed
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
365 |
# worse. (Due to construction of sets.)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
366 |
# This is O(N).
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
367 |
if child in path:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
368 |
# This is a cycle.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
369 |
cycle = path[path.index(child):]
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
370 |
# Check that this is not a dup cycle.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
371 |
is_dup = False
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
372 |
for other_cycle in cycles:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
373 |
if is_rotated(other_cycle, cycle):
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
374 |
is_dup = True
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
375 |
break
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
376 |
if not is_dup:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
377 |
cycles.append(cycle)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
378 |
yield cycle
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
379 |
else:
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
380 |
# Push this new path onto the 'stack'.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
381 |
# This is probably the most expensive part of the algorithm
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
382 |
# (a list copy).
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
383 |
paths.append(path + [child])
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
384 |
# Mark the node as visited.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
385 |
visited_nodes.add(child)
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
386 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
387 |
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
388 |
if __name__ == '__main__':
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
389 |
# Run the doctest tests.
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
390 |
import sys
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
391 |
import doctest
|
Gustavo J. A. M. Carneiro <gjc@inescporto.pt>
parents:
diff
changeset
|
392 |
doctest.testmod(sys.modules['__main__'])
|