Hamiltonian Cycles and Interface Programming

This time round, I'd like to illustrate the (surprisingly?) extensive possibilities of adding interactive controls to demonstrations. In fact, Mathematica seems to fall only just short of what you could achieve with a 'proper' visual programming language.

For the purposes of illustration, I will use the classic graph theory problem of finding a Hamiltonian Cycle, in the popular geographical context. More specifically, I will program an application allowing the user to:

1. Select a number of countries, where the selection is illustrated on a map
2. If possible, find a closed-loop ground journey around those countries, passing through each one exactly once and returning to the starting location
3. Switching between continents where they wish the task to be performed

The result will look like this:

The first step in achieving the above is to set up the list of countries for a given continent (say, Europe), where the user can click on their names to toggle them on / off.

The appropriate control is TogglerBar, and we specify it to store the dynamically updated user's selection under SelectionEurope. Country names are to be displayed vertically and are obtained using the CountryData function. The control is then embedded within a Pane of a specified size, with a vertical scrollbar.

Next, we define a function ContourEurope that will return a Polygon in the shape of a given European country.

The polygon is obtained using  CountryData, has a black edge and is filled with different shades of gray, depending on whether the specified country is a member of SelectionEurope. 

Similarly, the function CentreEurope below uses CountryData to obtain the latitude and longitude of the center of a given country, and then reverses them to match the on-screen width and height.

We now need something to turn our list of chosen countries into a graph, specifying the way in which we can move between them (e.g. that we can move from Spain directly to France, but not to Germany). The following function does this for a given list of countries x :

For every country x[[i]] in x (i.e. i ranging from 1 to Length[x]), the function obtains all neighbors of this country using CountryData, and then takes the Intersection of the set of neighbors with part of x that remains after dropping the first i countries. In other words, we want those neighbors of i which:

1. are also members of the selection x
2. appear after i on the list

where (2) is because we don't want to connect i with those neighbors which have already been connected with i during previous iterations of Do (e.g. once we add the connection France -> Germany in the graph, we don't want to add Germany -> France later on: the graph is obviously 'undirected'). We then use the /@ operator to apply a function (x[[i]] -> #)& to the obtained list of neighbours, e.g. if the i-th country in x is France and the neighbors under consideration are {Spain, Germany}, then mapping the function yields {France -> Spain, France -> Germany}. The resulting connections are then added to list using Join, before moving on to the next country (numbered i+1). The final value of list is what the function returns.

With this, we may set up another interactive component: a Button that will make Mathematica attempt to find a cycle within the graph corresponding to the selected list of countries, and store it under CycleEurope. This is done using HamiltonianCycles, a procedure that Needs the GraphUtilities package to be loaded first.

We may now combine all the defined components in a Row as follows:

This puts first (leftmost) the list of countries to choose from, and puts the said button last (rightmost). In between, we place some dynamically updated Graphics. The latter consists of the contours of all countries (obtained by mapping the function ContourEurope onto the list of all countries CountryData["Europe"]), as well as a red thick line (a Polygon with no filling) connecting the center coordinates of the chosen countries in the order prescribed by CycleEurope (again, this is obtained by using /@ to apply the appropriate function to all elements of the respective list).

We can construct the controls for other continents by simply changing the variable names (e.g. CycleEurope to CycleAfrica), and then combine them by means of TabView, allowing the user to switch between them using tabs.

Unfortunately, I'm unable to embed the resulting app here, as some of the interactive controls used are currently disabled as 'unsafe' in browser mode (hope this changes soon). To see the final outcome, download the Mathematica source code (.nb), or download the .cdf version, accessible with the free CDF Player.