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
|
# simple implementation of topological sort
# using kjbuckets. For very large and very dense
# graphs you can do better...
from kjbuckets import kjGraph, kjSet
LOOPERROR = "LOOPERROR"
# topological sort
def tsort(list_of_pairs):
result = []
Graph = kjGraph(list_of_pairs)
notsource = (kjSet(Graph.values()) - kjSet(Graph.keys())).items()
while Graph:
sources = kjSet(Graph.keys())
dests = kjSet(Graph.values())
startingpoints = sources - dests
if not startingpoints:
raise LOOPERROR, "loop detected in Graph"
for node in startingpoints.items():
result.append(node)
del Graph[node]
return result + notsource
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"
|
