[erlang-questions] 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 <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/
> questions/7834702/find-all-possible-paths-from-one-
> vertex-in-a-directed-cyclic-graph-in-erlang
>
> best regards,
> Vlad
>
>
> On Sun, Apr 22, 2018 at 10:33 PM, bengt <cean.ebengt@REDACTED> 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
>> erlang-questions@REDACTED
>> http://erlang.org/mailman/listinfo/erlang-questions
>>
>
>
> _______________________________________________
> erlang-questions mailing list
> erlang-questions@REDACTED
> http://erlang.org/mailman/listinfo/erlang-questions
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20180422/5a2871f1/attachment.htm>