Getting the root (head) of a DiGraph in networkx (Python)
Question: I'm trying to use `networkx` to do some graph representation in a project, and
I'm not sure how to do a few things that should be simple. I created a
directed graph with a bunch of nodes and edges, such that there is only one
root element in this graph. Now, what I'd like to do is start at the root, and
then iterate through the children of each element and extract some information
from them. How do I get the root element of this DiGraph?

So it would be something like this:

    
    
    #This is NOT real code, just pseudopython to convey the general intent of what I'd like to do
    
        root = myDiGraph.root()
        for child in root.children():
            iterateThroughChildren(child)
    
    def iterateThroughChildren(parent):
        if parent.hasNoChildren(): return
        for child in parent.children():
            //do something
            //
            iterateThroughChildren(child)
    

I didn't see anything in the documentation that suggested an easy way to
retrieve the root of a DiGraph -- am I supposed to infer this manually? :O I
tried getting `iter(myDiGraph)` with the hope that it would iterate starting
at the root, but the order seems to be random... :\

Help will be appreciated, thanks!


Answer: If by having "one root element" you mean your directed graph is a rooted tree,
(http://en.wikipedia.org/wiki/Tree_%28graph_theory) then the root will be the
only node with zero in-degree.

You can find that node in linear time (in the number of nodes) with:

    
    
    In [1]: import networkx as nx
    
    In [2]: G=nx.balanced_tree(2,3,create_using=nx.DiGraph()) # tree rooted at 0
    
    In [3]: [n for n,d in G.in_degree().items() if d==0] 
    Out[3]: [0]
    

Or you could use a topological sort (root is first item):

    
    
    In [4]: nx.topological_sort(G)
    Out[4]: [0, 1, 3, 8, 7, 4, 9, 10, 2, 5, 11, 12, 6, 13, 14]
    

Alternatively it might be faster to start with a given (random) node and
follow the predecessors until you find a node with no predecessors.

