scala - 图 : Is it possible to execute a program on each vertex without receiving a message?

Question

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

我在这里给出了在 pregel 的逻辑中实现的 SSSP 算法的官方代码，您可以看到只有收到消息的顶点才会在下一次迭代中执行他们的程序，但就我而言，我希望 pregel 函数迭代运行，即每个 super 步骤顶点执行他们的程序，如果需要，他们可以投票停止!!这个例子中的推理看起来不像 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"))

}

Answer 1

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

Pregel 的 API 发送一个 init message到第一个 super 步骤中的所有图顶点，在那里它们可以在它们变为非事件状态之前至少执行一次它们的例程。

在这个 super 步骤结束时，每个顶点v可能会向其邻居发送消息并等待接收其他人的消息。

在第二个 super 步骤中，并非所有顶点都会收到来自其邻居的信息，这意味着并非所有顶点都会在第二个 super 步骤中被激活!所以，为了解决这个问题，我们需要回到 super 第一步并确保每个顶点都会收到一条消息!如何？通过向自己发送消息! (这是我可以保证在下一个 super 步骤中激活我的顶点的唯一方法，但我相信这不是最好的方法，因为这会增加发送和接收的消息数量)。

在第二个 super 步骤中，每个顶点将至少收到一条消息，因此将处于事件状态，以便它可以执行其程序。

为了确保在接下来的 super 步骤中激活顶点，我们可以这样做。

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