0

I want to compute all the paths in directed acyclic graph from multiple inputs (x1, .., xn) to one output. The graph has the same depth which d and the inputs come to the graph at the same time (the shape is like Artificial Neural Networks with many inputs and one output). Could you please tell me if there are some algorithms that can compute such paths?

Regards,

S.AMEEN
  • 1,461
  • 4
  • 16
  • 23

1 Answers1

0

1) Run a depth first search, starting at the output and traversing each edge in the reverse direction, to find all nodes from which you can get to the output.

2) Delete all nodes from which you cannot get to the output.

3) Run a recursive search on the modified graph, starting at each input node in turn, to find all paths to the output.

Because you have removed all the dead ends, this should produce all the paths as fast as you can output them, but you should be warned that there may be a very large number of different paths, even from small graphs - a graph the shape of a ladder and length n may have about 2^n paths - at each rung you have a choice as to whether to go up the left or the right hand side of the ladders, so there are 2^(number of rungs) different paths.

mcdowella
  • 19,301
  • 2
  • 19
  • 25
  • Many thanks for explaining, could you please tell me if there any implementation in python for doing such idea. – S.AMEEN Sep 01 '15 at 19:11
  • I don't know of any myself, but a quick search suggests that http://stackoverflow.com/questions/606516/python-graph-library might give some pointers. The sorts of searches I suggest are worth writing just for practice if you are not familiar with them. – mcdowella Sep 02 '15 at 04:28