Seven Bridges to Raku - Part 3: Hamilton
[81.3] Published 9. July 2020.See also: The Introduction | Part 1: Königsberg | Part 2: Euler.
Hamiltonian Path & Circuit
A graph is a Hamiltonian Path (also called traceable path) if we can make a path along the edges so that we visit all the nodes exactly once. We do not have to use all the edges.The graph is a Hamiltonian Circuit (also called Hamiltonian Cycle) if we can connect the start and end nodes.
See en.wikipedia.org/wiki/Hamiltonian_path for more information.
A walk Through
Let us consider Königsberg. Start by removing (discarding) duplicate edges (bridges) between two nodes (land masses), marked with a red cross, to simplify the process.Then connect the nodes without visiting any node more than once, giving a path marked with green edges. We must start somewhere, and I chose «North bank» (1), followed by «Lomse» (2) and «Keniphof» (3):
If we choose the blue edge to «South Bank» (4S), we get a Hamiltonian Path (1 » 2 » 3 » 4S). If we on the other hand choose the orange edge to «North bank» (4N), we get a path that looks like a cycle (1 » 2 » 3 » 4N), except that it does not connect all the edges (as 4S is missing). So it isn't.
Let us try again:
This time we avoided the «Dom Brücke» (marked with a blue cross). Now we get a graph that is a Hamiltonian Circuit.
This simple walk through illustrates the problem. We have to continue trying, until we find a Hamiltonian Path or Hamiltonian Circuit. If we find the former, we must still go on to find the latter. We can only stop when we do find a Hamiltonian Circuit, or we have exhausted the possibilities.
The task is NP-complete (see en.wikipedia.org/wiki/NP-completeness) so the program will take longer and longer time to run through the graph as we add more and more edges (and nodes).
The program is quite simple, really:
File: hamiltonian (only changes from «eulerian» shown)
if $reachable-nodes < $number-of-nodes # [1]
{
say "Not an Eulerian path/trail nor a cycle/circuit (as we have at least \
two graphs).";
exit; # [2]
}
if any(@bridge-count) == 0
{
say "Not an Eulerian path/trail nor a cycle/circuit (as one or more \
nodes are disconnected).";
exit; # [2]
}
if $odd-edges == 0
{
say "Eulerian path/trail & Eulerian cycle/circuit.";
}
elsif $odd-edges == 2
{
say "An Eulerian path/trail.";
}
else
{
say "Not an Eulerian path/trail nor a cycle/circuit.";
}
for %nodes.keys.sort -> $id # [3]
{
@(%next{$id}) = @(%next{$id}) ?? @(%next{$id}).unique !! ();
}
my @ham-path; # [4]
sub traverse ($start, @path is copy) # [5]
{
@path.push($start); # [6]
say ": Hamilton { @path.elems != $number-of-nodes ?? "partial " \
!! "all/check" }: { @path.join(", ") }" if $verbose;
if @path.elems == $number-of-nodes # [7]
{
if any(@(%next{@path[0]})) eq @path[*-1] # [8]
{
@path.push: @path[0]; # [8a]
say "Hamiltonian path & cycle: { path2name(@path) }"; # [8b]
exit; # [8c]
}
say ": Hamiltonian path: { @path.join(" → ") }" if $verbose;
@ham-path.push: @path; # [9]
return; # [9a]
}
return unless %next{$start}; # [10]
for @(%next{$start}) -> $next # [11]
{
next if $next eq any(@path); # [12]
traverse($next, @path); # [13]
}
}
traverse($_, () ) for %nodes.keys.sort; # [14]
if @ham-path # [15]
{
say "Hamiltonian path: { path2name(@(@ham-path[0])) }";
}
else # [16]
{
say "Not a Hamiltonian path/trail nor a cycle/circuit.";
}
sub path2name (@path, $div = " → ") # [17]
{
return @path.map({ %nodes{$_} }).join($div);
}
[1] The program is the same as «eulerian» until we arrive here.
[2] Exit the program (i.e. don't check for Hamilton) if the graph cannot possibly satisfy Hamilton.
[3] Remove duplicate edges. %nodes.keys gives us
all the nodes (the IDs). @(%next{$id}) gives us a list of connected
nodes for the ID given with given $id. We remove duplicates with
.unique, and assign the duplicate free array back. The ternary test
is there to catch nodes without edges, as it would not work out trying to access
an array that isn't there. Note the sort on the keys, so that
we get them in the same order each time we run the program. This reduces entropy,
and makes it possible to write tests, which I will refrain from doing.
[4] We are going to collect Hamiltonian paths here.
[5] The recurive procedure looking for Hamilton (paths and
circuits). The first paramter is the current node, and the second is the path up
to that node, as a list. Note the is copy so that each recursive
call ends up with their own private copy of the path.
[6] Add the current node to the path.
[7] Do we have all the nodes in the path?
[8] Yes; Does the first element in the path (@path[0]) have an
edge to the last element in the path (@path[*-1]). An any
junction (as described in the second part of this article) does the heavy lifting.
If yes, add the first node to the path [8a], print the path [8b], and exit [8c].
[9] We have a Hamilton path (but not a circuit), add it to the list of Hamilton paths.
[10] Return from this recursion if the current node has no edges. (This should not happen, but better safe than sorrow.)
[11] Iterate over all the connected nodes to the current one.
[12] Skip the edge if we have already visited the node on the other end. We use an any
junction for this lookup.
[13] Recursively follow the new node.
[14] Start the show, starting with all the nodes one after each other.
[15] We reach this line if the program has not been killed off, e.g. if we found a Hamiltonian circuit. Print the first Hamiltonian path, if we have any.
[16] No Hamiltonian paths? Say so.
[17] Print the node names, and not the IDs. Specify another charcter than the arrow if you don't like it.
See
docs.raku.org/routine/unique for
more information about unique.
See
docs.raku.org/type/Signature#index-entry-trait_is_copy
for more information about the is copy trait.
Running through our real world sample graphs:
$ ./hamiltonian königsberg.def
Not an Eulerian path/trail nor a cycle/circuit.
Hamiltonian path & cycle: Kneiphof (western island) → North Bank
→ Lomse (eastern island) → South Bank → Kneiphof (western island)
$ ./hamiltonian --verbose königsberg.def
: Kneiphof (western island) has 5 edges.
: Lomse (eastern island) has 3 edges.
: North Bank has 3 edges.
: South Bank has 3 edges.
: Edges: 5 3 3 3
: Number of edges with odd edges: 4
: Number of nodes: 4
: Number of nodes reachable from Kneiphof (western island): 4
Not an Eulerian path/trail nor a cycle/circuit.
: Hamilton partial : K
: Hamilton partial : K, N
: Hamilton partial : K, N, L
: Hamilton all/check: K, N, L, S
Hamiltonian path & cycle: Kneiphof (western island) → North Bank
→ Lomse (eastern island) → South Bank → Kneiphof (western island)
$ ./hamiltonian paris-bridges.def
An Eulerian path/trail.
Hamiltonian path & cycle: Île de la Cité → Right Bank (Rive Droite)
→ Île Saint-Louis → Left Bank (Rive Gauche) → Île de la Cité
$ ./hamiltonian paris-termini.def
Not an Eulerian path/trail nor a cycle/circuit.
Not a Hamiltonian path/trail nor a cycle/circuit.
$ ./hamiltonian paris-termini-bus.def
An Eulerian path/trail.
Hamiltonian path & cycle: Gare d'Austerlitz → Gare du Lyon
→ Gare Saint-Lazare → Gare du Nord → Gare du l'Est → Gare Montparnasse
→ Gare d'Austerlitz
$ ./hamiltonian london-termini.def
Not an Eulerian path/trail nor a cycle/circuit.
Hamiltonian path: Blackfriars Station → Cannon Street Station
→ Liverpool Street Station → Kings Cross & St Pancras Stations
→ Euston Station → Victoria Station → Paddington Station
→ Marylebone Station → Charing Cross Station → Waterloo Station
→ London Bridge Station
$ ./hamiltonian london-termini-bus.def
Not an Eulerian path/trail nor a cycle/circuit.
Hamiltonian path: Blackfriars Station → Kings Cross & St Pancras Stations
→ Cannon Street Station → Charing Cross Station
→ Victoria Station → Paddington Station → Marylebone Station
→ Euston Station → Waterloo Station → Liverpool Street Station
→ London Bridge Station
$ ./hamiltonian st-petersburg-termini.def
Hamiltonian path: Балтийский вокзал\n(Baltic station)
→ Витебский вокзал\n (Vitebsky station)
→ Главный вокзал\n(Moscow station)
→ Финляндский вокзал\n(Finlandic station)
$ ./hamiltonian --verbose st-petersburg-termini.def
: Балтийский вокзал\n(Baltic station) has 1 edges.
: Финляндский вокзал\n(Finlandic station) has 1 edges.
: Главный вокзал\n(Moscow station) has 2 edges.
: Витебский вокзал\n (Vitebsky station) has 2 edges.
: Edges: 2 1 2 1
: Number of edges with odd edges: 2
: Number of nodes: 4
: Number of nodes reachable from Главный вокзал\n(Moscow station): 4
An Eulerian path/trail.
: Hamilton partial : B
: Hamilton partial : B, V
: Hamilton partial : B, V, M
: Hamilton all/check: B, V, M, F
: Hamiltonian path: B → V → M → F
: Hamilton partial : F
: Hamilton partial : F, M
: Hamilton partial : F, M, V
: Hamilton all/check: F, M, V, B
: Hamiltonian path: F → M → V → B
: Hamilton partial : M
: Hamilton partial : M, F
: Hamilton partial : M, V
: Hamilton partial : M, V, B
: Hamilton partial : V
: Hamilton partial : V, M
: Hamilton partial : V, M, F
: Hamilton partial : V, B
Hamiltonian path: Балтийский вокзал\n(Baltic station)
→ Витебский вокзал\n (Vitebsky station)
→ Главный вокзал\n(Moscow station)
→ Финляндский вокзал\n(Finlandic station)
./hamiltonian moscow-termini.def
Not an Eulerian path/trail nor a cycle/circuit.
Hamiltonian path: Рижский вокзал\n(Rizhsky Station)
→ Казанский/Ленинградский/Ярославский вокзал\n
(Kazansky/Leningradsky/Yaroslavsky Station)
→ Курский вокзал\n(Kursky Station) → Киевский вокзал\n(Kiyevsky Station)
→ Павелецкий вокзал\n(Paveletsky Station)
→ Белорусский вокзал\n(Belorussky Station)
→ Савёловский вокзал\n(Savyolovsky Station)
./hamiltonian budapest-termini.def
Not an Eulerian path/trail nor a cycle/circuit (as we have at least two \
graphs).
$ ./hamiltonian budapest-termini+H.def
Not an Eulerian path/trail nor a cycle/circuit (as we have at least two \
graphs).
$ ./hamiltonian prague-termini.def
An Eulerian path/trail.
Hamiltonian path: Hlavní nádraží (Praha hl.n)
→ Nádraží Holešovice (Praha-Holešovice) → Masarykovo nádraží
This was quite fast (except the London Bus network that took about 2.1 seconds to run on my pc), but that is certainly because the graphs are not that big.
Summary
| Graph | One Graph | Eulerian path | Eulerian cycle | Hamiltonian path | Hamiltonian cycle |
| Königsberg Bridges | |||||
| Paris Bridges | |||||
| Paris Termini/Metro | |||||
| Paris Termini/Bus | |||||
| London Termini/Tube | |||||
| Budapest Termini | |||||
| Budapest Termini + H | |||||
| Prague Termini |
Part 4: Executive Power
See the next part; Part 4: Executive Power.