An efficient way to find all paths between two nodes in a non-cyclic directed graph
I want to find all paths between two nodes in a graph. I wrote a recursive function that finds all paths using a depth-first search algorithm. But for large plots this is very inefficient, so I cannot use it for my program.
I am thinking about implementing an iterative method for my problem . It will be a very long time for me. So did anyone know if this would make sense?
Is the iterative way more efficient in this case? Or is it possible to optimize the recursive method?
My current function:
function RecDFS(g::GenericGraph, visited)
nodes = out_neighbors(visited[length(visited)], g)
for i in nodes
if in(i,visited)
continue
end
if i.label == "End"
push!(visited,i)
println(visited) # print every path from the first node in visited to the node with the label End
pop!(visited)
break
end
# continue recursive..
for i in nodes
if (in(i, visited) || i.label == "End")
continue
end
push!(visited,i)
depthFirstSearchAllI(g, visited)
pop!(visited)
end
end
source to share
After some thought, I found a good solution for my problem. Take a look at this sample code:
function RecDFS(g::GenericGraph, visited)
nodes = out_neighbors(visited[length(visited)], g)
if(checkPath(visited))
for i in nodes
if in(i,visited)
continue
end
if i.label == "End"
push!(visited,i)
println(visited) # print every path from the first node in visited to the node with the label End
pop!(visited)
break
end
end
# continue recursive..
for i in nodes
if (in(i, visited) || i.label == "End")
continue
end
push!(visited,i)
depthFirstSearchAllI(g, visited)
pop!(visited)
end
end
end
All in all, I just added an additional if-statement. The function checkPath(visited)
returns true if the path is still valid. If the path (or portion of the path) is not valid, the function ends.
For my specific problem, this is a very good solution. It was 100x faster in my test run, and my largest instance of the problem only takes 15 seconds with 500 nodes and 16000 edges.
Many thanks to Ashkan Kzma and Rob for your help.
source to share
The problem you are trying to solve is actually NP-hard, which means there is no polynomial time algorithm for it!
So you can find some optimizations for your problem, but you can't get it up and running fast enough!
As with optimization, you can do the following. First of all, you mentioned in your question that your input is a DAG diagram and DAGs by definition have the following property:
In two different connected parts of the DAG, there are no paths between the two nodes.
so if you have a list of nodes that have a DAG chunk connected (this is achieved in polynomial time), you can easily cross out a lot of hopeless combinations.
As with creating your iterative program, you can easily use the stack. Just replace each recursive call with stack.push (node) and put the move part of your code after a while (the stack is not empty) and just put the nodes one by one if there are none. This should do it.
source to share
Perform a topological sort vertices in your availability group to get [v0, v1, ... , vn]
. Let's assume your start node is vs
your destination vt
. (If s > t
, then there are no ways)
Then, for each i
in, s+1 .. t
calculate the paths P(i)
from vs
to vi
as follows:
- If there is an edge
vs -> vi
, then one path (length 1) - Find all
j
such thats < j < i
there is an edgevj -> vi
. Add all paths obtained by selecting paths fromP(j)
and adding an edgevj -> vi
- Note. for this
i
there is no guarantee that there are any paths fromvs
tovi
As noted, there can be exponentially many paths, so the derivation of all paths cannot be done less exponentially at all. However, using this approach, you can count the number of paths in linear time.
source to share