Re: Multiple sources shortest path

[Vasiliki Kalavri]

Hi,

you can certainly use a for-loop like this to run SSSP several times. Just make sure you return or store the result of the computation for each source, by adding a data sink e.g.:

for (id : Ids) {

          graph.run(new SingleSourceShortestPaths<Long>(id, maxIterations))

  .getVertices().print();

}

However, if you have a large amount of source nodes, executing one SSSP for each of them is probably not the most efficient way to go.

Instead, you could maybe write a custom multiple shortest paths program, where each node calculates distances for multiple sources in each iteration. In this case, the vertex value could be a vector of size equal to the number of input sources. 

Cheers,

V.

On 14 February 2015 at 12:26, HungChang <[hidden email]> wrote:

Hi,

In graph api there's an single source shortest path library.

DataSet<Vertex&lt;Long,Double>> singleSourceShortestPaths =
                graph.run(new SingleSourceShortestPaths<Long>(srcVertexId,
maxIterations)).getVertices();

For Multiple Source, would it be possible to run it for all nodes using
for-loop?
for example,

for(Node node: nodes){
 DataSet<Vertex&lt;Long,Double>> singleSourceShortestPaths =
                graph.run(new SingleSourceShortestPaths<Long>(node,
maxIterations)).getVertices();
}




--
View this message in context: http://apache-flink-incubator-user-mailing-list-archive.2336050.n4.nabble.com/Multiple-sources-shortest-path-tp729.html
Sent from the Apache Flink (Incubator) User Mailing List archive. mailing list archive at Nabble.com.

[Sebastian Schelter]

In general, all-pairs-shortest-paths is a non-scalable problem as it
produces output proportional to the square of the number of vertices in
a network.

--sebastian


On 15.02.2015 12:37, Vasiliki Kalavri wrote:

> Hi,
>
> you can certainly use a for-loop like this to run SSSP several times.
> Just make sure you return or store the result of the computation for
> each source, by adding a data sink e.g.:
>
> for (id : Ids) {
>            graph.run(new SingleSourceShortestPaths<Long>(id, maxIterations))
> .getVertices().print();
> }
>
> However, if you have a large amount of source nodes, executing one SSSP
> for each of them is probably not the most efficient way to go.
> Instead, you could maybe write a custom multiple shortest paths program,
> where each node calculates distances for multiple sources in each
> iteration. In this case, the vertex value could be a vector of size
> equal to the number of input sources.
>
> Cheers,
> V.
>
> On 14 February 2015 at 12:26, HungChang <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     Hi,
>
>     In graph api there's an single source shortest path library.
>
>     DataSet<Vertex&lt;Long,Double>> singleSourceShortestPaths =
>                      graph.run(new
>     SingleSourceShortestPaths<Long>(srcVertexId,
>     maxIterations)).getVertices();
>
>     For Multiple Source, would it be possible to run it for all nodes using
>     for-loop?
>     for example,
>
>     for(Node node: nodes){
>       DataSet<Vertex&lt;Long,Double>> singleSourceShortestPaths =
>                      graph.run(new SingleSourceShortestPaths<Long>(node,
>     maxIterations)).getVertices();
>     }
>
>
>
>
>     --
>     View this message in context:
>     http://apache-flink-incubator-user-mailing-list-archive.2336050.n4.nabble.com/Multiple-sources-shortest-path-tp729.html
>     Sent from the Apache Flink (Incubator) User Mailing List archive.
>     mailing list archive at Nabble.com.
>
>

[Hung]

Thank you for your reply.

True.
I didn't recognize the non-scalable problem before.
and also thanks Vasiliki for the suggestions of control flow and loop.