3

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)

vineeshvs
  • 479
  • 7
  • 32
  • 1
    Finding the longest path (which passes through each node exactly once) is an NP-hard problem. What are your expectations (complexity, ...) and how large a graph are you considering? – Anthony Labarre Mar 20 '19 at 13:36
  • @AnthonyLabarre The final objective is to divide (approximately) the longest 10 paths in the graph into three sections and get the signals in those nodes. The final graph will have more than 100 nodes (but can expect upto 1000 nodes at least later). – vineeshvs Mar 20 '19 at 13:43
  • @AnthonyLabarre Is it still an NP-hard problem even if we remove the cycles by topologically sorting the nodes? – vineeshvs Mar 20 '19 at 13:50
  • 1
    No, if you have a DAG (directed acyclic graph) then the problem becomes polynomial. Is this your case (your code snippet which uses `dag_longest_path` seems to suggest so)? Note that you cannot sort vertices topologically if the graph has a cycle, so I'm not sure how you intend to remove cycles (meaning it's possible but there are several ways to do that). – Anthony Labarre Mar 20 '19 at 14:09
  • I will be using DAG and will explore the ways to eliminate the cycles. (I convert HDL descriptions in Verilog to graphs. Will consider that also in short-listing the ways to eliminate the cycles). Thanks Prof. @AnthonyLabarre – vineeshvs Mar 22 '19 at 05:32

1 Answers1

1

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

Shir
  • 1,157
  • 13
  • 35
  • I have implemented method 1 and used Timsort in Python (https://www.geeksforgeeks.org/timsort/). Works for my task. Thanks @Shir. – vineeshvs Apr 19 '19 at 06:54