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 <brian.wilson....@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 <michaelma...@yahoo.com
>> <mailto:michaelma...@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....@gmail.com
>> <mailto:brian.wilson....@gmail.com>>
>> To: user@spark.apache.org <mailto: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
>>
>>
>
