0

My problem is all simple paths problem on hallucinogens. I need to find all the paths between two nodes on the basis of the edges and not nodes

I found this as a solution but this approach is way too slow considering the size of my actual graph. I would like to know what are the optimizations that could be done to better this. I have modified the code given in the link to use deque() This is not of too much help either 

  g=nx.MultiGraph()
  g.add_edge(1,1,key='a')
  g.add_edge(1,2,key='b')
  g.add_edge(2,4,key='c')
  g.add_edge(2,4,key='d')
  g.add_edge(3,2,key='e')
  g.add_edge(3,3,key='f')
  g.add_edge(1,3,key='g')
  g.add_edge(1,5,key='h')
  g.add_edge(5,5,key='i')
The Answer for all_path(1,4): 

Path: 0 --> [(1, 1, 'a'), (1, 2, 'b'), (2, 4, 'c')]
Path: 1 --> [(1, 1, 'a'), (1, 2, 'b'), (2, 4, 'd')]
Path: 2 --> [(1, 1, 'a'), (1, 3, 'g'), (3, 2, 'e'), (2, 4, 'c')]
Path: 3 --> [(1, 1, 'a'), (1, 3, 'g'), (3, 2, 'e'), (2, 4, 'd')]
Path: 4 --> [(1, 1, 'a'), (1, 3, 'g'), (3, 3, 'f'), (3, 2, 'e'), (2, 4, 'c')]
Path: 5 --> [(1, 1, 'a'), (1, 3, 'g'), (3, 3, 'f'), (3, 2, 'e'), (2, 4, 'd')]
Path: 6 --> [(1, 2, 'b'), (2, 4, 'c')]
Path: 7 --> [(1, 2, 'b'), (2, 4, 'd')]
Path: 8 --> [(1, 3, 'g'), (3, 2, 'e'), (2, 4, 'c')]
Path: 9 --> [(1, 3, 'g'), (3, 2, 'e'), (2, 4, 'd')]
Path: 10 --> [(1, 3, 'g'), (3, 3, 'f'), (3, 2, 'e'), (2, 4, 'c')]
Path: 11 --> [(1, 3, 'g'), (3, 3, 'f'), (3, 2, 'e'), (2, 4, 'd')]

Community
  • 1
  • 1
Lelouch Lamperouge
  • 8,171
  • 8
  • 49
  • 60
  • You may like to describe the size of your graph. Is the usage of `multigraph` absolutely necessary? – eat Apr 07 '11 at 07:02
  • @eat, Absolutely, there are a quite a few situations where there are more than one edge between between 2 neighbors – Lelouch Lamperouge Apr 08 '11 at 00:23
  • @Ashish, Can't. DFS needs to be recursive. The program stack would blow up – Lelouch Lamperouge Apr 08 '11 at 00:24
  • So, how many nodes and edges? Do you have any estimation on the number possible paths? Why DFS needs to be recursive? Won't a own queue be sufficient? Al tough I don't know whether BFS versus DFS makes any difference, since you need all paths. Just an idea; try to find out paths from simple graph and then add those multi edges. – eat Apr 08 '11 at 07:36
  • There are about 2.5 million edges. I am unable to estimate the number of paths. I am currently using an iterative BFS for solving this problem. As a modification, I am limiting the path length to 20 hops, so it works fine for now. But I might have to something about it very soon – Lelouch Lamperouge Apr 09 '11 at 01:10

1 Answers1

0

Try to build new graph with where current edges are transformed into nodes and there is an edge beetween two nodes if we can use their corresponding edges consequently in a path. After it you can solve your problem with DFS.

Artem Volkhin
  • 1,362
  • 8
  • 22