[erlang-questions] Wanted: A method to find all paths from V1 to V2 using digraph module

[Vlad Dumitrescu]

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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://erlang.org/pipermail/erlang-questions/attachments/20180422/bc497dac/attachment.htm>