6

当我尝试使用 Scala 在 Graphx 中实现算法时，我发现无法在下一次迭代中激活所有顶点。如何向我的所有图形顶点发送消息？在我的算法中，所有顶点都应该执行一些超级步骤（无论它们是否收到消息，因为即使没有收到消息也是应该在下一次迭代中处理的事件）。

我在这里给出了在 pregel 的逻辑中实现的 SSSP 算法的官方代码，你可以看到只有收到消息的顶点才会在下一次迭代中执行它们的程序，但是对于我的情况，我希望 pregel 函数迭代运行，即每个超级步骤顶点执行他们的程序，如果需要他们可以投票停止！这个例子中的推理看起来不像 Pregel 的论文逻辑。请对如何实现 Pregel 的真实逻辑有任何想法？

val graph: Graph[Long, Double] =
  GraphGenerators.logNormalGraph(sc, numVertices = 100).mapEdges(e => e.attr.toDouble)
val sourceId: VertexId = 42 // The ultimate source
// Initialize the graph such that all vertices except the root have distance infinity.
val initialGraph = graph.mapVertices((id, _) =>
    if (id == sourceId) 0.0 else Double.PositiveInfinity)
val sssp = initialGraph.pregel(Double.PositiveInfinity)(
  (id, dist, newDist) => math.min(dist, newDist), // Vertex Program
  triplet => {  // Send Message
    if (triplet.srcAttr + triplet.attr < triplet.dstAttr) {
      Iterator((triplet.dstId, triplet.srcAttr + triplet.attr))
    } else {
      Iterator.empty
    }
  },
  (a, b) => math.min(a, b) // Merge Message
)
println(sssp.vertices.collect.mkString("\n"))

}

4

1 回答 1

4

在阅读了来自@Mahmoud Hanafy 和@Shaido 的两个回复，确认无法在 GraphX 中激活顶点或投票停止后，我尝试在算法本身中实现这个逻辑。所以，这就是我所做的：

  • Pregel 的 APIinit message在第一个超级步骤中向所有图顶点发送一个，它们可以在它们变为非活动状态之前至少执行一次例程。
  • 在这个超级步骤结束时，每个顶点v可以向它的邻居发送消息并等待接收来自其他顶点的消息。
  • 在第二个超级步骤中，并不是所有的顶点都会从他们的邻居那里收到信息，这意味着在第二个超级步骤中并不是所有的顶点都会被激活！所以，为了解决这个问题，我们需要回到超级第一步，并确保每个顶点都会收到一条消息！如何？通过向自己发送消息！（这是我可以保证在下一个超级步骤中激活我的顶点的唯一方法，但我相信这不是最好的方法，因为这会增加发送和接收的消息数量）。
  • 在第二个超级步骤中，每个顶点将至少收到一条消息，因此将处于活动状态，以便执行其程序。
  • 为了确保在接下来的超级步骤中激活顶点，我们可以这样做。

我再说一遍，这是我想出的解决问题的唯一方法，但我不鼓励你使用它。

于 2018-12-04T18:45:28.660 回答