python networkx: simple way to get all simple paths from root to leaf

Question

I build a tree based on a directed graph. The source data is a series of parent child relationships in an SQL table. It's guaranteed to be a tree (which I verify anyway). I want the set of simple paths from the root to each leaf. The data is headers in an accounting "chart of accounts", and the paths will look like "Root -> Assets -> Current Assets -> Receivables -> Trade Debtors" where 'Trade Debtors' is the actual account.

At the moment, I collect the leaf IDs (the actual accounts) as I build the graph. I can do this because they are identified by certain attributes in the data. Then I iterate:

for leaf in detail_or_bank_accts:
    paths_to_detail_or_bank_accts.append(list(nx.all_simple_paths(G,0,leaf)))

But lucky for me that I know the leaf nodes. Is there a more elegant way of doing this?

Yes. I want to find all paths between node 0 and the set of nodes which are "leaves". My question is really: is there an easy way to either find the set of leaf nodes, or a one liner that generates all paths between the root of the tree and the leaves when I don't know the leaves. — Tim Richardson
comment on your current code - given that you know there is only one path, you probably want the code to stop calculating once it finds a path. Try shortest_path rather than all_simple_paths. — Joel

Joel Joel · Accepted Answer · 2018-01-04T01:25:43

I'm assuming you've got a DiGraph. It's pretty quick to figure out which nodes are leaves.

for node in G:
    if G.out_degree(node)==0: #it's a leaf
        paths.append(nx.shortest_path(G, root, node))

python networkx: simple way to get all simple paths from root to leaf

1 Answers