CODEWITHSUNDEEP
pythonnetworkx
vineeshvs
vineeshvs

Reputation: 565

How to find the longest 10 paths in a Digraph with Python NetworkX?

Is there a way to find the top 10 long paths in a Digraph (with self-loops removed) made using NetworkX?

What I have tried so far, (cone is the Digraph with self-loops)

cone.remove_edges_from(cone.selfloop_edges())    
print nx.dag_longest_path(cone)

Note: In the terminology I have used, longest path means the path which passes through maximum number of nodes (unlike the standard definition where we consider the edge weight)

Upvotes: 3

Views: 1847

Answers (1)

Shir
Shir

Reputation: 1207

I can think of two attitudes:

  1. Find all paths in the graph, sort by length and take the 10 longest
  2. Find the longest path, then each time remove one edge in it, and find the longest path in the remaining graph. If you do this with all edges, and take the longest path from all tries, you should get the 2nd longest graph in the original graph. (extending this to 10 might be not very efficient, but it should work)

For the first idea (find all the paths and then choose the longest)- here is a naive example code. It is not the best efficiency you can get, but only an example-

import itertools
import networkx as nx

all_paths=[]

for (x,y) in itertools.combinations(DAG.nodes,2):
     for path in nx.all_simple_paths(DAG,x,y):
         all_paths.append(path)

all_paths.sort(key=len,reverse=True)
print all_paths[:10]

If you want a solution that is more efficient, you should probably use DFS in order to get all the paths in the graph. You can see some ideas here or here for example.

Regarding the second option (find second longest path using elimination of longest path edges), here is a code that demonstrates how to find the 2nd longest path:

longest_path = nx.dag_longest_path(DG)
print "longest path = " + longest_path

second_longest_paths = []
for i in range(len(longest_path) - 1):
    edge = (longest_path[i], longest_path[i + 1])
    DG.remove_edges_from([edge])
    second_longest_paths.append(nx.dag_longest_path(DG))
    DG.add_edges_from([edge])

second_longest_paths.sort(reverse=True, key=len)
print "second longest path = " + str(second_longest_paths[0])

But I think extending this to 10 longest paths might be a bit tricky (probably involves recursive over the process we just did, to find the second longest path in the graphs with the eliminated edges from level 2...).

Upvotes: 1

Related Questions