parameters: (g)
docstring: Topologically sort a graph.
  
      The input g is a pygraphviz graph object representing a DAG. The function
      yields the vertices of g in an arbitrary order consistent with the edges,
      so that for any edge v->w, v is output before w.
docstring_summary: Topologically sort a graph.
docstring_tokens: Topologically sort a graph .
function: def toposort(g):
      """Topologically sort a graph.
  
      The input g is a pygraphviz graph object representing a DAG. The function
      yields the vertices of g in an arbitrary order consistent with the edges,
      so that for any edge v->w, v is output before w."""
  
      # Count the number of immediate predecessors *not yet output* for each
      # vertex. Initially this is simply their in-degrees.
      ideg = {v: g.in_degree(v) for v in g.nodes_iter()}
  
      # Set of vertices which can be output next, which is true if they have no
      # immediate predecessor that has not already been output.
      ready = {v for v, d in ideg.items() if d == 0}
  
      # Keep outputting vertices while we have any to output.
      while len(ready) > 0:
          v = next(iter(ready))
          yield v
          ready.remove(v)
  
          # Having output v, find each immediate successor w, and decrement its
          # 'ideg' value by 1, to indicate that one more of its predecessors has
          # now been output.
          for w in g.out_neighbors(v):
              ideg[w] -= 1
              if ideg[w] == 0:
                  # If that counter reaches zero, w is ready to output.
                  ready.add(w)
function_tokens: def toposort ( g ) : # Count the number of immediate predecessors *not yet output* for each # vertex. Initially this is simply their in-degrees. ideg = { v : g . in_degree ( v ) for v in g . nodes_iter ( ) } # Set of vertices which can be output next, which is true if they have no # immediate predecessor that has not already been output. ready = { v for v , d in ideg . items ( ) if d == 0 } # Keep outputting vertices while we have any to output. while len ( ready ) > 0 : v = next ( iter ( ready ) ) yield v ready . remove ( v ) # Having output v, find each immediate successor w, and decrement its # 'ideg' value by 1, to indicate that one more of its predecessors has # now been output. for w in g . out_neighbors ( v ) : ideg [ w ] -= 1 if ideg [ w ] == 0 : # If that counter reaches zero, w is ready to output. ready . add ( w )