blob: 68398612cf46b2dddbef36bd5336a3189f9e7017 [file] [log] [blame]
S.Çağlar Onura95895d2015-02-09 13:34:11 -05001#!/usr/bin/env python
Sapan Bhatia24836f12013-08-27 10:16:05 -04002
3import time
4import traceback
5import commands
6import threading
7import json
Sapan Bhatia45cbbc32014-03-11 17:48:30 -04008import pdb
Sapan Bhatia24836f12013-08-27 10:16:05 -04009
10from datetime import datetime
11from collections import defaultdict
12
Sapan Bhatia45cbbc32014-03-11 17:48:30 -040013# Topological sort
14# Notes:
15# - Uses a stack instead of recursion
16# - Forfeits optimization involving tracking currently visited nodes
Sapan Bhatia467b7ce2013-10-02 09:25:46 -040017def toposort(g, steps=None):
Sapan Bhatia45cbbc32014-03-11 17:48:30 -040018 # 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)
Sapan Bhatia467b7ce2013-10-02 09:25:46 -040025 if (not steps):
Sapan Bhatia45cbbc32014-03-11 17:48:30 -040026 steps = all_nodes
Sapan Bhatia467b7ce2013-10-02 09:25:46 -040027
Sapan Bhatia45cbbc32014-03-11 17:48:30 -040028 # Final order
Sapan Bhatiaa2227d12013-10-02 09:48:42 -040029 order = []
Sapan Bhatiaa2227d12013-10-02 09:48:42 -040030
Sapan Bhatia45cbbc32014-03-11 17:48:30 -040031 # DFS stack, not using recursion
32 stack = []
Sapan Bhatiaa2227d12013-10-02 09:48:42 -040033
Sapan Bhatia45cbbc32014-03-11 17:48:30 -040034 # Unmarked set
35 unmarked = all_nodes
Sapan Bhatia24836f12013-08-27 10:16:05 -040036
Sapan Bhatia45cbbc32014-03-11 17:48:30 -040037 # visiting = [] - skip, don't expect 1000s of nodes, |E|/|V| is small
Sapan Bhatia24836f12013-08-27 10:16:05 -040038
Sapan Bhatia45cbbc32014-03-11 17:48:30 -040039 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):
Sapan Bhatia6b1b7fc2015-01-27 03:54:29 +000048 add = False
49 stack.insert(0,m)
Sapan Bhatia45cbbc32014-03-11 17:48:30 -040050 except KeyError:
51 pass
52 if (add):
Sapan Bhatia6b1b7fc2015-01-27 03:54:29 +000053 if (n in steps and n not in order):
Sapan Bhatia45cbbc32014-03-11 17:48:30 -040054 order.append(n)
55 item = stack.pop(0)
Sapan Bhatia6b1b7fc2015-01-27 03:54:29 +000056 try:
57 unmarked.remove(item)
58 except ValueError:
59 pass
Sapan Bhatia45cbbc32014-03-11 17:48:30 -040060
61 noorder = list(set(steps) - set(order))
62 return order + noorder
63
64def main():
Scott Baker286a78f2015-02-18 16:13:48 -080065 graph_file=open('xos.deps').read()
Sapan Bhatia45cbbc32014-03-11 17:48:30 -040066 g = json.loads(graph_file)
67 print toposort(g)
68
69if (__name__=='__main__'):
70 main()
Sapan Bhatia467b7ce2013-10-02 09:25:46 -040071
72#print toposort({'a':'b','b':'c','c':'d','d':'c'},['d','c','b','a'])