You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@flink.apache.org by HungChang <un...@gmail.com> on 2015/02/14 12:26:21 UTC
Multiple sources shortest path
Hi,
In graph api there's an single source shortest path library.
DataSet<Vertex<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<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.
Re: Multiple sources shortest path
Posted by Sebastian <ss...@googlemail.com>.
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 <unicorn.banachi@gmail.com
> <ma...@gmail.com>> wrote:
>
> Hi,
>
> In graph api there's an single source shortest path library.
>
> DataSet<Vertex<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<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.
>
>
Re: Multiple sources shortest path
Posted by Vasiliki Kalavri <va...@gmail.com>.
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 <un...@gmail.com> wrote:
> Hi,
>
> In graph api there's an single source shortest path library.
>
> DataSet<Vertex<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<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.
>