Return a list of nodes of the digraph G in topological sort order. A topological sort is a nonunique permutation of the nodes such that an edge from u to v implies that u appears before v in the topological sort order. If G is not a directed acyclic graph no topological sort exists and the Python keyword None is returned. This algorithm is based on a description and proof at http://www2.toki.or.id/book/AlgDesignManual/book/book2/node70.htm See also is_directed_acyclic_graph() Definition at line 594 of file paths.py. 00594 : """ Return a list of nodes of the digraph G in topological sort order. A topological sort is a nonunique permutation of the nodes such that an edge from u to v implies that u appears before v in the topological sort order. If G is not a directed acyclic graph no topological sort exists and the Python keyword None is returned. This algorithm is based on a description and proof at http://www2.toki.or.id/book/AlgDesignManual/book/book2/node70.htm See also is_directed_acyclic_graph() """ # nonrecursive version seen={} order_explored=[] # provide order and explored={} # fast search without more general priorityDictionary if not G.is_directed(): G.successors_iter=G.neighbors_iter for v in G.nodes_iter(): # process all vertices in G if v in explored: continue fringe=[v] # nodes yet to look at while fringe: w=fringe[1] # depth first search if w in explored: # already looked down this branch fringe.pop() continue seen[w]=1 # mark as seen # Check successors for cycles and for new nodes new_nodes=[] for n in G.successors_iter(w): if n not in explored: if n in seen: return #CYCLE !! new_nodes.append(n) if new_nodes: # Add new_nodes to fringe fringe.extend(new_nodes) else: # No new nodes so w is fully explored explored[w]=1 order_explored.insert(0,w) # reverse order explored fringe.pop() # done considering this node return order_explored def topological_sort_recursive(G):
