CODEWITHSUNDEEP
pythonnetwork-programmingnetworkx
MrMimic
MrMimic

Reputation: 15

Find all paths from a node to leaves

I have a huge networkx graph object (1.8M nodes). I want to input this object with a given node and retrieve all paths going from this node to a leaf (a node connected with only one edge). By the way, the length of those paths is not fixed.

The only way I found doing that is:

    leaves = [node for node in G.nodes() if len(G.edges(node)) == 1]
    for leaf in leaves:
        paths =  [x for x in nx.all_simple_paths(G, 1, leaf, cutoff=None)]

However, it takes ages to loop over all possible leave and look for a path between the given node and the leaf.

Is there a way to get the result faster? Like in ontologies explosion used on information retrieval with ElasticSearch?

Thanks

Upvotes: 1

Views: 693

Answers (1)

Joel
Joel

Reputation: 23887

Add an edge from every leaf to a new node auxiliary. Find all paths from the given node to auxiliary. Then remove the final step of each path and you have all paths from the given node to a leaf.

Upvotes: 2

Related Questions