Login | Register   
RSS Feed
Download our iPhone app
Browse DevX
Sign up for e-mail newsletters from DevX

By submitting your information, you agree that devx.com may send you DevX offers via email, phone and text message, as well as email offers about other products and services that DevX believes may be of interest to you. DevX will process your information in accordance with the Quinstreet Privacy Policy.


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

It has been proven that you can always color a map with four colors in such as way that no two adjacent regions have the same color. Unfortunately doing so can be both difficult and time consuming—but it's not too hard to color a map with five colors.




Application Security Testing: An Integral Part of DevOps

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!

Rod Stephens is a consultant and author who has written more than a dozen books and two hundred magazine articles, mostly about Visual Basic. During his career he has worked on an eclectic assortment of applications for repair dispatch, fuel tax tracking, professional football training, wastewater treatment, geographic mapping, and ticket sales. His VB Helper web site receives more than 7 million hits per month and provides three newsletters and thousands of tips, tricks, and examples for Visual Basic programmers.
Comment and Contribute






(Maximum characters: 1200). You have 1200 characters left.



We have made updates to our Privacy Policy to reflect the implementation of the General Data Protection Regulation.
Thanks for your registration, follow us on our social networks to keep up-to-date