Let’s hear it for Logo! (2)

Continuing my re-discovery of Logo, I thought I’d try to implement a backtracking solution to finding a Hamiltonian cycle in a graph. Backtracking is easily implemented by treating the routine as a boolean function, which simply returns the truth value of the existence of a Hamiltonian cycle. The basic schema works like this, given a graph G and a path P:

isHamilton(P,G):

  • If P contains all vertices of G without repeats, and the end of P is the same as the start, then return TRUE.
  • For all vertices v adjacent to the end of P and which are not contained in P output the result of isHamilton(P+v, G).
  • return FALSE

For a nice introduction to backtracking, see https://www.cis.upenn.edu/~matuszek/cit594-2012/Pages/backtracking.html.

We will enter our graphs as adjacency lists: this is a list of lists, where each member list consists of a vertex followed by all its adjacent vertices. For example, the adjacency list of the wheel graph W_6 on 6 vertices, with 1 as the central vertex and vertices 2 – 6 in clockwork order:

Rendered by QuickLaTeX.com

would look like this:

[[1 2 3 4 5 6] [2 1 3 6] [3 1 2 4] [4 1 3 5] [5 1 4 6] [6 1 2 5]]

We start with two helper programs, one which tests the adjacency of two vertices, and one which tests whether a vertex can be added to an existing path:

to adjacentp :vert1 :vert2 :graph
output memberp :vert1 bf item :vert2 :graph
end

to allowable :vert :path :graph
  make "bool1 memberp :vert :path
  make "bool2 adjacentp :vert (last :path) :graph
  output (and (not :bool1) :bool2)
end

The Hamiltonian code now simply copies the above algorithm description:

to hamilton :path :graph
print :path
make "count :count + 1
if equalp (count :path) (count :graph) ~
   [ifelse adjacentp (first :path) (last :path) :graph [output "TRUE] [output "FALSE]]

foreach firsts :graph ~
        [if allowable # :path :graph ~
           [if hamilton lput # :path :graph [output "TRUE]]]
output "FALSE
end

The print :path statement does exactly that; the idea is that when the program finishes its run with a positive result, the last path printed before output TRUE will be the cycle we want. Here’s an example:

? make "wheel6 [[1 2 3 4 5 6] [2 1 3 6] [3 1 2 4] [4 1 3 5] [5 1 4 6] [6 1 2 5]]
? show hamilton [1] :wheel6
1
1 2
1 2 3
1 2 3 4
1 2 3 4 5
1 2 3 4 5 6
TRUE

As an example of a non-Hamiltonian graph, consider this simple graph on 5 vertices:

Rendered by QuickLaTeX.com

? show hamilton [1] [[1 2 4 5] [2 1 3] [3 2 4 5] [4 1 3] [5 1 3]]
1
1 2
1 2 3
1 2 3 4
1 2 3 5
1 4
1 4 3
1 4 3 2
1 4 3 5
1 5
1 5 3
1 5 3 2
1 5 3 4
FALSE

Note how in this last example, the routine explored all possible paths before giving up and returning FALSE. This is a very inefficient program; there are ways to speed up such a program, some of which are listed in the references here. When I ran this program on the Barnette-Bosák-Lederberg graph, it took several hours, and 4,173,760 calls of the program before it returned FALSE.

Clearly there are many possible improvements which could be made: for example there should be a “calling” program for which you simply enter a graph, and then the above program is used as a driver. Also, printing out all paths as they are formed is unnecessary (although it provides insight into the backtracking approach). The allowable program returns FALSE immediately if the path is empty: this is why in its current form the hamilton program needs a non-empty path at the start. We could also more conventionally enter a graph as a list of edges (for an unordered graph, each edge would be an unordered list of two elements – being the vertices at its ends), and construct an adjacency list from that. But I was only interested in a proof of concept, and in how relatively easy it was to use Logo for it.

Leave a Reply

Your email address will not be published. Required fields are marked *