planetstack/observer/toposort.py

   1 #!/usr/bin/python
   2
   3 import time
   4 import traceback
   5 import commands
   6 import threading
   7 import json
   8
   9 from datetime import datetime
  10 from collections import defaultdict
  11
  12 def toposort(g, steps=None):
  13         if (not steps):
  14                 keys = set(g.keys())
  15                 values = set({})
  16                 for v in g.values():
  17                         values=values | set(v)
  18
  19                 steps=list(keys|values)
  20
  21         reverse = {}
  22
  23         for k,v in g.items():
  24                 for rk in v:
  25                         try:
  26                                 reverse[rk].append(k)
  27                         except:
  28                                 reverse[rk]=k
  29
  30         sources = []
  31         for k,v in g.items():
  32                 if not reverse.has_key(k):
  33                         sources.append(k)
  34
  35         for k,v in reverse.iteritems():
  36                 if (not v):
  37                         sources.append(k)
  38
  39         rev_order = []
  40         marked = []
  41         while sources:
  42                 n = sources.pop(0)
  43                 try:
  44                         for m in g[n]:
  45                                 if m not in marked:
  46                                         sources.append(m)
  47                                         marked.append(m)
  48                 except KeyError:
  49                         pass
  50                 if (n in steps):
  51                         rev_order.append(n)
  52         order = rev_order.reverse()
  53
  54         return order
  55
  56 graph_file=open('model-deps').read()
  57 g = json.loads(graph_file)
  58 print toposort(g)
  59
  60 #print toposort({'a':'b','b':'c','c':'d','d':'c'},['d','c','b','a'])