Assignment 3: Color searching

Due Friday, April 10, at 4pm. Worth 30 points. Submit by uploading Searcher.java and your paper to Sauron [Instructions]. You may choose to work with a classmate on this assignment; if you do so, you should submit a single solution together.

Graph coloring is a heavily studied problem. In it, we're given a graph and some number k of colors, and our goal is to assign a color to as many vertices as possible so that no two adjacent vertices have the same color. In the below example using k as three, it's actually possible to color all vertices, as shown. Note that the lower right vertex was forced red because its neighbors were already colored green and blue. However, the top right vertex could safely be recolored red.

Before coloring	After coloring (`k` = 3)

Like most good problems, graph coloring is NP-hard. It's even NP-hard when we're working with just three colors. However, there's a greedy algorithm that frequently works relatively well: We begin by choosing a random vertex and choosing a random color for it. Then we select one of the vertices with the fewest viable colors and color it with one of those. Then again select the vertex with the fewest possibilities and color it with one of those. Continue until no more vertices are left to choose.

The distributed code implements this algorithm. It consists of seven classes. (You can download all seven in this ZIP file.)

UndirectedGraph Represents an undirected graph. This is basically unmodified since Assignment 2.

Vertex Represents a single vertex in a graph, including its color selection and a list of possible colors.

GraphCanvas A Swing component for displaying a graph within a window.

GreedyColoring Implements the greedy coloring algorithm and provides methods for assigning and unassigning colors to vertices (which incorporates updates to the possible colors for neighboring vertices).

Searcher Implements local search. This is the class that you should be modifying as part of this assignment.

Main Provides a main method which determines the number of vertices and the edge probability (I recommend 0.75). From this, it creates a random grid of vertices, executes the greedy algorithm, displays the colored graph, and then executes one step of your Searcher class with each mouse click.

Batch Provides another main method using no graphical interface. It takes 100 random graphs, does the greedy algorithm on each, then does 40 steps of your Searcher algorithm. It displays the average number of uncolored vertices and the average time taken across the 100 trials.

Your assignment is first to read §9.3.1 and §9.3.2 from the textbook about local search heuristics for improving solutions to optimization problems. Then you should develop a good local search heuristic for 3-coloring, implement this in Searcher, and write a brief paper of 1 to 2 single-spaced pages describing your algorithm and its performance. You should submit your Searcher solution and your paper (in OpenOffice.org or Microsoft Word format) to Sauron.

Your solution's quality will be evaluated based on its efficiency and its effectiveness. The paper will be evaluated on its writing quality, on how well it presents your heuristic, and on the quality of analysis.

`UndirectedGraph`	Represents an undirected graph. This is basically unmodified since Assignment 2.
`Vertex`	Represents a single vertex in a graph, including its color selection and a list of possible colors.
`GraphCanvas`	A Swing component for displaying a graph within a window.
`GreedyColoring`	Implements the greedy coloring algorithm and provides methods for assigning and unassigning colors to vertices (which incorporates updates to the possible colors for neighboring vertices).
`Searcher`	Implements local search. This is the class that you should be modifying as part of this assignment.
`Main`	Provides a `main` method which determines the number of vertices and the edge probability (I recommend 0.75). From this, it creates a random grid of vertices, executes the greedy algorithm, displays the colored graph, and then executes one step of your `Searcher` class with each mouse click.
`Batch`	Provides another `main` method using no graphical interface. It takes 100 random graphs, does the greedy algorithm on each, then does 40 steps of your `Searcher` algorithm. It displays the average number of uncolored vertices and the average time taken across the 100 trials.