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):
  13         reverse = {}
  14
  15         for k,v in g.items():
  16                 for rk in v:
  17                         try:
  18                                 reverse[rk].append(k)
  19                         except:
  20                                 reverse[rk]=k
  21
  22         sources = []
  23         for k,v in g.items():
  24                 if not reverse.has_key(k):
  25                         sources.append(k)
  26
  27
  28         for k,v in reverse.iteritems():
  29                 if (not v):
  30                         sources.append(k)
  31
  32         order = []
  33         marked = []
  34         while sources:
  35                 n = sources.pop()
  36                 try:
  37                         for m in g[n]:
  38                                 if m not in marked:
  39                                         sources.append(m)
  40                                         marked.append(m)
  41                 except KeyError:
  42                         pass
  43                 if (n in steps):
  44                         order.append(n)
  45
  46         return order
  47
  48 print toposort({'a':'b','b':'c','c':'d','d':'c'},['d','c','b','a'])