git://git.onelab.eu
/
plstackapi.git
/ blob
commit
grep
author
committer
pickaxe
?
search:
re
summary
|
shortlog
|
log
|
commit
|
commitdiff
|
tree
history
|
raw
|
HEAD
Merge branch 'master' of git://git.planet-lab.org/plstackapi
[plstackapi.git]
/
planetstack
/
observer
/
toposort.py
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
12
def toposort(g, steps):
13
reverse = {}
14
15
for k,v in g.items():
16
for rk in v:
17
try:
18
reverse[rk].append(k)
19
except:
20
reverse[rk]=k
21
22
sources = []
23
for k,v in g.items():
24
if not reverse.has_key(k):
25
sources.append(k)
26
27
28
for k,v in reverse.iteritems():
29
if (not v):
30
sources.append(k)
31
32
order = []
33
marked = []
34
while sources:
35
n = sources.pop()
36
try:
37
for m in g[n]:
38
if m not in marked:
39
sources.append(m)
40
marked.append(m)
41
except KeyError:
42
pass
43
if (n in steps):
44
order.append(n)
45
46
return order
47
48
print toposort({'a':'b','b':'c','c':'d','d':'c'},['d','c','b','a'])