planetstack/openstack_observer/toposort.py

   1 #!/usr/bin/python
   2
   3 import time
   4 import traceback
   5 import commands
   6 import threading
   7 import json
   8 import pdb
   9
  10 from datetime import datetime
  11 from collections import defaultdict
  12
  13 # Topological sort
  14 # Notes:
  15 # - Uses a stack instead of recursion
  16 # - Forfeits optimization involving tracking currently visited nodes
  17 def toposort(g, steps=None):
  18         # Get set of all nodes, including those without outgoing edges
  19         keys = set(g.keys())
  20         values = set({})
  21         for v in g.values():
  22                 values=values | set(v)
  23
  24         all_nodes=list(keys|values)
  25         if (not steps):
  26                 steps = all_nodes
  27
  28         # Final order
  29         order = []
  30
  31         # DFS stack, not using recursion
  32         stack = []
  33
  34         # Unmarked set
  35         unmarked = all_nodes
  36
  37         # visiting = [] - skip, don't expect 1000s of nodes, |E|/|V| is small
  38
  39         while unmarked:
  40                 stack.insert(0,unmarked[0]) # push first unmarked
  41
  42                 while (stack):
  43                         n = stack[0]
  44                         add = True
  45                         try:
  46                                 for m in g[n]:
  47                                         if (m in unmarked):
  48                                                 if (m not in stack):
  49                                                         add = False
  50                                                         stack.insert(0,m)
  51                                                 else:
  52                                                         # Should not happen, if so there's a loop
  53                                                         print 'Loop at %s'%m
  54                         except KeyError:
  55                                 pass
  56                         if (add):
  57                                 if (n in steps):
  58                                         order.append(n)
  59                                 item = stack.pop(0)
  60                                 unmarked.remove(item)
  61
  62         noorder = list(set(steps) - set(order))
  63         return order + noorder
  64
  65 def main():
  66         graph_file=open('planetstack.deps').read()
  67         g = json.loads(graph_file)
  68         print toposort(g)
  69
  70 if (__name__=='__main__'):
  71         main()
  72
  73 #print toposort({'a':'b','b':'c','c':'d','d':'c'},['d','c','b','a'])