Shortest Path

User 459 | 7/14/2014, 1:22:54 AM

I am new to graphlab. I am checking on shortest path (SSSP) example but it only gives me the distance as output but not the path. Is there a way to get a path rather than distance.

Comments

User 14 | 7/14/2014, 2:35:53 AM

ShortestPath model has a get_path method, which allows you to query the shortest path to a given destination vertex. For more information please refer to the API docs below:

http://graphlab.com/products/create/docs/generated/graphlab.shortestpath.ShortestPathModel.html#graphlab.shortestpath.ShortestPathModel

Have a great day!


User 459 | 7/14/2014, 2:42:21 AM

Thanks Jay but i am looking in a distributed mode. Does the Python implementation of graphlab support distributed graph?


User 14 | 7/14/2014, 3:38:50 AM

Not yet, but it is definitely on the road map.


User 447 | 7/25/2014, 11:10:22 PM

my (dmcennis) fork has a djikstra algorithm on graphlab that can provide a good starting point for you that should work in distributed mode. May require some modification in the main method to get what you want and its raw graphlab - not graphlab create, but its pretty straightforward. ( https://github.com/dmcennis/graphlab master )


User 442 | 7/27/2014, 8:36:24 PM

I have modify the SSSP source so that it collects paths. Link for the code is https://github.com/kailashjoshi/graphlab/tree/master/apps/sssp_getPath

Let say your input data is

<pre class="CodeBlock"><code>3 2 4 3 2 0 3 5 3 6 7 6 2 8 8 9 8 11 10 11 2 1 2 3 3 4 0 2 5 3 6 3 6 7 8 2 9 8 11 8 11 10</code></pre>

and if you want to find all the shortest path from the source id 1, then the output will be as follow

<pre class="CodeBlock"><code>VID Distance Parentnode 3 2 '2' 0 2 '2' 2 1 '1' 9 3 '8' 7 4 '6' 10 4 '11' 11 3 '8' 1 0 '1' 6 3 '3' 5 3 '3' 4 3 '3' 8 2 '2'</code></pre>

I am new to both c++ and graphlab world, please let me know if you have any suggestions in the code. The program only captures single path for now but I am working on it so that the program also capture alternative path.


User 442 | 7/28/2014, 12:20:19 AM

Quick update, I have updated the code and repository. Now the program is able to collect alternative paths as well

Input data

<pre class="CodeBlock"><code>1 2 2 3 3 4 1 5 5 6 6 4</code></pre>

Output with alternative paths

<pre class="CodeBlock"><code>VID Distance ParentNodes 2 1 '1' 3 2 '2' 1 0 '1' 4 3 '3''6' 5 1 '1' 6 2 '2''5'</code></pre>


User 447 | 3/9/2015, 1:33:32 AM

@DannyBickson Please confirm you have the working repository I sent by email.


User 447 | 4/12/2015, 11:16:03 AM

Here is a link to the github repository I sent to Danny manually. Let me know if it works. The records should show the github upload with different content then currently included. If it doesn't or doesn't work, check back and I'll try something else.

https://drive.google.com/open?id=0Bx9PY06zuheNbDVEUTBCeUVqN1U&authuser=0