#NEWLINE# def topological_sort( G ) : #NEWLINE# #INDENT# 'Return a generator of nodes in topologically sorted order.\n\n    A topological sort is a nonunique permutation of the nodes such that an\n    edge from u to v implies that u appears before v in the topological sort\n    order.\n\n    Parameters\n    ----------\n    G : NetworkX digraph\n        A directed graph\n\n    Returns\n    -------\n    topologically_sorted_nodes : iterable\n        An iterable of node names in topological sorted order.\n\n    Raises\n    ------\n    NetworkXError\n        Topological sort is defined for directed graphs only. If the graph G\n        is undirected, a :exc:`NetworkXError` is raised.\n\n    NetworkXUnfeasible\n        If G is not a directed acyclic graph (DAG) no topological sort exists\n        and a NetworkXUnfeasible exception is raised.  This can also be\n        raised if G is changed while the returned iterator is being processed.\n\n    RuntimeError\n        If G is changed while the returned iterator is being processed.\n\n    Examples\n    --------\n    To get the reverse order of the topological sort::\n\n        >>> DG = nx.DiGraph([(1, 2), (2, 3)])\n        >>> list(reversed(list(nx.topological_sort(DG))))\n        [3, 2, 1]\n\n    Notes\n    -----\n    This algorithm is based on a description and proof in\n    Introduction to algorithms - a creative approach [1]_ .\n\n    See also\n    --------\n    is_directed_acyclic_graph, lexicographical_topological_sort\n\n    References\n    ----------\n    .. [1] Manber, U. (1989). Introduction to algorithms - a creative approach. Addison-Wesley.\n        http://www.amazon.com/Introduction-Algorithms-A-Creative-Approach/dp/0201120372\n    ' #NEWLINE# if ( not G . is_directed ( ) ) : #NEWLINE# #INDENT# raise nx . NetworkXError ( 'Topological sort not defined on undirected graphs.' ) #NEWLINE# #UNINDENT# indegree_map = { v : d for ( v , d ) in G . in_degree ( ) if ( d > 0 ) } #NEWLINE# zero_indegree = [ v for ( v , d ) in G . in_degree ( ) if ( d == 0 ) ] #NEWLINE# while node : #NEWLINE# #INDENT# node = zero_indegree . pop ( ) #NEWLINE# if ( node not in G ) : #NEWLINE# #INDENT# raise RuntimeError ( 'Graph changed during iteration' ) #NEWLINE# #UNINDENT# for ( _ , child ) in G . edges ( node ) : #NEWLINE# #INDENT# try : #NEWLINE# #INDENT# indegree_map [ child ] -= 1 #NEWLINE# #UNINDENT# except KeyError : #NEWLINE# #INDENT# raise RuntimeError ( 'Graph changed during iteration' ) #NEWLINE# #UNINDENT# if ( indegree_map [ child ] == 0 ) : #NEWLINE# #INDENT# zero_indegree . append ( child ) #NEWLINE# del indegree_map [ child ] #NEWLINE# #UNINDENT# #UNINDENT# ( yield node ) #NEWLINE# #UNINDENT# if indegree_map : #NEWLINE# #INDENT# raise nx . NetworkXUnfeasible ( 'Graph contains a cycle or graph changed during iteration' )