|
|
by Marko Riedel
We will consider the problem of finding Hamiltonian cycles in undirected graphs. A Hamiltonian cycle of a graph (V,E), where V are the vertices and E the edges, is a cycle that visits every node exactly one. It visits every node of the graph in turn, starting at some vertex and returning to the start vertex at the end. A Hamiltonian cycle in a four-by-four grid graph is shown in Figure 5.
We will use backtracking to find Hamiltonian cycles, as indicated in the title of this section. The structure of the algorithm is very much like the structure of the algorithm for the queens problem, which is no accident, of course. Our algorithm iterates over the vertices, constructing the set of Hamiltonian cycles for each choice of start vertex. (This set is independent of the start vertex.) We build the cycle as we go. We look at the neighbors of the current last node of the cycle and add them to the cycle, checking one after another, if they have not been visited. If the cycle contains all vertices of the graph, then we check whether there is an edge from the last node to the first, and we have found a Hamiltonian cycle if this is the case. Otherwise we backtrack, successively removing nodes from the cycle that have had all their neighbors checked. The algorithm starts over when all vertices have been used as start vertices.
This algorithm is very much like the algorithm for the queens problem and hence it lends itself to a recursive implementation, where each recursive call roughly corresponds to a neighboring node being appended to the cycle and the base case occurs when the cycle contains all vertices and we check whether the last vertex is adjacent to the first. Recursion occurs only if the current last vertex has a neighbor that has not been visited. This is a straightforward design, but it has the drawback that it does not lend itself to single-step mode, where the user may observe individual nodes being checked and added to the cycle. This is the same situation as with the queens problem. It could be fixed by integrating an event loop into the recursion, but we will simply unroll the recursion and record the state of the search at any given time. We record the vertices of the cycle and the current last vertex (the latter is for convenience). We also maintain an array of bits that tells us which vertices have been visited (this is for lookup in constant time). There is an additional array that records which neighbor should be processed next as we iterate over the neighbors of a given vertex. This last array is equivalent to the stack in a recursive implementation and its first entry is a vertex (the start vertex). The remaining entries are indices into the array of neighbors of the current vertex.
The GUI is straightforward. There is one window, which contains an image of the graph and the cycle that has so far been computed. Ordinary edges and vertices are drawn in black. The cycle is drawn in magenta and the candidate vertex that is currently being examined is drawn in red, as is the edge that connects it to the cycle. The background color changes from white to green when a solution has been found. The items on the main menu let the user single-step through the search or run it automatically. There is an item that advances the search to the next solution. The algorithm starts over when all vertices have been processed. The application can be a bit slow to respond to the menu item “halt” when it is doing an automatic search of a large graph, where state transition time intervals are shorter.
This recipe provides an opportunity to use object-oriented programming. There are three types of classes: first, a generic graph view class (a subclass of NSView) that draws the graph and implements the search, second, subclasses of this class that implement particular types of graphs and third, a controller, which is the delegate of the application object, parses command line arguments, provides the main menu, responds when the user clicks on an item and controls the timer that moves from one state to the next during automated searches.
The program knows four types of graphs:
It may be an interesting excercise to add other kinds of graphs to this program.
We start by including everything so we don’t have to list individual classes. We need the math header for the square root function, the sine and cosine functions and the value of π. The class GView:NSView represents graphs and controls the search for Hamiltonian cycles. The qualifiers on its instance variables also illustrate the object-oriented structure of the application. The actual graph is stored in an adjacency list adj that contains the neighbors of each vertex. The physical layout of the graph is stored in the array loc, which holds the plane coordiantes of each vertex. These variables are protected, rather than private, because subclasses of GView need to access them when they create the adjacency list and assign locations in the initializer. The remaining instance variables are private and only GView can access them. The array cycle stores the current cycle1, adjPos[k] stores the next neighbor to examine when selecting vertex number k. The array visited is an array of bits and it stores flags that indicate whether a given vertex has been visited. This is so we don’t need to search the cycle to determine whether a given neighbor has been visited and hence should not be added to the cycle. The variable candidate holds the vertex currently under consideration for addition to the cycle. It is a vertex number when the cycle is empty and an index into the corresponding array from the adjacency list when there is at least one vertex on the cycle. The variable lastVertex holds the last vertex on the cycle, so that we can access this value without retrieving it from the cycle array first. This variable is set to -1 when the cycle is empty. There is a variable that counts the number of solutions computed so far, and a boolean flag that switches on when the search moves from one start vertex to the next.
The method initWithFrame:vertices: is the initializer of the GView class. It should be called from its subclasses with the correct number of vertices and the frame rectangle. It initializes everything that is common to all types of graphs. The method initWithDimension: is the responsiblity of subclasses of GView. It should initialize the adjacency list and compute vertex locations. A GView knows how to draw itself and the current cycle, and this is the purpose of drawRect:. It is shared among the subclasses of GView, which also implements the most important method of the entire recipe, namely next, which advances from one state of the search to the next.
The remaining four methods are very simple. The method isSolution returns a boolean that indicates whether the current state of the search corresponds to a solution. The method vertexCount returns the number of vertices and the method solCount, the number of solutions found since the program was last in its initial state. The flag returned by newRun is true when we move from one start vertex of the cycle to the next.
The common initializer initWithFrame:vertices: starts by invoking the initializer of NSView with the frame rectangle computed by the subclass. It records the vertex count and initializes the adjacency list and its entries, which will later hold the nieghbors of all vertices; adj[k] is an array that holds the neighbors of vertex k. It also initializes the array of vertex locations, which are also computed by the subclass.
The second half of the initializer deals with the variables that store the state of the search. The cycle is initially empty. The array of flags visited consists entirely of zeros, i.e. no vertex has been visited. The array of indices into arrays of neighbors adj is empty also. The vertex number zero is the first candidate. The last Vertex is set to -1, a value that indicates that the value of candidate is a vertex and not an index into an array of neighbors. The solution counter is set to zero and the new-run flag to false (it will be true for the first time when all cycles that start at vertex zero have been processed and the search moves on to vertex one.)
The method initWithDimension: is the subclasses’ responsiblity. They will be able to turn the abstract superclass GView into concrete graphs by implementing just this one method.
The method drawRect: is fairly important to the recipe. It lets the user get a quick grasp on the algorithm by viewing the graph and the current cycle. The constant RADIUS defines the radius of the black filled circles that represent vertices. The first step is to draw the background – green if we have a solution and white otherwise.
The next step is to draw the edges. Edges are four pixels wide and drawn in black. We iterate over the entries of the adjacency list, one for each vertex. The value of each entry is an array of neighbors. We retrieve the start point vp and the end point wp of each edge and connect them with a line. We draw the path with PSstroke() once all edges have been processed. Recall that the array loc tells us where each end point, i.e. vertex, has to go. The macro LOC saves some typing when we retrieve locations.
We now draw the edges of the cycle (but not its vertices – all vertices are drawn after the edges so that they cover the parts of the edge lines that lie inside the vertex circles). Edges are drawn in magenta, ten pixels wide. We move to the location of the first vertex and connect additional vertices with lines. The call to PSstroke() actually draws the path.
The last edge that we draw goes from the last vertex of the cycle to the candidate vertex, if any. We use this opportunity to compute the candidate vertex, which we will need to color red later. The value of candidate can be used directly when the cycle is empty. Otherwise it is an index into the array of neighbors of the last vertex (the array of neighbors is retrieved from the adjacency list). We do not set the candidate vertex when its value indicates that all neighbors of the last vertex have been processed.
We may now draw an edge from the last vertex to the candidate vertex, if appropriate. The edge is drawn in red and at the same width as the other edges of the cycle, i.e. ten pixels. We are done drawing edges.
The last step is to draw the vertices. The index variable v iterates over all vertices. It selects the right color, sets the color and draws the filled circle that represents the vertex. Vertices that have been visited are drawn in magenta, the candidate vertex is drawn in red and the remaining vertices are drawn in black. This concludes the implementation of drawRect:. The entire graph and the cycle have been drawn.
We now move on to the most important method of this recipe: next, the method that moves from one state of the search to the next. There are three types of states: first, a cycle that has not visited all vertices, second, a cycle that has visited all vertices but could not be closed, amd third, a cycle that could be closed and returns to the start vertex through its last entry. For a graph with n vertices and m vertices on the cycle, these three cases become, respectively, m < n, m = n andm = n + 1.
We first treat the transition from the state m = n to m = n + 1. We must check whether we can connect the last vertex to the first. We retrieve the NSNumber objects that hold the first and the last vertex and query them for the actual integer values, storing the result in firstVal and lastVal. Next we extract the array of neighbors of the last vertex and store it in lastAdj. We also extract the number of neighbors. The next step is to iterate over all neighbors and check whether the first vertex of the cycle is among them. We end the loop if this is the case, and add the vertex to the cycle, thereby moving to the state m = n + 1. It is left as an exercise to the reader to modify this recipe so that graphs are represented not only by adjacency lists but also by incidence matrices. The check whether the cycle can be closed then becomes a one-liner, albeit at the cost of additional storage space.
The next step implements the transition from the m = n + 1 state back to the m = n state. This is done by removing the last vertex from the cycle, incrementing the solution counter and assigning a value to the candidate that indicates that all neighbors of the last vertex have been processed. This is necessary so that we can successfully fall through to the backtracking code.
The backtracking code is implemented with a loop. It starts at the end of the cycle and removes vertices that have had all their neighbors processed. The test
candidate==[[adj objectAtIndex:lastVertex] count]
indicates whether the current last vertex has had all its neighbors processed. If this is the case, then it triggers the following sequence of steps:
The loop repeats until a vertex has been found that has not had all its neighbors processed, or until the cycle is empty.
There is a bit of an interlude as we check whether the algorithm has returned to the start point and output a status message on STDERR. Each cycle will have been counted once for each of its vertices, and once for each of two directions in which it may be traversed, which accounts for the division by two times the vertex count in the log statement.
We are now done with the backtracking code and can move on to where we actually add a vertex to the cycle. This would be the recursive call in a recursive implementation. We also determine whether we have a new run, i.e. a new start vertex, which occurs when the current cycle is the reduction of a cycle that was not empty. Our first step in the addition of a vertex is to determine which neighbor of the last vertex should be tested. There are two cases: first, when the cycle is empty: the candidate value directly determines the vertex, second, when the cycle is not empty: the candidate value is an index into the array of neighbors of the last vertex. We set neighbor to be an NSNumber object that holds the neighbor vertex value and nval to be the vertex itself.
