# Graphx Graph Traversal with Pregel Explained

## Breadth First Graph Traversal with Graphx using Pregel

To demonstrate Graph Traversal using Pregel from Graphx, construct the graph first, called graph:

Create a new graph called markedGraph by transforming original graph:

#### Thought Process:

markedGraph is the same as original graph except vertex attributes other than the VertexId=1 is Infinity. Vertex attribute for VertexId=1 is 0.0.

We will visit all vertices as long as vertex attributes are Infinity. During visit, set the visited Vertex attribute to non Infinity.

We will not visit vertices where vertex attributes are not Infinity.

When each vertex attribute is no longer Infinity in the end, visit (traverse) ends, thus complete the graph traversal.

Then print all vertex id out after traversal ends where no more vertex attributes is Infinity.

#### Implementation of Pregel:

Calling < graph >.pregel will return a new graph. We will use Pregel to traverse markedGraph that has starting vertex (1, 0.0), rest of vertices are (VertexId, Double.Infinity).

Internally, pregel will run in loop, each step of the loop is called SuperStep. During each SuperStep, the vertex where its vertex attribute not Double.Infinity will send its vertex attribute to connected neighboring vertices whose vertex attribites are Double.Infinity. The receiving vertices whose vertex attributes will be set to the smallest value of messages (if it receives more than one messages from different connected beighboring sending vertices), overwriting its original vertex value of Double.Infinity.

Vertices whose vertex attributes are Double.Infinity do not send message, just stay put.

Also, vertices do not send messages to connected neighboring vertices whose vertex attributes are NOT Double.Infinity, also stay put.

Loop or iteration will end when all vertices whose vertex attributes are NOT Double.Infinity. Hence, traverse completes.

#### How Pregel works

Pregel method take 2 argument lists

pregel(< argument list 1 >)(< argument list 2 >)

argument list 1 is a list of value arguments, argument list 1 is to set initial value

argument list 2 is a list of functional arguments, which is an example of Scala higher order function, meaning each function argument is free to have its own execution algorithm, its own logic.

In this example

first argument list is

(Double.PositiveInfinity, 20)

It defines:

Initial message is Double.PositiveInfinity. The initial message is to start the computation. This message is passed to all the vertices in the vertexRDD to do the 1st iteration. Including the starting vertex whose vertex attribute is 0.0, but Double.PositiveInfinity is greater than 0.0, therefore, it will not replace vertex attribute that is not greater than the message which is Double.PositiveInfinity.

Maximum iteration 20, loop will end after 20 SuperSteps. In this example, 20 will be sufficient as a mechanism to break endless loop if it happens.

second argument list is

(vprog, sendMessage, mergeMessage)

that contains 3 function arguments:

*Important to note, during each SuperStep, each sending vertex sends the message to its directly connected vertex in parallel, you can imagine multiple instances of sendMessage, mergeMessage and vprog running in parallel across all worker nodes (computers) in the Spark network cluster, updating vertex attributes at the same time across many vertices. This is not done in serial. * vprog (stands for vertex program, it does the change to the vertex attribute if condition is met)

//vprog is Vertex Program, take action with message received, to set the Vertex attribute with smaller value message, if it was ∞, it will be replaced // by a value which is smaller than ∞

val vprog = { (id: VertexId, attr: Double, msg: Double) => math.min(attr,msg) }

sendMessage During each SuperStep in the loop once the computation starts, each triplet that has the connected neighboring vertices to examine whether sending message can proceed, *if and only if a vertex whose vertex attribute is NOT Double.PositiveInfinity can send message ONLY to directly connected vertex whose vertex attribute is Double.PositiveInfinity*

The message if send is in the form of sending vertex attribute plus 1.

Logic of this code is:

*Vertex will not send message if its vertex attribute is Double.PositiveInfinity or if vertex attribue of the connected neighboring vertex is NOT Double.PositiveInfinity.*

For each SuperStep, sendMessage returns an Iterator of VertexId and message received. (Again, message is in the form of sending vertex attribute plus 1)

mergeMessage

For reciving Vertex, if multiple messages are received, return the smallest message value.

Following is visualization of each SuperStep in the loop:

Super Step 1: root vertex (1,0.0) sends message which its vertex attribute 0.0+1=1.0 to its connected neighboring vertices (vertexId=2) and (vertexId=3) which had Double.PositiveInfinity prior, setting vertex (vertexId=2) to (2,1.0), (vertexId=3) to (3,2.0)

Super Step 2: In this step, vertices (vertexId=2) and (vertexId=3) sends message which its vertex attribute 1.0+1=2.0 to its connected neighboring vertices, sent the vertex attributes of these receiving vertices to 2.0

Super Step 3: No vertex attributes are Double.PositiveInfinity, loop ends. Here is the end state of the Graph that is returned by pregel call

#### Summary:

Before Super Loop starts

markedGraph.vertices.collect

res2: Array[(org.apache.spark.graphx.VertexId, Double)] = Array((4,Infinity), (1,0.0), (5,Infinity), (6,Infinity), (2,Infinity), (3,Infinity), (7,Infinity))

After Super Loop ends, all vertices with Infinity attributes have been changed to a non infinity value during visiting the vertex by message

graphTraverse.vertices.collect

res3: Array((4,2.0), (1,0.0), (5,2.0), (6,2.0), (2,1.0), (3,1.0), (7,2.0))

If you print out based on traverse, it should be starting from where the vertex attribute to be 0.0, then propagating to 1.0, then 2.0

Here is the entire Graph traverse code and the result of running it is the path of graph traversal

#### Summary

Clearly, as you can see, Graph traversal by sending message from the starting Vertex to its directly connected vertices then propagate to next layer of vertices is accomplished by breadth first traversal.

Last updated