1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| from itertools import chain
flatten = chain.from_iterable # dedicated to eyquem ;)
class DGraph(object):
def __init__(self):
self.next = dict()
self.prev = dict()
def add_vertex(self, v):
if v not in self.next:
self.next[v] = []
self.prev[v] = []
def add_edge(self, (v1,v2)):
self.add_vertex(v1)
self.add_vertex(v2)
self.next[v1].append(v2)
self.prev[v2].append(v1)
def postorder(self, v, result=None):
"post-order DFS traversal from vertex v (no cycle detection)"
if result is None:
result = []
for n in self.next[v]:
if n not in result:
self.postorder(n, result)
result.append(v)
return result
def roots(self):
"returns all vertices without predecessors"
return (vtx for vtx, pred in self.prev.iteritems() if not pred)
def topological_sort(self):
return flatten(reversed(self.postorder(r)) for r in self.roots())
def vertices(self):
return self.next.iterkeys()
def dependency_sort(data):
# build the graph
G = DGraph()
for e in data:
if e[0] is None:
G.add_vertex(e[1])
else:
G.add_edge(e)
# sort the vertices
l = list(G.topological_sort())
# check for cycles:
# if the graph has cycles, all vertices won't be in the result
v = set(G.vertices())
rest = v - set(l)
if rest:
print "Cycle detected. The following vertices leads to a cycle:", list(rest)
else:
print l
data = [(None, 'F'),('C','E'),('B','D'),('A','B'),('E','H'),('A','C'),('D','E'),('F','G')]
dependency_sort(data)
data = [(None, 'F'),('C','E'),('B','D'),('A','B'),('E','H'),('A','C'),('D','E'),('F','G'),('E','A')]
dependency_sort(data) |
