Logo Search packages:      
Sourcecode: python-networkx version File versions  Download package

def networkx::paths::topological_sort (   G  ) 

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):


Generated by  Doxygen 1.6.0   Back to index