Sapan Bhatia | 24836f1 | 2013-08-27 10:16:05 -0400 | [diff] [blame] | 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 | |
Sapan Bhatia | 467b7ce | 2013-10-02 09:25:46 -0400 | [diff] [blame^] | 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 | |
Sapan Bhatia | 24836f1 | 2013-08-27 10:16:05 -0400 | [diff] [blame] | 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 | |
Sapan Bhatia | 24836f1 | 2013-08-27 10:16:05 -0400 | [diff] [blame] | 35 | for k,v in reverse.iteritems(): |
| 36 | if (not v): |
| 37 | sources.append(k) |
| 38 | |
Sapan Bhatia | 467b7ce | 2013-10-02 09:25:46 -0400 | [diff] [blame^] | 39 | rev_order = [] |
Sapan Bhatia | 24836f1 | 2013-08-27 10:16:05 -0400 | [diff] [blame] | 40 | marked = [] |
| 41 | while sources: |
Sapan Bhatia | 467b7ce | 2013-10-02 09:25:46 -0400 | [diff] [blame^] | 42 | n = sources.pop(0) |
Sapan Bhatia | 24836f1 | 2013-08-27 10:16:05 -0400 | [diff] [blame] | 43 | try: |
| 44 | for m in g[n]: |
| 45 | if m not in marked: |
| 46 | sources.append(m) |
| 47 | marked.append(m) |
| 48 | except KeyError: |
| 49 | pass |
| 50 | if (n in steps): |
Sapan Bhatia | 467b7ce | 2013-10-02 09:25:46 -0400 | [diff] [blame^] | 51 | rev_order.append(n) |
| 52 | order = rev_order.reverse() |
Sapan Bhatia | 24836f1 | 2013-08-27 10:16:05 -0400 | [diff] [blame] | 53 | |
| 54 | return order |
| 55 | |
Sapan Bhatia | 467b7ce | 2013-10-02 09:25:46 -0400 | [diff] [blame^] | 56 | graph_file=open('model-deps').read() |
| 57 | g = json.loads(graph_file) |
| 58 | print toposort(g) |
| 59 | |
| 60 | #print toposort({'a':'b','b':'c','c':'d','d':'c'},['d','c','b','a']) |