Getting the root (head) of a DiGraph in networkx (

问题:

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!

回答1:

If by having "one root element" you mean your directed graph is a rooted tree, 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() 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.