You are viewing a plain text version of this content. The canonical link for it is here.
Posted to user@spark.apache.org by Brian Wilson <br...@gmail.com> on 2016/10/24 13:11:41 UTC
Shortest path with directed and weighted graphs
I have been looking at the ShortestPaths function inbuilt with Spark here <https://github.com/apache/spark/blob/master/graphx/src/main/scala/org/apache/spark/graphx/lib/ShortestPaths.scala>.
Am I correct in saying there is no support for weighted graphs with this function? By that I mean that it assumes all edges carry a weight = 1
Many thanks
Brian
Re: java.lang.NoSuchMethodError - GraphX
Posted by Brian Wilson <br...@gmail.com>.
I have discovered that this dijkstra's function was written for scala 1.6. The remainder of my code is 2.11.
I have checked the functions within the dijkstra function and can’t see any that are illegal. For example `mapVertices`, `aggregateMessages` and `outerJoinVertices` are all being used correctly.
What else could this be?
Thanks
Brian
> On 25 Oct 2016, at 08:47, Brian Wilson <br...@gmail.com> wrote:
>
> Thank you Michael! This looks perfect but I have a `NoSuchMethodError` that I cannot understand.
>
> I am trying to implement a weighted shortest path algorithm from your `Spark GraphX in Action` book. The part in question is Listing 6.4 "Executing the shortest path algorithm that uses breadcrumbs" from Chapter 6 [here][1].
>
> I have my own graph that I create from two RDDs. There are `344436` vertices and `772983` edges. I can perform an unweighted shortest path computation using the native GraphX library and I'm confident in the graph construction.
>
> In this case I use their Dijkstra's implementation as follows:
>
> val my_graph: Graph[(Long),Double] = Graph.apply(verticesRDD, edgesRDD).cache()
>
> def dijkstra[VD](g:Graph[VD,Double], origin:VertexId) = {
> var g2 = g.mapVertices(
> (vid,vd) => (false, if (vid == origin) 0 else Double.MaxValue,
> List[VertexId]()))
>
> for (i <- 1L to g.vertices.count-1) {
> val currentVertexId =
> g2.vertices.filter(!_._2._1)
> .fold((0L,(false,Double.MaxValue,List[VertexId]())))((a,b) =>
> if (a._2._2 < b._2._2) a else b)
> ._1
>
> val newDistances = g2.aggregateMessages[(Double,List[VertexId])](
> ctx => if (ctx.srcId == currentVertexId)
> ctx.sendToDst((ctx.srcAttr._2 + ctx.attr,
> ctx.srcAttr._3 :+ ctx.srcId)),
> (a,b) => if (a._1 < b._1) a else b)
>
> g2 = g2.outerJoinVertices(newDistances)((vid, vd, newSum) => {
> val newSumVal =
> newSum.getOrElse((Double.MaxValue,List[VertexId]()))
> (vd._1 || vid == currentVertexId,
> math.min(vd._2, newSumVal._1),
> if (vd._2 < newSumVal._1) vd._3 else newSumVal._2)})
> }
>
> g.outerJoinVertices(g2.vertices)((vid, vd, dist) =>
> (vd, dist.getOrElse((false,Double.MaxValue,List[VertexId]()))
> .productIterator.toList.tail))
> }
>
> // Path Finding - random node from which to find all paths
> val v1 = 4000000028222916L
>
> I then call their function with my graph and a random vertex ID. Previously I had issues with `v1` not being recognised as `long` type and the `L` suffix solved this.
>
> val results = dijkstra(my_graph, 1L).vertices.map(_._2).collect
>
> println(results)
>
> However, this returns the following:
>
> Error: Exception in thread "main" java.lang.NoSuchMethodError: scala.runtime.ObjectRef.create(Ljava/lang/Object;)Lscala/runtime/ObjectRef;
> at GraphX$.dijkstra$1(GraphX.scala:51)
> at GraphX$.main(GraphX.scala:85)
> at GraphX.main(GraphX.scala)
> at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
> at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
> at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
> at java.lang.reflect.Method.invoke(Method.java:498)
> at org.apache.spark.deploy.SparkSubmit$.org$apache$spark$deploy$SparkSubmit$$runMain(SparkSubmit.scala:731)
> at org.apache.spark.deploy.SparkSubmit$.doRunMain$1(SparkSubmit.scala:181)
> at org.apache.spark.deploy.SparkSubmit$.submit(SparkSubmit.scala:206)
> at org.apache.spark.deploy.SparkSubmit$.main(SparkSubmit.scala:121)
> at org.apache.spark.deploy.SparkSubmit.main(SparkSubmit.scala)
>
> Line 51 refers to the line `var g2 = g.mapVertices(`
> Line 85 refers to the line `val results = dijkstra(my_graph, 1L).vertices.map(_._2).collect`
>
> What method is this exception referring to? I am able to package with `sbt` without error and I canno see what method I am calling whcih does not exist.
>
> Many thanks!
>
> Brian
>
> [1]: https://www.manning.com/books/spark-graphx-in-action#downloads <https://www.manning.com/books/spark-graphx-in-action#downloads>
>
>> On 24 Oct 2016, at 16:54, Michael Malak <michaelmalak@yahoo.com <ma...@yahoo.com>> wrote:
>>
>> Chapter 6 of my book implements Dijkstra's Algorithm. The source code is available to download for free. https://www.manning.com/books/spark-graphx-in-action <https://www.manning.com/books/spark-graphx-in-action>
>>
>>
>>
>>
>> From: Brian Wilson <brian.wilson.bel@gmail.com <ma...@gmail.com>>
>> To: user@spark.apache.org <ma...@spark.apache.org>
>> Sent: Monday, October 24, 2016 7:11 AM
>> Subject: Shortest path with directed and weighted graphs
>>
>> I have been looking at the ShortestPaths function inbuilt with Spark here <https://github.com/apache/spark/blob/master/graphx/src/main/scala/org/apache/spark/graphx/lib/ShortestPaths.scala>.
>>
>> Am I correct in saying there is no support for weighted graphs with this function? By that I mean that it assumes all edges carry a weight = 1
>>
>> Many thanks
>>
>> Brian
>>
>>
>
Re: java.lang.NoSuchMethodError - GraphX
Posted by Brian Wilson <br...@gmail.com>.
Thank you Michael! This looks perfect but I have a `NoSuchMethodError` that I cannot understand.
I am trying to implement a weighted shortest path algorithm from your `Spark GraphX in Action` book. The part in question is Listing 6.4 "Executing the shortest path algorithm that uses breadcrumbs" from Chapter 6 [here][1].
I have my own graph that I create from two RDDs. There are `344436` vertices and `772983` edges. I can perform an unweighted shortest path computation using the native GraphX library and I'm confident in the graph construction.
In this case I use their Dijkstra's implementation as follows:
val my_graph: Graph[(Long),Double] = Graph.apply(verticesRDD, edgesRDD).cache()
def dijkstra[VD](g:Graph[VD,Double], origin:VertexId) = {
var g2 = g.mapVertices(
(vid,vd) => (false, if (vid == origin) 0 else Double.MaxValue,
List[VertexId]()))
for (i <- 1L to g.vertices.count-1) {
val currentVertexId =
g2.vertices.filter(!_._2._1)
.fold((0L,(false,Double.MaxValue,List[VertexId]())))((a,b) =>
if (a._2._2 < b._2._2) a else b)
._1
val newDistances = g2.aggregateMessages[(Double,List[VertexId])](
ctx => if (ctx.srcId == currentVertexId)
ctx.sendToDst((ctx.srcAttr._2 + ctx.attr,
ctx.srcAttr._3 :+ ctx.srcId)),
(a,b) => if (a._1 < b._1) a else b)
g2 = g2.outerJoinVertices(newDistances)((vid, vd, newSum) => {
val newSumVal =
newSum.getOrElse((Double.MaxValue,List[VertexId]()))
(vd._1 || vid == currentVertexId,
math.min(vd._2, newSumVal._1),
if (vd._2 < newSumVal._1) vd._3 else newSumVal._2)})
}
g.outerJoinVertices(g2.vertices)((vid, vd, dist) =>
(vd, dist.getOrElse((false,Double.MaxValue,List[VertexId]()))
.productIterator.toList.tail))
}
// Path Finding - random node from which to find all paths
val v1 = 4000000028222916L
I then call their function with my graph and a random vertex ID. Previously I had issues with `v1` not being recognised as `long` type and the `L` suffix solved this.
val results = dijkstra(my_graph, 1L).vertices.map(_._2).collect
println(results)
However, this returns the following:
Error: Exception in thread "main" java.lang.NoSuchMethodError: scala.runtime.ObjectRef.create(Ljava/lang/Object;)Lscala/runtime/ObjectRef;
at GraphX$.dijkstra$1(GraphX.scala:51)
at GraphX$.main(GraphX.scala:85)
at GraphX.main(GraphX.scala)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:498)
at org.apache.spark.deploy.SparkSubmit$.org$apache$spark$deploy$SparkSubmit$$runMain(SparkSubmit.scala:731)
at org.apache.spark.deploy.SparkSubmit$.doRunMain$1(SparkSubmit.scala:181)
at org.apache.spark.deploy.SparkSubmit$.submit(SparkSubmit.scala:206)
at org.apache.spark.deploy.SparkSubmit$.main(SparkSubmit.scala:121)
at org.apache.spark.deploy.SparkSubmit.main(SparkSubmit.scala)
Line 51 refers to the line `var g2 = g.mapVertices(`
Line 85 refers to the line `val results = dijkstra(my_graph, 1L).vertices.map(_._2).collect`
What method is this exception referring to? I am able to package with `sbt` without error and I canno see what method I am calling whcih does not exist.
Many thanks!
Brian
[1]: https://www.manning.com/books/spark-graphx-in-action#downloads <https://www.manning.com/books/spark-graphx-in-action#downloads>
> On 24 Oct 2016, at 16:54, Michael Malak <mi...@yahoo.com> wrote:
>
> Chapter 6 of my book implements Dijkstra's Algorithm. The source code is available to download for free. https://www.manning.com/books/spark-graphx-in-action <https://www.manning.com/books/spark-graphx-in-action>
>
>
>
>
> From: Brian Wilson <br...@gmail.com>
> To: user@spark.apache.org
> Sent: Monday, October 24, 2016 7:11 AM
> Subject: Shortest path with directed and weighted graphs
>
> I have been looking at the ShortestPaths function inbuilt with Spark here <https://github.com/apache/spark/blob/master/graphx/src/main/scala/org/apache/spark/graphx/lib/ShortestPaths.scala>.
>
> Am I correct in saying there is no support for weighted graphs with this function? By that I mean that it assumes all edges carry a weight = 1
>
> Many thanks
>
> Brian
>
>
Re: Shortest path with directed and weighted graphs
Posted by Michael Malak <mi...@yahoo.com.INVALID>.
Chapter 6 of my book implements Dijkstra's Algorithm. The source code is available to download for free. https://www.manning.com/books/spark-graphx-in-action
From: Brian Wilson <br...@gmail.com>
To: user@spark.apache.org
Sent: Monday, October 24, 2016 7:11 AM
Subject: Shortest path with directed and weighted graphs
I have been looking at the ShortestPaths function inbuilt with Spark here.
Am I correct in saying there is no support for weighted graphs with this function? By that I mean that it assumes all edges carry a weight = 1
Many thanks
Brian