<div dir="ltr"><div class="gmail_default" style="font-family:verdana,sans-serif">Hi Bengt,</div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div class="gmail_default" style="font-family:verdana,sans-serif">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:</div><div class="gmail_default" style="font-family:verdana,sans-serif"><br></div><div class="gmail_default" style="font-family:verdana,sans-serif">-Vasu</div><div class="gmail_default" style="font-family:verdana,sans-serif"><pre style="background-color:rgb(43,43,43);color:rgb(169,183,198);font-family:Menlo;font-size:9pt"><br>-spec get_short_path(<span style="color:rgb(152,118,170)">G</span>, <span style="color:rgb(152,118,170)">V1</span>, <span style="color:rgb(152,118,170)">V2</span>) -> <span style="color:rgb(152,118,170)">Vertices </span>| 'false' <span style="color:rgb(204,120,50);font-weight:bold">when<br></span><span style="color:rgb(204,120,50);font-weight:bold"> </span><span style="color:rgb(152,118,170)">G </span>:: graph(),<br> <span style="color:rgb(152,118,170)">V1 </span>:: vertex(),<br> <span style="color:rgb(152,118,170)">V2 </span>:: vertex(),<br> <span style="color:rgb(152,118,170)">Vertices </span>:: [vertex(),...]<span style="color:rgb(204,120,50);font-weight:bold">.<br></span><span style="color:rgb(204,120,50);font-weight:bold"><br></span>get_short_path(<span style="color:rgb(152,118,170)">G</span>, <span style="color:rgb(152,118,170)">V1</span>, <span style="color:rgb(152,118,170)">V2</span>) -><br> <span style="color:rgb(152,118,170)">T </span>= new(),<br> add_vertex(<span style="color:rgb(152,118,170)">T</span>, <span style="color:rgb(152,118,170)">V1</span>),<br> <span style="color:rgb(152,118,170)">Q </span>= queue:new(),<br> <span style="color:rgb(152,118,170)">Q1 </span>= queue_out_neighbours(<span style="color:rgb(152,118,170)">V1</span>, <span style="color:rgb(152,118,170)">G</span>, <span style="color:rgb(152,118,170)">Q</span>),<br> <span style="color:rgb(152,118,170)">L </span>= spath(<span style="color:rgb(152,118,170)">Q1</span>, <span style="color:rgb(152,118,170)">G</span>, <span style="color:rgb(152,118,170)">V2</span>, <span style="color:rgb(152,118,170)">T</span>),<br> delete(<span style="color:rgb(152,118,170)">T</span>),<br> <span style="color:rgb(152,118,170)">L</span><span style="color:rgb(204,120,50);font-weight:bold">.<br></span><span style="color:rgb(204,120,50);font-weight:bold"> </span></pre></div></div><div class="gmail_extra"><br clear="all"><div><div class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><p style="margin:0px;font-family:Papyrus"><span style="letter-spacing:0px"><b><font size="2">Vasu Dasari</font></b></span></p></div></div></div>
<br><div class="gmail_quote">On Sun, Apr 22, 2018 at 5:44 PM, Vlad Dumitrescu <span dir="ltr"><<a href="mailto:vladdu55@gmail.com" target="_blank">vladdu55@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi Bengt,<div><br></div><div>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. </div><div><br></div><div>Someone asked the same thing before at <a href="https://stackoverflow.com/questions/7834702/find-all-possible-paths-from-one-vertex-in-a-directed-cyclic-graph-in-erlang" target="_blank">https://stackoverflow.com/<wbr>questions/7834702/find-all-<wbr>possible-paths-from-one-<wbr>vertex-in-a-directed-cyclic-<wbr>graph-in-erlang</a></div><div><br></div><div>best regards,</div><div>Vlad</div><div><br></div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Apr 22, 2018 at 10:33 PM, bengt <span dir="ltr"><<a href="mailto:cean.ebengt@gmail.com" target="_blank">cean.ebengt@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Greetings,<br>
<br>
The digraph module has get_path/3 to find one path from V1 to V2. Is there a way to find all paths?<br>
I considered removing the found path and trying again, but that does not work when paths overlap.<br>
<br>
Best Wishes,<br>
bengt<br>
______________________________<wbr>_________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org" target="_blank">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" rel="noreferrer" target="_blank">http://erlang.org/mailman/list<wbr>info/erlang-questions</a><br>
</blockquote></div><br></div>
</div></div><br>______________________________<wbr>_________________<br>
erlang-questions mailing list<br>
<a href="mailto:erlang-questions@erlang.org">erlang-questions@erlang.org</a><br>
<a href="http://erlang.org/mailman/listinfo/erlang-questions" rel="noreferrer" target="_blank">http://erlang.org/mailman/<wbr>listinfo/erlang-questions</a><br>
<br></blockquote></div><br></div>