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
|
# more complex implementation of topological sort
LOOPERROR = "LOOPERROR"
def tsort(pairs):
from kjbuckets import kjGraph, kjSet
G = kjGraph(pairs)
Gt = ~G # transpose
sources = kjSet(G.keys())
dests = kjSet(G.values())
all = (sources+dests).items()
total = len(all)
endpoints = dests - sources
for i in xrange(total-1, -1, -1):
#print i, endpoints
if not endpoints:
raise LOOPERROR, "loop detected"
choice = endpoints.choose_key()
for n in Gt.neighbors(choice):
G.delete_arc(n,choice)
if not G.has_key(n):
endpoints[n] = n
del endpoints[choice]
all[i] = choice
return all
if __name__=="__main__":
list = [ (1,2), (3,4), (1,6), (6,3), (3,9), (4,2) ]
print tsort(list)
try:
list = [ (1,2), (3,4), (1,6), (6,3), (3,9), (3,1) ]
print tsort(list)
print "WHOOPS: loop 1-6-3-1 not detected"
except LOOPERROR:
print "loop error as expected"
|
