File: tsort2.py

package info (click to toggle)
python-kjbuckets 2.2-4
  • links: PTS
  • area: main
  • in suites: potato
  • size: 264 kB
  • ctags: 262
  • sloc: ansic: 2,581; python: 363; makefile: 55
file content (37 lines) | stat: -rw-r--r-- 1,014 bytes parent folder | download | duplicates (2)
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"