CODEWITHSUNDEEP
pythonnetworkx
Tim Richardson
Tim Richardson

Reputation: 7251

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

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?

Upvotes: 2

Views: 4025

Answers (1)

Joel
Joel

Reputation: 23887

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

Upvotes: 3

Related Questions