Disable creation of an OpenStack gateway for private netwroks (and nat networks too...
[plstackapi.git] / 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'])