Mercurial > repos > shellac > sam_consensus_v3
comparison env/lib/python3.9/site-packages/galaxy/util/topsort.py @ 0:4f3585e2f14b draft default tip
"planemo upload commit 60cee0fc7c0cda8592644e1aad72851dec82c959"
author | shellac |
---|---|
date | Mon, 22 Mar 2021 18:12:50 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:4f3585e2f14b |
---|---|
1 """ | |
2 Topological sort. | |
3 | |
4 From Tim Peters, see: | |
5 http://mail.python.org/pipermail/python-list/1999-July/006660.html | |
6 | |
7 topsort takes a list of pairs, where each pair (x, y) is taken to | |
8 mean that x <= y wrt some abstract partial ordering. The return | |
9 value is a list, representing a total ordering that respects all | |
10 the input constraints. | |
11 E.g., | |
12 | |
13 topsort( [(1,2), (3,3)] ) | |
14 | |
15 Valid topological sorts would be any of (but nothing other than) | |
16 | |
17 [3, 1, 2] | |
18 [1, 3, 2] | |
19 [1, 2, 3] | |
20 | |
21 ... however this variant ensures that 'key' order (first element of | |
22 tuple) is preserved so the following will be result returned: | |
23 | |
24 [1, 3, 2] | |
25 | |
26 because those are the permutations of the input elements that | |
27 respect the "1 precedes 2" and "3 precedes 3" input constraints. | |
28 Note that a constraint of the form (x, x) is really just a trick | |
29 to make sure x appears *somewhere* in the output list. | |
30 | |
31 If there's a cycle in the constraints, say | |
32 | |
33 topsort( [(1,2), (2,1)] ) | |
34 | |
35 then CycleError is raised, and the exception object supports | |
36 many methods to help analyze and break the cycles. This requires | |
37 a good deal more code than topsort itself! | |
38 """ | |
39 | |
40 | |
41 class CycleError(Exception): | |
42 def __init__(self, sofar, numpreds, succs): | |
43 Exception.__init__(self, "cycle in constraints", | |
44 sofar, numpreds, succs) | |
45 self.preds = None | |
46 | |
47 # return as much of the total ordering as topsort was able to | |
48 # find before it hit a cycle | |
49 def get_partial(self): | |
50 return self[1] | |
51 | |
52 # return remaining elt -> count of predecessors map | |
53 def get_pred_counts(self): | |
54 return self[2] | |
55 | |
56 # return remaining elt -> list of successors map | |
57 def get_succs(self): | |
58 return self[3] | |
59 | |
60 # return remaining elements (== those that don't appear in | |
61 # get_partial()) | |
62 def get_elements(self): | |
63 return self.get_pred_counts().keys() | |
64 | |
65 # Return a list of pairs representing the full state of what's | |
66 # remaining (if you pass this list back to topsort, it will raise | |
67 # CycleError again, and if you invoke get_pairlist on *that* | |
68 # exception object, the result will be isomorphic to *this* | |
69 # invocation of get_pairlist). | |
70 # The idea is that you can use pick_a_cycle to find a cycle, | |
71 # through some means or another pick an (x,y) pair in the cycle | |
72 # you no longer want to respect, then remove that pair from the | |
73 # output of get_pairlist and try topsort again. | |
74 def get_pairlist(self): | |
75 succs = self.get_succs() | |
76 answer = [] | |
77 for x in self.get_elements(): | |
78 if x in succs: | |
79 for y in succs[x]: | |
80 answer.append((x, y)) | |
81 else: | |
82 # make sure x appears in topsort's output! | |
83 answer.append((x, x)) | |
84 return answer | |
85 | |
86 # return remaining elt -> list of predecessors map | |
87 def get_preds(self): | |
88 if self.preds is not None: | |
89 return self.preds | |
90 self.preds = preds = {} | |
91 remaining_elts = self.get_elements() | |
92 for x in remaining_elts: | |
93 preds[x] = [] | |
94 succs = self.get_succs() | |
95 | |
96 for x in remaining_elts: | |
97 if x in succs: | |
98 for y in succs[x]: | |
99 preds[y].append(x) | |
100 | |
101 if __debug__: | |
102 for x in remaining_elts: | |
103 assert len(preds[x]) > 0 | |
104 return preds | |
105 | |
106 # return a cycle [x, ..., x] at random | |
107 def pick_a_cycle(self): | |
108 remaining_elts = self.get_elements() | |
109 | |
110 # We know that everything in remaining_elts has a predecessor, | |
111 # but don't know that everything in it has a successor. So | |
112 # crawling forward over succs may hit a dead end. Instead we | |
113 # crawl backward over the preds until we hit a duplicate, then | |
114 # reverse the path. | |
115 preds = self.get_preds() | |
116 from random import choice | |
117 x = choice(remaining_elts) | |
118 answer = [] | |
119 index = {} | |
120 in_answer = index.has_key | |
121 while not in_answer(x): | |
122 index[x] = len(answer) # index of x in answer | |
123 answer.append(x) | |
124 x = choice(preds[x]) | |
125 answer.append(x) | |
126 answer = answer[index[x]:] | |
127 answer.reverse() | |
128 return answer | |
129 | |
130 | |
131 def _numpreds_and_successors_from_pairlist(pairlist): | |
132 numpreds = {} # elt -> # of predecessors | |
133 successors = {} # elt -> list of successors | |
134 for first, second in pairlist: | |
135 # make sure every elt is a key in numpreds | |
136 if first not in numpreds: | |
137 numpreds[first] = 0 | |
138 if second not in numpreds: | |
139 numpreds[second] = 0 | |
140 | |
141 # if they're the same, there's no real dependence | |
142 if first == second: | |
143 continue | |
144 | |
145 # since first < second, second gains a pred ... | |
146 numpreds[second] = numpreds[second] + 1 | |
147 | |
148 # ... and first gains a succ | |
149 if first in successors: | |
150 successors[first].append(second) | |
151 else: | |
152 successors[first] = [second] | |
153 return numpreds, successors | |
154 | |
155 | |
156 def topsort(pairlist): | |
157 numpreds, successors = _numpreds_and_successors_from_pairlist(pairlist) | |
158 | |
159 # suck up everything without a predecessor | |
160 answer = [x for x in numpreds.keys() if numpreds[x] == 0] | |
161 | |
162 # for everything in answer, knock down the pred count on | |
163 # its successors; note that answer grows *in* the loop | |
164 for x in answer: | |
165 assert numpreds[x] == 0 | |
166 del numpreds[x] | |
167 if x in successors: | |
168 for y in successors[x]: | |
169 numpreds[y] = numpreds[y] - 1 | |
170 if numpreds[y] == 0: | |
171 answer.append(y) | |
172 # following "del" isn't needed; just makes | |
173 # CycleError details easier to grasp | |
174 del successors[x] | |
175 | |
176 if numpreds: | |
177 # everything in numpreds has at least one predecessor -> | |
178 # there's a cycle | |
179 if __debug__: | |
180 for x in numpreds.keys(): | |
181 assert numpreds[x] > 0 | |
182 raise CycleError(answer, numpreds, successors) | |
183 return answer | |
184 | |
185 | |
186 def topsort_levels(pairlist): | |
187 numpreds, successors = _numpreds_and_successors_from_pairlist(pairlist) | |
188 | |
189 answer = [] | |
190 | |
191 while 1: | |
192 # Suck up everything without a predecessor. | |
193 levparents = [x for x in numpreds.keys() if numpreds[x] == 0] | |
194 if not levparents: | |
195 break | |
196 answer.append(levparents) | |
197 for levparent in levparents: | |
198 del numpreds[levparent] | |
199 if levparent in successors: | |
200 for levparentsucc in successors[levparent]: | |
201 numpreds[levparentsucc] -= 1 | |
202 del successors[levparent] | |
203 | |
204 if numpreds: | |
205 # Everything in num_parents has at least one child -> | |
206 # there's a cycle. | |
207 raise CycleError(answer, numpreds, successors) | |
208 | |
209 return answer |