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         order = []
  40         marked = []
  41
  42         while sources:
  43                 n = sources.pop(0)
  44                 try:
  45                         for m in g[n]:
  46                                 if m not in marked:
  47                                         sources.append(m)
  48                                         marked.append(m)
  49                 except KeyError:
  50                         pass
  51                 if (n in steps):
  52                         order.append(n)
  53
  54         order.reverse()
  55
  56         return order
  57
  58 graph_file=open('model-deps').read()
  59 g = json.loads(graph_file)
  60 print toposort(g)
  61
  62 #print toposort({'a':'b','b':'c','c':'d','d':'c'},['d','c','b','a'])