root/galaxy-central/lib/galaxy/util/topsort.py

リビジョン 2, 7.1 KB (コミッタ: hatakeyama, 14 年 前)

import galaxy-central

行番号 
1"""
2Topological sort.
3
4From Tim Peters, see:
5   http://mail.python.org/pipermail/python-list/1999-July/006660.html
6
7topsort takes a list of pairs, where each pair (x, y) is taken to
8mean that x <= y wrt some abstract partial ordering.  The return
9value is a list, representing a total ordering that respects all
10the input constraints.
11E.g.,
12   topsort( [(1,2), (3,3)] )
13may return any of (but nothing other than)
14   [3, 1, 2]
15   [1, 3, 2]
16   [1, 2, 3]
17because those are the permutations of the input elements that
18respect the "1 precedes 2" and "3 precedes 3" input constraints.
19Note that a constraint of the form (x, x) is really just a trick
20to make sure x appears *somewhere* in the output list.
21
22If there's a cycle in the constraints, say
23   topsort( [(1,2), (2,1)] )
24then CycleError is raised, and the exception object supports
25many methods to help analyze and break the cycles.  This requires
26a good deal more code than topsort itself!
27"""
28
29from exceptions import Exception
30
31class 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
120def 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
170def 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
Note: リポジトリブラウザについてのヘルプは TracBrowser を参照してください。