Colorful Algorithms: Solving Map-coloring and Related Problems : Page 3

Writing Colorful Code
The downloadable example program for this article is rather involved and contains a lot of code that isn't related to map coloring so I haven't shown it all here. For example, it includes a simple map editor (not discussed) that lets you draw regions to color.

The program represents regions on the map with the MapRegion class. This class provides basic support for adding and removing a region from a list of MapRegion objects.

The code in Listing 1 shows the most important parts of the main program's map-coloring code. I've used VB.NET for the code in this article, but the download includes a C# version.

The code begins by declaring a list called m_Regions that holds the MapRegions that comprise the map: Private

   m_Regions As New List(Of MapRegion)

It then declares a RuleTypes enumeration that defines values representing the two rules for simplifying the map.

   ' The two rules for simplifying the map.
   Private Enum RuleTypes
       DegreeUnderFive
       NonAdjacentNeighbors
   End Enum

The AssignColors method controls the map coloring process. It creates a stack named action_stack to keep track of the rules the program follows and the objects that are involved when the map is manipulated.

   Private Sub AssignColors()
       ' The removed regions.
       Dim action_stack As New Stack()
   
       ' Simplify the map.
       Do While m_Regions.Count > 0
           SimplifyMap(m_Regions, action_stack)
       Loop
   
       ' Rebuild the map.
       Do While action_stack.Count > 0
           RestoreRegion(m_Regions, action_stack)
       Loop
   End Sub

While the m_Regions collection holds any MapRegion objects, AssignColors calls the SimplifyMap method (see Listing 1) which appliesthe two rules. It continues calling SimplifyMap until m_Regions is empty.

Next the subroutine calls RestoreRegion to undo one of the rules stored in action_stack. It continues calling RestoreRegion until the stack is empty and all of the MapRegion objects have been restored to the map and colored properly.

Subroutine SimplifyMap first attempts to apply Rule 1, searching the regions list for a region with a degree less than five. If it finds such a region, it removes it from the regions list and adds it to the stack. It also adds the RuleTypes value DegreeUnderFive to the stack to remember that it used Rule 1 on this node.

If SimplifyMap cannot apply Rule 1, it applies Rule 2, searching for a region with a degree of exactly five that has neighbors N1 and N2 that are not neighbors of each other. The MapRegion class's FindNonAdjacents function returns True when a region satisfies these conditions.

After finding the necessary node and its neighbors, the subroutine removes the node. It makes a new node to represent the neighbors, makes the new node adopt the neighbors' lists of neighbors, and adds the new node to the regions list. It then removes the original neighbors from the list and pushes all the relevant objects onto the stack. It finishes by adding the RuleTypes value NonAdjacentNeighborsto the stack to record the fact that it used Rule 2 on these objects.

Subroutine RestoreRegion reverses the most recent simplification. It pops the most recent RuleTypes value off the stack to determine which rule was used at this point in the simplification process.

If the most recent simplification was made with Rule 1, the subroutine pops the node that was removed under Rule 1 off the stack. It puts the node back in the map and calls its AssignColor method to give it a color. The MapRegion class's AssignColor method picks a color for the node that isn't used by its neighbors. Because the region has degree less than five, there is at least one unused color available.

   ' Assign a color to this region.
   Public Sub AssignColor()
      Me.ColorIndex = 0
   
      ' Try each color (skipping the "unassigned" color).
      For test_color As Integer = 1 To BackColor.Length - 1
         ' See if neighbor is using this color.
         Dim is_used As Boolean = False
         For Each nbr As MapRegion In Neighbors
            If nbr.ColorIndex = test_color Then
               is_used = True
               Exit For
            End If
         Next nbr
   
         ' See if the color is available.
         If Not is_used Then
            Me.ColorIndex = test_color
            Exit For
         End If
      Next test_color
   
      ' Make sure we found a color.
      Debug.Assert(Me.ColorIndex > 0, _
         "Error assigning a color to the region")
   End Sub

If instead the most recent simplification was made with Rule 2, the subroutine pops all the relevant objects off the stack. It restores the neighbors to the map and sets their colors to the color previously assigned to the combined region. It then removes the combined region, restores the original node X that had degree exactly five, and calls its AssignColor method.

As you can see, coloring a map with five colors isn't too hard. In fact, because the MapRegion class's AssignColor method considers the five available colors in the same order every time, it picks the fifth color only when it must—so it often finds four-colorings "accidentally." However, if you really need to produce four-color maps reliably every time, you can always check the 1,476 special cases used in Appel and Haken's proof!

Previous Page