Graphs are inherently recursive data structures as properties of vertices depend on properties of their neighbors, which in turn depend on properties of their own neighbors. As a consequence, many important graph algorithms iteratively recompute the properties of each vertex until a fixed-point condition is reached. A range of graph-parallel abstractions have been proposed to express these iterative algorithms. GraphX exposes a variant of the Pregel API.

At a high level, the Pregel operator in GraphX is a bulk-synchronous parallel messaging abstraction constrained to the topology of the graph. The Pregel operator executes in a series of steps in which vertices receive the sum of their inbound messages from the previous super step, compute a new value for the vertex property, and then send messages to neighboring vertices in the next super step. Using Pregel, messages are computed in parallel as a function of the edge triplet and the message computation has access to both the source and destination vertex attributes. Vertices that do not receive a message are skipped within a super step. The Pregel operators terminate iteration and return the final graph when there are no messages remaining.

Some algorithms which come built-in using Pregel API are as follows:

• ConnectedComponents
• ShortestPaths
• Traveling salesman
• PageRank (covered in the next section)

The Pregel API signature is shown in the following code, which shows the various arguments needed. The exact usage will be shown in the subsequent sections, so you can refer to this signature for clarification:

def pregel[A]
 (initialMsg: A,   // the initial message to all vertices
 maxIter: Int = Int.MaxValue,  // number of iterations
 activeDir: EdgeDirection = EdgeDirection.Out) 
 // incoming or outgoing edges
 (vprog: (VertexId, VD, A) => VD,
 sendMsg: EdgeTriplet[VD, ED] => Iterator[(VertexId, A)], 
 //send message function
 mergeMsg: (A, A) => A) //merge strategy
 : Graph[VD, ED]