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

Question

When I was trying to implement an algorithm in Graphx with Scala, I didn't find it possible to activate all the vertices in the next ietration.. How can I send a message to all my graph vertices? In my algorithm, there is some super-steps that should be executed by all the vertices (whether they receive a message or not because even not receiving a message is an event that should be handled in next iteration).

I give here the official code of SSSP algorithm implemeted in pregel's logic, you can see that only vertices that received a message will execute their program in the next iteration but for my case, I want pregel function to run iteratively i.e., each super-step the vertices execute their programs and they can vote to halt if needed !! The reasoning in this example doesn't look like Pregel's paper logic. Please any ideas on how to implement Pregel's real logic?

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"))

}

Joaquinajoash

if you want all nodes to keep sending and receiving messages, so you should always send a message. in the code you added it didn't send a message in some cases and send Iterator.empty you shouldn't do so! – Anear

The nodes will execute their program on all incoming messages to compute a new vertex value. Without an incoming message there will be no computation. As the other comment said, if all nodes continue sending messages then the vertex programs will continue to be executed (if they have an incoming edge and there no guarantee it will be at every iteration though when the graph is directed). For this to work you need to specify the maxIterations parameter - I don't think there is any way to vote to stop. – Softshoe

The alternative would be to implement the logic yourself. Or you could execute pregel multiple times with maxIterations=1 but that does not sound very efficient. – Softshoe

@Softshoe I agree with what you said, now I'm trying to implement the logic myself since you confirmed there is no way to vote to stop the algorithm. – Joaquinajoash

Answer 1

After reading the two replies from @Mahmoud Hanafy and @Shaido confirming that there is no way to activate the vertices or vote to halt in GraphX, I tried to implement this logic within the algorithm itself. So, here is what I did:

• Pregel's API sends an init message to all the graph vertices in the first super-step where they can execute their routines at least one time before they become inactive.
• At the end of this super-step, each vertex v may send messages to its neighbors and wait to receive messages from others.
• In the second super-step, not all vertices will receive information from their neighbors, that means not all vertices will be activated in the second super-step ! So, to solve this we need to get back to super-step one and ensure that each vertex will receive a message ! How? by sending a message to itself ! (This is the only way I can guarantee the activation of my vertex in the next super-step but I believe it's not the best one to do it because this will increase the number of messages sent and received).
• In the second super-step, every vertex will receive at least one message and hence will be active so it can execute its program.
• To ensure that a vertex will be activated in the next super-steps, we can do the same.

I repeat, this is the only way I come up with to solve my problem but I don't encourage you to use it.

Joaquinajoash