[erlang-questions] Wanted: A method to find all paths from V1 to V2 using digraph module
Sun Apr 22 23:49:59 CEST 2018
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:
-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(),
Q = queue:new(),
Q1 = queue_out_neighbours(V1, G, Q),
L = spath(Q1, G, V2, T),
On Sun, Apr 22, 2018 at 5:44 PM, Vlad Dumitrescu <vladdu55@REDACTED> 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.
> Someone asked the same thing before at https://stackoverflow.com/
> best regards,
> On Sun, Apr 22, 2018 at 10:33 PM, bengt <cean.ebengt@REDACTED> wrote:
>> 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,
>> erlang-questions mailing list
> erlang-questions mailing list
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the erlang-questions