Welcome, guest | Sign In | My Account | Store | Cart
```#!/usr/bin/env python3.2

def sort_direct_acyclic_graph(edge_list) :
# edge_set is consummed, need a copy
edge_set = set([tuple(i) for i in edge_list])

# node_list will contain the ordered nodes
node_list = list()

# source_set is the set of nodes with no incomming edges
node_from_list, node_to_list = zip(* edge_set)
source_set = set(node_from_list) - set(node_to_list)

while len(source_set) != 0 :
# pop node_from off source_set and insert it in node_list
node_from = source_set.pop()
node_list.append(node_from)

# find nodes which have a common edge with node_from
from_selection = [e for e in edge_set if e[0] == node_from]
for edge in from_selection :
# remove the edge from the graph
node_to = edge[1]

# if node_to don't have any remaining incomming edge :
to_selection = [e for e in edge_set if e[1] == node_to]
if len(to_selection) == 0 :

if len(edge_set) != 0 :
raise IndexError # not a direct acyclic graph
else :
return node_list

u = [
['a', 'b'], # a -> b, etc.
['a', 'c'],
['b', 'e'],
['c', 'd'],
['b', 'd'],
['e', 'f'],
['c', 'f'],
]

>>> sort_direct_acyclic_graph(u)
['a', 'c', 'b', 'e', 'd', 'f']
```

#### Diff to Previous Revision

```--- revision 8 2013-01-08 19:17:52
+++ revision 9 2013-03-06 19:21:11
@@ -12,7 +12,7 @@
source_set = set(node_from_list) - set(node_to_list)

while len(source_set) != 0 :
-		# pop node_from of source_set and insert it in node_list
+		# pop node_from off source_set and insert it in node_list
node_from = source_set.pop()
node_list.append(node_from)

```