Parallel graph coloring algorithms are based on the observation that if we split the graph into multiple independent sets of vertices, we can color those in parallel without introducing any conflict.
To develop a parallelized version of the sequential greedy graph coloring algorithm from the previous section, we will be relying on a simple, yet effective algorithm proposed by Jones and Plassmann [6]. Before diving into the implementation details, let's take a few minutes to explain how the algorithm generates independent sets and how can we guarantee that our compute function will avoid data races while accessing the graph.
At initialization time, each vertex is assigned a random token. During each super-step, every vertex that hasn't been colored yet compares its own token value to the value of every uncolored neighbor. In the highly unlikely case that two neighboring vertices have been assigned the same random token, we can use the vertex ID as an extra comparison predicate to break the tie. The vertex with the highest token value gets to choose the next color using the same steps as the sequential algorithm while the neighboring vertices remain idle, waiting for their turn.
The concept of using tokens to enforce a coloring order guarantees that, at every super-step, we only color exactly one vertex from each independent set. At the same time, since connected vertices wait for their turn before they can pick a color, no data races can occur.
Just like we did with the shortest path implementation, we will begin by defining a type for holding the state of each vertex and a type that describes the messages that are exchanged between neighboring vertices:
type vertexState struct { token int color int usedColors map[int]bool } type VertexStateMessage struct { ID string Token int Color int } func (m *VertexStateMessage) Type() string { return "vertexStateMessage" }
The vertexState struct keeps track of the token and colors that are assigned to the vertex. Furthermore, the usedColors map tracks colors that have already been assigned to the vertex neighbors. Vertices broadcast their state to each of their neighbors by exchanging VertexStateMessage instances. In addition to the token and color value, these messages also include a vertex ID. As we mentioned previously, the vertex ID is required for breaking ties while comparing token values.
Now, let's break down the compute function for this algorithm into small chunks and examine each chunk in more detail:
v.Freeze() state := v.Value().(*vertexState) if g.Superstep() == 0 { if state.color == 0 && len(v.Edges()) == 0 { state.color = 1 return nil } state.token = random.Int() state.usedColors = make(map[int]bool) return g.BroadcastToNeighbors(v, state.asMessage(v.ID())) }
First things first, each super-step iteration begins by marking all the vertices as inactive. This way, vertices will only be reactivated in subsequent super-steps when a neighbor gets to pick a color and broadcast its selection. Consequently, once the last remaining vertex has been colored, no further messages will be exchanged and all the vertices will be marked as inactive. This observation will serve as the termination condition for the algorithm.
Super-step 0 serves as an initialization step. During this step, we assign random tokens to all the vertices and have them all announce their initial state to their neighbors. If any of the vertices are pre-colored, their assigned colors will also be included in the broadcasted state update message. The vertexState type defines a handy helper method called asMessage which generates a VertexStateMessage, that can be sent to neighbors via the graph's BroadcastToNeighbors method:
func (s *vertexState) asMessage(id string) *VertexStateMessage { return &VertexStateMessage{ ID: id, Token: s.token, Color: s.color, } }
Of course, the input graph may potentially include vertices with no neighbors. If these vertices have not been already pre-colored, we simply assign them the first available color, which in our particular implementation is color 1.
The next block of code processes state announcements from the vertex neighbors. Before iterating each state message, each vertex sets its local pickNextColor variable to true. Then, the message list is iterated and the following occurs:
- If a neighbor has been assigned a color, we insert it into the usedColors map for the local vertex.
- If any of the neighbors has a higher token value or has the same token value but their ID string value is greater than the local vertex one, they have a higher priority for picking the next color. Therefore, the pickNextColor variable will be set to false for the local vertex.
Once all state announcements have been processed, we check the value of the pickNextColor variable. If the vertex is not allowed to pick the next color, it simply broadcasts its current state and waits for the next super-step, as follows:
pickNextColor := true myID := v.ID() for msgIt.Next() { m := msgIt.Message().(*vertexStateMessage) if m.Color != 0 { state.usedColors[m.Color] = true } else if state.token < m.Token || (state.token == m.Token && myID < m.ID) { pickNextColor = false } } if !pickNextColor { return g.BroadcastToNeighbors(v, state.asMessage(v.ID())) }
Otherwise, the vertex gets to select the next color to be assigned to it:
for nextColor := 1; ; nextColor++ { if state.usedColors[nextColor] { continue } state.color = nextColor return g.BroadcastToNeighbors(v, state.asMessage(myID)) }
Since some of the vertices in the graph might be pre-colored, our goal is to pick the smallest not used color for this vertex. To do this, we initialize a counter with the smallest allowed value and enter a loop: at each step, we check whether usedColors contains an entry for the nextColor value. If so, we increment the counter and try again. Otherwise, we assign nextColor to the vertex and broadcast our updated state to the neighbors.
In case you are having concerns about the space requirements for keeping track of the used colors on a per-vertex basis, we can actually do much better if we don't need to support potentially pre-colored graphs. If that happens to be the case, each vertex only needs to keep track of the maximum color value that's assigned to its neighbors. At color selection time, the vertex picks maxColor + 1 as its own color.
The full source code and tests for the graph coloring implementation from this section can be found in this book's GitHub repository in the Chapter08/color folder.