Wanted: A method to find all paths from V1 to V2 using digraph module

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Wanted: A method to find all paths from V1 to V2 using digraph module

bengt e
Greetings,

The digraph module has get_path/3 to find one path from V1 to V2. Is there a way to find all paths?
I considered removing the found path and trying again, but that does not work when paths overlap.

Best Wishes,
bengt
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Wanted: A method to find all paths from V1 to V2 using digraph module

Vlad Dumitrescu-2
Hi Bengt,

The solution is to do a search starting from one of the vertices and keep track of the found paths (saving a stack of already traversed vertices and watching out for cycles), but in the worst case it is an O(n!) algorithm. Even in non-pathological cases, it is easy to get an untractable number of solutions as the complexity is exponential. 


best regards,
Vlad


On Sun, Apr 22, 2018 at 10:33 PM, bengt <[hidden email]> wrote:
Greetings,

The digraph module has get_path/3 to find one path from V1 to V2. Is there a way to find all paths?
I considered removing the found path and trying again, but that does not work when paths overlap.

Best Wishes,
bengt
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Wanted: A method to find all paths from V1 to V2 using digraph module

Vasu Dasari
Hi Bengt,

Can you check digraph.erl source code for function get_short_path/1, which might give you some ideas of retrieving list of paths between vertices:

-Vasu

-spec get_short_path(G, V1, V2) -> Vertices | 'false' when
G :: graph(),
V1 :: vertex(),
V2 :: vertex(),
Vertices :: [vertex(),...].

get_short_path(G, V1, V2) ->
T = new(),
add_vertex(T, V1),
Q = queue:new(),
Q1 = queue_out_neighbours(V1, G, Q),
L = spath(Q1, G, V2, T),
delete(T),
L.

Vasu Dasari


On Sun, Apr 22, 2018 at 5:44 PM, Vlad Dumitrescu <[hidden email]> wrote:
Hi Bengt,

The solution is to do a search starting from one of the vertices and keep track of the found paths (saving a stack of already traversed vertices and watching out for cycles), but in the worst case it is an O(n!) algorithm. Even in non-pathological cases, it is easy to get an untractable number of solutions as the complexity is exponential. 


best regards,
Vlad


On Sun, Apr 22, 2018 at 10:33 PM, bengt <[hidden email]> wrote:
Greetings,

The digraph module has get_path/3 to find one path from V1 to V2. Is there a way to find all paths?
I considered removing the found path and trying again, but that does not work when paths overlap.

Best Wishes,
bengt
_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Wanted: A method to find all paths from V1 to V2 using digraph module

Jesper Louis Andersen-2
In reply to this post by Vlad Dumitrescu-2
On Sun, Apr 22, 2018 at 11:45 PM Vlad Dumitrescu <[hidden email]> wrote:
Hi Bengt,

The solution is to do a search starting from one of the vertices and keep track of the found paths (saving a stack of already traversed vertices and watching out for cycles), but in the worst case it is an O(n!) algorithm. Even in non-pathological cases, it is easy to get an untractable number of solutions as the complexity is exponential. 


The obvious algorithm is a breadth-first-search keeping track of the possible paths in each vertex. But if the number of edges are high, then this has to visit all the edges.

It might be possible, given assumptions about cycles, to use a variant of (Floyd-)Warshall's algorithm. Build an "ascendancy matrix", but rather than processing boolean bits in each matrix cell, track the (number of) paths. If you can pull this off, then we are closer to something like O(n^3), though there are obvious flaws given cycles. So it may be you would need to analyze the incoming data and make sure the graph has a certain structure.

Is the graph directed or undirected? Are all the paths simple (i.e., they are not allowed to cycle?). I'd also look into graph cuts where you can divide the graph into two halves, one containing S and one containing T. It could be the solution count can be based on that number.


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Wanted: A method to find all paths from V1 to V2 using digraph module

bengt e
The origin of this is the problem https://leetcode.com/problems/cheapest-flights-within-k-stops/description/
so yes it is a very simple structure with lots of assumptions that can be made.
Since it should be possible to write the code in 30 minutes I thought there might be a short-cut (Professor Layton solution :-)
I will do it the long way instead. Hopefully in just one day. Should be good for me anyway.

bengt

On 23 Apr 2018, at 15:56, Jesper Louis Andersen <[hidden email]> wrote:

On Sun, Apr 22, 2018 at 11:45 PM Vlad Dumitrescu <[hidden email]> wrote:
Hi Bengt,

The solution is to do a search starting from one of the vertices and keep track of the found paths (saving a stack of already traversed vertices and watching out for cycles), but in the worst case it is an O(n!) algorithm. Even in non-pathological cases, it is easy to get an untractable number of solutions as the complexity is exponential. 


The obvious algorithm is a breadth-first-search keeping track of the possible paths in each vertex. But if the number of edges are high, then this has to visit all the edges.

It might be possible, given assumptions about cycles, to use a variant of (Floyd-)Warshall's algorithm. Build an "ascendancy matrix", but rather than processing boolean bits in each matrix cell, track the (number of) paths. If you can pull this off, then we are closer to something like O(n^3), though there are obvious flaws given cycles. So it may be you would need to analyze the incoming data and make sure the graph has a certain structure.

Is the graph directed or undirected? Are all the paths simple (i.e., they are not allowed to cycle?). I'd also look into graph cuts where you can divide the graph into two halves, one containing S and one containing T. It could be the solution count can be based on that number.



_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions
Reply | Threaded
Open this post in threaded view
|

Re: Wanted: A method to find all paths from V1 to V2 using digraph module

Jesper Louis Andersen-2
That problem is just Floyd-Warshall for O(n^3) runtime. If you accept O(n^3 * lg n) then there is a brilliant algorithm based on successive matrix multiplication (power ranking) in a matrix multiplication in which the +/2 operation is min/2. and the */2 operation is +/2. See for instance the code in Paulson's ML for the working programmer, Chapter 7: http://www.cl.cam.ac.uk/~lp15/MLbook/programs/sample7.sml Look for MatrixZSP, ZSP and PathZSP in that code listing.



On Mon, Apr 23, 2018 at 4:36 PM bengt <[hidden email]> wrote:
The origin of this is the problem https://leetcode.com/problems/cheapest-flights-within-k-stops/description/
so yes it is a very simple structure with lots of assumptions that can be made.
Since it should be possible to write the code in 30 minutes I thought there might be a short-cut (Professor Layton solution :-)
I will do it the long way instead. Hopefully in just one day. Should be good for me anyway.


bengt


On 23 Apr 2018, at 15:56, Jesper Louis Andersen <[hidden email]> wrote:

On Sun, Apr 22, 2018 at 11:45 PM Vlad Dumitrescu <[hidden email]> wrote:
Hi Bengt,

The solution is to do a search starting from one of the vertices and keep track of the found paths (saving a stack of already traversed vertices and watching out for cycles), but in the worst case it is an O(n!) algorithm. Even in non-pathological cases, it is easy to get an untractable number of solutions as the complexity is exponential. 


The obvious algorithm is a breadth-first-search keeping track of the possible paths in each vertex. But if the number of edges are high, then this has to visit all the edges.

It might be possible, given assumptions about cycles, to use a variant of (Floyd-)Warshall's algorithm. Build an "ascendancy matrix", but rather than processing boolean bits in each matrix cell, track the (number of) paths. If you can pull this off, then we are closer to something like O(n^3), though there are obvious flaws given cycles. So it may be you would need to analyze the incoming data and make sure the graph has a certain structure.

Is the graph directed or undirected? Are all the paths simple (i.e., they are not allowed to cycle?). I'd also look into graph cuts where you can divide the graph into two halves, one containing S and one containing T. It could be the solution count can be based on that number.


_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions

_______________________________________________
erlang-questions mailing list
[hidden email]
http://erlang.org/mailman/listinfo/erlang-questions