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