dependency_node_traversal

#!/usr/bin/python
edges = [[4, 6], [3, 4], [2, 3], [3, 5], [1, 2], [1, 3], [5, 6], [7, 2]]
result = []
edge_map = {}
start_nodes = []
# find start nodes
for edge in edges:
    if edge[0] not in start_nodes:
        # add to start_nodes
        start_nodes.append(edge[0])
reverse_edge = {}
# convert edge to map
for edge in edges:
    if edge[1] in start_nodes:
        # remove from start_nodes and add to edge_map
        start_nodes.remove(edge[1])
    if edge[0] not in edge_map:
        edge_map[edge[0]] = [edge[1]]
    else:            
        edge_map[edge[0]].append(edge[1])
    # add to reverse edge map
    if edge[1] not in reverse_edge:
        reverse_edge[edge[1]] = [edge[0]]
    else:
        reverse_edge[edge[1]].append(edge[0])

next_node = []
cur_node = []
# loop through all start nodes
while len(start_nodes) > 0:
    node = start_nodes.pop()
    cur_node.append(node)
    # if this node has dependency node
    if node in edge_map:
        depend_nodes = edge_map.pop(node)
        while len(depend_nodes) > 0:        
            depend_node = depend_nodes.pop()        
            # remove reverse edge
            reverse_edge[depend_node].remove(node)
            if len(reverse_edge[depend_node]) == 0:
                next_node.append(depend_node)

    if len(start_nodes) == 0:
        start_nodes = next_node
        next_node = []
        result.append(cur_node)
        cur_node = []
    
if len(edge_map) > 0:
    print("graph has cycle dependency!")
else:
    print(result)