Graphx：是否可以在不接收消息的情况下在每个顶点上执行程序？

Question

当我尝试使用 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"))

}

Answer 1

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

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

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

Graphx：是否可以在不接收消息的情况下在每个顶点上执行程序？

Graphx : Is it possible to execute a program on each vertex without receiving a message?

scala

apache-spark

graph-theory

spark-graphx

spark-shell