S.Çağlar Onur | a95895d | 2015-02-09 13:34:11 -0500 | [diff] [blame] | 1 | #!/usr/bin/env python |
Sapan Bhatia | 24836f1 | 2013-08-27 10:16:05 -0400 | [diff] [blame] | 2 | |
| 3 | import time |
| 4 | import traceback |
| 5 | import commands |
| 6 | import threading |
| 7 | import json |
Sapan Bhatia | 45cbbc3 | 2014-03-11 17:48:30 -0400 | [diff] [blame] | 8 | import pdb |
Sapan Bhatia | 24836f1 | 2013-08-27 10:16:05 -0400 | [diff] [blame] | 9 | |
| 10 | from datetime import datetime |
| 11 | from collections import defaultdict |
| 12 | |
Sapan Bhatia | 45cbbc3 | 2014-03-11 17:48:30 -0400 | [diff] [blame] | 13 | # Topological sort |
| 14 | # Notes: |
| 15 | # - Uses a stack instead of recursion |
| 16 | # - Forfeits optimization involving tracking currently visited nodes |
Sapan Bhatia | 467b7ce | 2013-10-02 09:25:46 -0400 | [diff] [blame] | 17 | def toposort(g, steps=None): |
Sapan Bhatia | 45cbbc3 | 2014-03-11 17:48:30 -0400 | [diff] [blame] | 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) |
Sapan Bhatia | 467b7ce | 2013-10-02 09:25:46 -0400 | [diff] [blame] | 25 | if (not steps): |
Sapan Bhatia | 45cbbc3 | 2014-03-11 17:48:30 -0400 | [diff] [blame] | 26 | steps = all_nodes |
Sapan Bhatia | 467b7ce | 2013-10-02 09:25:46 -0400 | [diff] [blame] | 27 | |
Sapan Bhatia | 45cbbc3 | 2014-03-11 17:48:30 -0400 | [diff] [blame] | 28 | # Final order |
Sapan Bhatia | a2227d1 | 2013-10-02 09:48:42 -0400 | [diff] [blame] | 29 | order = [] |
Sapan Bhatia | a2227d1 | 2013-10-02 09:48:42 -0400 | [diff] [blame] | 30 | |
Sapan Bhatia | 45cbbc3 | 2014-03-11 17:48:30 -0400 | [diff] [blame] | 31 | # DFS stack, not using recursion |
| 32 | stack = [] |
Sapan Bhatia | a2227d1 | 2013-10-02 09:48:42 -0400 | [diff] [blame] | 33 | |
Sapan Bhatia | 45cbbc3 | 2014-03-11 17:48:30 -0400 | [diff] [blame] | 34 | # Unmarked set |
| 35 | unmarked = all_nodes |
Sapan Bhatia | 24836f1 | 2013-08-27 10:16:05 -0400 | [diff] [blame] | 36 | |
Sapan Bhatia | 45cbbc3 | 2014-03-11 17:48:30 -0400 | [diff] [blame] | 37 | # visiting = [] - skip, don't expect 1000s of nodes, |E|/|V| is small |
Sapan Bhatia | 24836f1 | 2013-08-27 10:16:05 -0400 | [diff] [blame] | 38 | |
Sapan Bhatia | 45cbbc3 | 2014-03-11 17:48:30 -0400 | [diff] [blame] | 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): |
Sapan Bhatia | 6b1b7fc | 2015-01-27 03:54:29 +0000 | [diff] [blame] | 48 | add = False |
| 49 | stack.insert(0,m) |
Sapan Bhatia | 45cbbc3 | 2014-03-11 17:48:30 -0400 | [diff] [blame] | 50 | except KeyError: |
| 51 | pass |
| 52 | if (add): |
Sapan Bhatia | 6b1b7fc | 2015-01-27 03:54:29 +0000 | [diff] [blame] | 53 | if (n in steps and n not in order): |
Sapan Bhatia | 45cbbc3 | 2014-03-11 17:48:30 -0400 | [diff] [blame] | 54 | order.append(n) |
| 55 | item = stack.pop(0) |
Sapan Bhatia | 6b1b7fc | 2015-01-27 03:54:29 +0000 | [diff] [blame] | 56 | try: |
| 57 | unmarked.remove(item) |
| 58 | except ValueError: |
| 59 | pass |
Sapan Bhatia | 45cbbc3 | 2014-03-11 17:48:30 -0400 | [diff] [blame] | 60 | |
| 61 | noorder = list(set(steps) - set(order)) |
| 62 | return order + noorder |
| 63 | |
| 64 | def main(): |
Scott Baker | 286a78f | 2015-02-18 16:13:48 -0800 | [diff] [blame] | 65 | graph_file=open('xos.deps').read() |
Sapan Bhatia | 45cbbc3 | 2014-03-11 17:48:30 -0400 | [diff] [blame] | 66 | g = json.loads(graph_file) |
| 67 | print toposort(g) |
| 68 | |
| 69 | if (__name__=='__main__'): |
| 70 | main() |
Sapan Bhatia | 467b7ce | 2013-10-02 09:25:46 -0400 | [diff] [blame] | 71 | |
| 72 | #print toposort({'a':'b','b':'c','c':'d','d':'c'},['d','c','b','a']) |