Graph Vertex Coloring in Spark GraphX / GraphFrames

*******************************************
A simple naive algorithm for ColorReduction
*******************************************

function ColorReduction(G = (V, E), ∆)
n = |V |
for v = Range(n) do
color(v) = v
end for

for v = ∆ + 2, n do
color(v) = min({1, ..., ∆ + 1} \ {cu|(u, v) ∈ E})
end for

end function

*******************************************
The line
color(v) = min({1, ..., ∆+1 } \ {cu|(u, v) ∈ E})
indicates that a node should choose a min value from
(1,...,∆ + 1) which is not taken by its neighbors.

For example, if my neighbors are colored (1,2,4,5) ,
then the node will choose its color as 3.

More info @ https://en.wikipedia.org/wiki/Graph_coloring
*******************************************
/**
* This is highly fast compared to naive but works only on a connected
* graph. If the graph is disconnected , it should be made sure to
* initialize atleast one value in each connected component to be
* initialized with a value in range of (1, k+1)
*
* This works on the principle of the principle of breadth first expansion
*
********************************************
A Fast algorithm for ColorReduction
*******************************************

function ColorReductionFast(G = (V, E), ∆, maxIter)
n = |V |
for v = Range(n) do
color(v) = v
end for

COLORED = {node | color(node) <= ( ∆ +1 ) }
NOT_COLORED = {node | color(node) > ( ∆ +1 ) }


for e ∈ (u,v) | u ∈ COLORED && v ∈ NOT_COLORED {
c(v) = min({1, ..., ∆ + 1} \ {cu|(u, v) ∈ E})
}

(or )

for iter = 1 , maxIter do
// updates colors of the neighbors of nodes whose colors are are already labelled.
color(v) = min({1, ..., ∆ + 1} \ {cu|(u, v) ∈ E}) such that color(u) < ∆ +1 && color (v) > (∆ + 1)
end for


end function
If you like my work, buy me a coffee.

--

--

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store