Seven Bridges to Raku - Part 1: Königsberg

See also: The Introduction.

Königsberg

The German city of Königsberg ceased to exist as such in 1945. The Russians annexed it (in accordance with the Yalta Conference), and renamed it Kaliningrad.

Königsberg was divided in a northern and southern part by the Pregel River, which had two islands; Kneiphof and Lomse. It also had seven bridges crossing the river between the two banks and the islands:

The problem was to decide if it is possible to cross all seven bridges only once, regardless of direction, and without cheating (e.g. using a boat).

(One can but speculate whether the students at the University of Königsberg (founded in 1544) spent their time running around trying to solve the Seven Bridges of Königsberg problem, on their own accord, or with the active support of their professors.)

In Graph theory, the land masses are the nodes, and the bridges are the edges (undirected, in this case). The internal distances on land has been abstracted away when we make it into a graph, so the distance between e.g. bridges 2 and 7 on the South Bank is zero.

Solving the Seven Bridges of Königsberg problem in a generic way, allowing us to specify different cities, islands and bridges, requires a configuration file where we set up the dependencies. So let us start with that:

S: South Bank
N: North Bank
K: Kneiphof (western island)
L: Lomse (eastern island)

N K Krämer Brücke   # 1
K S Grüne Brücke    # 2
K S Köttel Brücke   # 3
N K Schmiede Brücke # 4
N L Holz Brücke     # 5
K L Dom Brücke      # 6
S L Hohe Brücke     # 7

Start with the land masses (nodes). The first part is the ID (of one or more characters; letters, digits and underscores only, i.e. a string that is accepted by the \w regex), followed by a : (colon). The rest of the line is the name.

Then do the bridges (edges). The first two values are the IDs of the two land masses the bridge is connecting. The order of the IDs does not matter. The rest of the line is the name of the bridge.

Note that the names may contain a comment (which will be ignored), starting with a # (hash) character. I have added the bridge numbers from the illustration as comments. Any leading or trailing spaces are removed from the name as well. Also note that the program will ignore empty lines, and lines that it does not recognize.

You may wonder if I got the dependencies right. The fact that I have used the original names for the bridges instead of the numbers doesn't really help.

But we can write a program that creates the graph:

The graph has been created with the Graphviz program, also described in the Pokemon Chiao, Raku article.

This is the program doing the first part of the job; reading the configuration file and creating a Graphviz «dot» file. It prints to STDOUT (as does Graphviz, which we'll present later), so the user must redirect the output:

unit sub MAIN ($file where $file.IO.e && $file.IO.r);  # [1]

my %nodes;                                             # [2]

say 'graph foogrph {';                                 # [3]

for $file.IO.lines -> $line                            # [4]
{
  if $line ~~ /^(\w+) \: (.*)/                         # [5]
  {
    my ($id, $name) = ($0, $1.trim);                   # [6]
    $name = $0.trim if $name ~~ /(.*?)\#/;             # [7]
    say "  $id [label = \"$name\"]";                   # [8]
    %nodes{$id} = True;                                # [2a]
  }
  elsif $line ~~ /^(\w+) \s (\w+) \s (.*) /            # [9]
  {
    my ($from, $to, $name) = ($0, $1, $2.trim);        # [10]
    die "No such node $from" unless %nodes{$from};     # [11]
    die "No such node $to"   unless %nodes{$to};       # [12]

    $name = $0.trim if $name ~~ /(.*?)\#/;             # [7]
    say "  $from -- $to [label = \"$name\"]";          # [13]
  }
                                                       # [14]
}

say '}';                                               # [3a]

[1] Ensure that we specify a file (that exists and is readable) as argument.

[2] We note the existence of the nodes (indexed by the IDs) here. The value is set to True when we encounter a new node [2a].

[3] The start and end [3a] tags of the Graphviz specification.

[4] For each line in the configuration file,

[5] Is it a land mass (node)?

[6] Get the ID and the name. Note the usage of trim to get rid of leadning and trailing space characters. (If you only want to get rid of spaces on one end, use trim-leading or trim-trailing instead.)

[7] If the name contains a #, it is a comment that should be removed.

[8] Print the Graphviz line for the land mass (node).

[9] Is it a bridge (edge)?

[10] Get the two land masses (nodes) that the bridge (edge) connects, and the bridge name.

[11] Terminate the program if the first land mass doesn't exist.

[12] Ditto for the second one.

[13] Print the Graphviz line for the bridge (edge).

[14] Note the missing else here. The program silently ignores all other lines in the configuration file.

See docs.raku.org/routine/trim, docs.raku.org/routine/trim-leading and docs.raku.org/routine/trim-trailing for more information about trim and family.

Running it:

$ ./bridges-graphviz königsberg.def > königsberg.dot

The resulting Graphviz file, in case you are interested:

graph foogrph {
  S [label = "South Bank"]
  N [label = "North Bank"]
  K [label = "Kneiphof (western island)"]
  L [label = "Lomse (eastern island)"]
  N -- K [label = "Krämer Brücke"]
  K -- S [label = "Grüne Brücke"]
  K -- S [label = "Köttel Brücke"]
  N -- K [label = "Schmiede Brücke"]
  N -- L [label = "Holz Brücke"]
  K -- L [label = "Dom Brücke"]
  S -- L [label = "Hohe Brücke"]
}

It looks somewhat similar to the configuration file, and it is actually doable to create and edit them manually.

Then we can use Graphviz to build the graph, e.g. as a SVG (Scalable Vector Graphics) file:

$ dot -Tsvg königsberg.dot > königsberg.svg

This gives us the graph I showed earlier.

Comparing the graph with the map like illustration shows that I got it right. (It is much easier to look for errors in this graph, than in the configuration file.)

Two Bridges with One Stone

$ ./bridges-graphviz königsberg.def > königsberg.dot
$ dot -Tsvg königsberg.dot > königsberg.svg

We can combine them with a shell script wrapper:

#! /bin/bash

for file in "$@"
do
  ext=${file##*.}
  if [ $ext == 'def' ]; then
    if [ -f "$file" ]; then
      name=${file%.*}
      raku bridges-graphviz $name.def > $name.dot
      dot -Tsvg $name.dot > $name.svg
      echo -e ": $file -> $name.dot"
      echo -e ": $name.dot -> $name.svg"
    else
	echo -e "File $file does not exist";
    fi
  else
    echo -e "Ignoring file without .def extension: $file"
  fi
done

Note that it will (probably) only work if run from the same directory as the Raku script and the configuration files. Also note that it will happily overwrite existing files, by design. It requires the configuration file to have a «.def» extension, to minimize the risk of accidentally overwriting files it should not.

Running it:

$ ./bridges2svg königsberg.def 
: königsberg.def -> königsberg.dot
: königsberg.dot -> königsberg.svg

$ ./bridges2svg königsberg.dot
Ignoring file without .def extension: königsberg.dot

We can use it to generate several graphs at the same time, e.g.:

$ ./bridges2svg königsberg.def paris-bridges.def 
: königsberg.def -> königsberg.dot
: königsberg.dot -> königsberg.svg
: paris-bridges.def -> paris-bridges.dot
: paris-bridges.dot -> paris-bridges.svg

The Paris Bridges graph will be presented in the next part.

Part 2: Euler

See the next part; Part 2: Euler.