Four color theorem Java implementation of U.S. map

Question

I am attempting to assign a color to each of the states so that no two adjacent states share the same color (http://en.wikipedia.org/wiki/Four_color_theorem). The program will output each state and its color.

I'm reading in a text file with the following format for 48 states (2 aren't connected):

al,fl,ms,tn,ga
ar,la,tx,ok,mo,tn,ms
az,ca,nv,ut,nm
ca,az,nv,or
co,wy,ut,nm,ok,ks,ne
...

Example:

Alabama touches Florida, Mississippi, Tennessee, and Georgia.

Arkansas touches Louisiana, Texas, etc.

This is my code so far:

MapColor.java    

import java.io.*;
import java.util.*;

public class MapColor {

    public static void main(String[] args) throws IOException {

        ArrayList <String> statestemp = new ArrayList <String> ();
        ArrayList <State> states = new ArrayList <State> ();

        // read in each line
        BufferedReader reader = new BufferedReader(new FileReader("usa.txt"));
        String line = null;
        while ((line = reader.readLine()) != null) {
            statestemp.add(line);
        }
        reader.close();

        // create all state objects and adjacencies
        for (int i = 0; i < statestemp.size(); i++) {
            State st = new State();
            String[] str = statestemp.get(i).split(",");
            st.setName(str[0]);
            for (int j = 1; j < str.length; j++) {
                st.addAdj(str[j]);
            }
            states.add(st);
        }

        // set colors


        // print out states and adjacencies
        for (State s : states) {
            System.out.println("Name: " + s.getName());
            System.out.println("Color: " + s.getColor());
            System.out.print("Adj: ");
            s.getAdj();
            System.out.println();
            System.out.println();
        }

    }
}

and

State.java

import java.util.ArrayList;

public class State {

    public String n = null;
    public int c = 0;
    public ArrayList <String> adj = new ArrayList <String> ();

    public String getName() {
        return n;
    }
    public void setName(String name) {
        this.n = name;
    }
    public int getColor() {
        return c;
    }
    public void setColor(int color) {
        this.c = color;
    }
    public void addAdj(String s) {
        this.adj.add(s);
    }
    public ArrayList <String> getAdj() {
        return this.adj;
    }
}

I am at the point where I would like to begin assigning colors, but I am unsure how to go about making comparisons.

Any suggestions would be appreciated!

Answer 1

The four-color mapping algorithm is very complex, with 1476 special cases that you have to handle in your code. If you can spare one more color, the five color mapping algorithm will meet your requirements, is much simpler, and there is a nice writeup on it at devx.com

For the special case of a United States map, there are many states with less than five neighbors (e.g, Florida), so you only have to address the first case of the algorithm, which is this:

1. Convert the map to a graph (looks like you've done this or are close with your adjacency list)
2. Choose one node (state) on the graph with less than five neighbors and remove it from the graph. This will reduce the complexity of your graph and may cause some nodes that previously had five or more neighbors to now have less than five.
3. Choose another node from the updated graph with less than five neighbors and remove it.
4. Continue until you've removed all the nodes from the graph.
5. Add the nodes back the graph in reverse order from which you removed them (think stack here).
6. Color the added node with a color that is not used by any of its current neighbors.
7. Continue until you've colored in the entire graph.