GNUstep cookbook: Hamiltonian cycles.

[Marko Riedel]

Hi all,

I have added a new recipe to the cookbook. It uses backtracking to
compute Hamiltonian cycles in four types of graphs: cycles (trivial,
mostly for testing purposes), complete graphs, square grids and a
graph that consists of a grid and two handles. You might enjoy adding
your own graphs -- it's easy.

The URL is http://www.gnustep.it/marko/.

Here is an excerpt from the cookbook that describes the recipe:

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
{\tt 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.


Let me know if there are any problems with the TGZ or ZIP files or the
recipe itself. BTW Nicolas -- maybe it's time for a new web edition?
That would be terrific.


Best regards,

Marko Riedel

-- 
+------------------------------------------------------------+
| Marko Riedel, EDV Neue Arbeit gGmbH, mriedel@neuearbeit.de |
| http://www.geocities.com/markoriedelde/index.html          |
+------------------------------------------------------------+