Seven Bridges to Raku
# Part 2: Euler

by Arne Sommer

See also: The Introduction | Part 1: Königsberg.

An **Eulerian Circuit** requires that all the nodes have an even number of edges. An
**Eulerian Path** has zero or 2 nodes with an odd number of edges, and the rest are
even. This means that every **Eulerian Circuit** is also an **Eulerian Path** (but
not the other way round).

See
en.wikipedia.org/wiki/Eulerian_path for more information about the *eulerian terms*.

The first part of the program resembles the bridges-graphviz program:

File: eulerian-bridges (partial)unit sub MAIN ($file where $file.IO.e && $file.IO.r, :$verbose);
my %bridges; # [1]
my %nodes; # [2]
for $file.IO.lines -> $line
{
if $line ~~ /^(\w+) \: (.*)/
{
my ($id, $name) = ($0, $1.trim);
$name = $0.trim if $name ~~ /(.*?)\#/;
%nodes{$id} = $name; # [2]
}
elsif $line ~~ /^(\w+) \s (\w+) \s (.*) /
{
my ($from, $to, $name) = ($0, $1, $2.trim);
die "No such node $from" unless %nodes{$from};
die "No such node $to" unless %nodes{$to};
$name = $0.trim if $name ~~ /(.*?)\#/;
%bridges{$from}.push: $name; # [1a]
%bridges{$to}.push: $name; # [1b]
}
}

[1] We collect the bridges here. The key is a land mass ID (node), and the value is a list of bridge names (edges) connecting it to other nodes. The hash is populated in [1a] (outward bridge) and [1b] (inward bridge).

[2] We store the

if $verbose
{
for %bridges.keys.sort -> $id # [3]
{
say ": %name{$id} has { %bridges{$id}.elems } bridges."; # [3a]
}
}
my @bridge-count = %bridges.keys.map({ %bridges{$_}.elems}); # [4]
my $odd-bridges = @bridge-count.grep({ ! $_ %% 2 }).elems; # [5]
say ": Number of nodes with odd bridges: $odd-bridges" if $verbose;
if $odd-bridges == 0 # [6]
{
say "Eulerian path/trail & Eulerian cycle/circuit.";
}
elsif $odd-bridges == 2 # [6]
{
say "An Eulerian path/trail.";
}
else
{
say "Not an Eulerian path/trail nor a cycle/circuit.";
}

[3] Iterate over the nodes, printing the name and the number of nodes [3a].

[4] A list of the number of edges for each node. The order is unknown, as it does not matter.

[5] How many of the nodes have an odd number of edges?

[6] Euler or not, as described in the introduction to this section.

Checking it:

$ ./eulerian-bridges königsberg.def
Not an Eulerian path/trail nor a cycle/circuit.
$ ./eulerian-bridges --verbose königsberg.def
: Kneiphof (western island) has 5 bridges.
: Lomse (eastern island) has 3 bridges.
: North Bank has 3 bridges.
: South Bank has 3 bridges.
: Bridges: 3 3 3 5
: Number of nodes with odd bridges: 4
Not an Eulerian path/trail nor a cycle/circuit.

S: Southern Island
N: Northern Island
W: Western Island
S N Narrow Bridge
N W Northern Trail
W S New Bridge

The resulting graph:

Note that Graphviz really doesn't care
about *where* it positions the nodes, as «North» is just a label.
This doesn't really matter for us, as the graph is really an abstraction.

$ ./eulerian-bridges test-1.def
Eulerian path/trail & Eulerian cycle/circuit.
$ ./eulerian-bridges --verbose test-1.def
: Northern Island has 2 bridges.
: Southern Island has 2 bridges.
: Western Island has 2 bridges.
: Bridges: 2 2 2
: Number of nodes with odd bridges: 0
Eulerian path/trail & Eulerian cycle/circuit.

That is correct.

Another one, where we break the cycle (by adding two more bridges):

File: test-2.defS: Southern Island
N: Northern Island
W: Western Island
S N Narrow Bridge
N W Northern Trail
W S New Bridge
N S Holland Bridge
S W Royal Bridge

The resulting graph:

$ ./eulerian-bridges test-2.def
An Eulerian path/trail.
$ ./eulerian-bridges --verbose test-2.def
: Northern Island has 3 bridges.
: Southern Island has 4 bridges.
: Western Island has 3 bridges.
: Bridges: 3 3 4
: Number of nodes with odd bridges: 2
An Eulerian path/trail.

What happens if we add an island *without any bridges*?

```
S: Southern Island
N: Northern Island
W: Western Island
E: Easter Island
S N Narrow Bridge
N W Northern Trail
W S New Bridge
```

The resulting graph:

$ ./eulerian-bridges test-3.def
Eulerian path/trail & Eulerian cycle/circuit.
$ ./eulerian-bridges --verbose test-3.def
: Easter Island has 0 bridges.
: Northern Island has 2 bridges.
: Southern Island has 2 bridges.
: Western Island has 2 bridges.
: Bridges: 2 2 2
: Number of nodes with odd bridges: 0
Eulerian path/trail & Eulerian cycle/circuit.

Oops!

It should bail out at the count of 0 for the Easter Island (which indcidentally didn't show up in the «Bridges:» line). Let us fix that:

File: eulerian-bridges-sans-edges (changes only)my @bridge-count =
# %bridges.keys.map({ %bridges{$_}.elems});
%nodes.keys.map({ %bridges{$_} ?? @(%bridges{$_}).elems !! 0 });

The old code (the `#`

line) started with the `%bridges`

hash. The
keys are the nodes, but only nodes *with bridges* end up here. So we switch to the
`%nodes`

hash, which have them all (bridges or not).

The next trick is to look for nodes not in the hash and return a zero instead of the number
of elements in the array we find in the hash - as it is not there. You may remember that I
did just this in the *verbose* block a few lines ago...

if any(@bridge-count) == 0 # [1]
{
say "Not an Eulerian path/trail nor a cycle/circuit (as one or more \
nodes are disconnected).";
}
elsif $odd-bridges == 0
{
...

[1] Checking if any of the values in a list has a certain value is easy with an `any`

junction.

See
docs.raku.org/routine/any,
for more information about the `any`

junction.

Checking it:

$ ./eulerian-bridges-sans-edges test-3.def
Not an Eulerian path/trail nor a cycle/circuit (as one or more nodes \
are disconnected).
$ ./eulerian-bridges-sans-edges --verbose test-3.def
: Eastern Island has 0 bridges.
: Northern Island has 2 bridges.
: Southern Island has 2 bridges.
: Western Island has 2 bridges.
: Bridges: 0 2 2 2
: Number of nodes with odd bridges: 0
Not an Eulerian path/trail nor a cycle/circuit (as one or more nodes \
are disconnected).

Let us try a version where all islands have bridges, but where the graph is actually two separate graphs:

File: test-4.defS: Southern Island
N: Northern Island
W: Western Island
E: Eastern Island
S N Narrow Bridge
N S Northern Trail
W E New Bridge
E W Immaculate Bridge

Checking it:

$ ./eulerian-bridges-sans-edges --verbose test-4.def
Eulerian path/trail & Eulerian cycle/circuit.
$ ./eulerian-bridges-sans-edges --verbose test-4.def
: Eastern Island has 2 bridges.
: Northern Island has 2 bridges.
: Southern Island has 2 bridges.
: Western Island has 2 bridges.
: Bridges: 2 2 2 2
: Number of nodes with odd bridges: 0
Eulerian path/trail & Eulerian cycle/circuit.

Oops again!

We must add a check that all the nodes (islands) are connected:

File: eulerian (with the changes highlighted)unit sub MAIN ($file where $file.IO.e && $file.IO.r, :$verbose);
my %edges;
my %nodes;
my %next; # [1]
for $file.IO.lines -> $line
{
if $line ~~ /^(\w+) \: (.*)/
{
my ($id, $name) = ($0, $1.trim);
$name = $0.trim if $name ~~ /(.*?)\#/;
%nodes{$id} = %nodes{$id} = $name;
}
elsif $line ~~ /^(\w+) \s (\w+) \s (.*) /
{
my ($from, $to, $name) = ($0, $1, $2.trim);
die "No such node $from" unless %nodes{$from};
die "No such node $to" unless %nodes{$to};
$name = $0.trim if $name ~~ /(.*?)\#/;
%edges{$from}.push: $name;
%edges{$to}.push: $name;
%next{$from}.push: $to.Str; # [2]
%next{$to}.push: $from.Str; # [2]
}
}
if $verbose
{
for %nodes.keys.sort -> $id
{
my $count = %edges{$id} ?? @(%edges{$id}).elems !! 0;
say ": %nodes{$id} has $count edges.";
}
}
my @bridge-count =
%nodes.keys.map({ %edges{$_} ?? @(%edges{$_}).elems !! 0 });
say ": Edges: @bridge-count[]" if $verbose;
my $odd-edges = @bridge-count.grep({ $_ %% 2 == False }).elems;
say ": Number of nodes with odd edges: $odd-edges" if $verbose;
my %seen; # [3]
sub recursive ($start) # [4]
{
if %next{$start} # [5]
{
for @(%next{$start}) -> $next # [6]
{
next if %seen{$next}; # [7]
%seen{$next} = True; # [8]
recursive($next); # [9}
}
}
}
recursive(%nodes.keys[0]); # [10]
my $number-of-nodes = %nodes.keys.elems; # [11]
my $reachable-nodes = %seen.keys.elems; # [12]
say ": Number of nodes: $number-of-nodes" if $verbose; # [11]
say ": Number of nodes reachable from \
{ %nodes{%nodes.keys[0]} }: $reachable-nodes" if $verbose; # [12]
if ($reachable-nodes < $number-of-nodes) # [13]
{
say "Not an Eulerian path/trail nor a cycle/circuit \
(as we have at least two graphs).";
}
elsif any(@bridge-count) == 0
{
say "Not an Eulerian path/trail nor a cycle/circuit \
(as one or more nodes are disconnected).";
}
elsif $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.";
}

[1] A directed graph. For each node (ID) we get a list of connecting nodes (one for each bridge, so we can have duplicates). The bridges have been abstracted away.

[2] Here we set up the graph.

[3] Have we seen this edge already (during our traversal)?

[4] A recursive procedure, given a starting node.

[5] If the current node has connecting nodes,

[6] • iterate over the list (of connecting nodes).

[7] • skip a connecting node if we have already visited it.

[8] • mark the connecting node as visited.

[9] • and visit it (call it) recursively.

[10] Start the show at a random edge. We get the first one in the `%nodes`

hash,
whatever that may be. It does not matter which, as the recursion will visit them all (once),
if the nodes are connected.

[11] The total number of nodes.

[12] The number of nodes reachable from the recursion (including the starting node).

[13] Not one graph?

Checking it:

$ ./eulerian test-4.def
Not an Eulerian path/trail nor a cycle/circuit (as we have at least two \
graphs).
$ ./eulerian --verbose test-4.def
: Eastern Island has 2 bridges.
: Northern Island has 2 bridges.
: Southern Island has 2 bridges.
: Western Island has 2 bridges.
: Bridges: 2 2 2 2
: Number of nodes with odd bridges: 0
: Number of nodes: 4
: Number of nodes reachable from Northern Island: 2
Not an Eulerian path/trail nor a cycle/circuit (as we have at least two \
graphs).

We can run this program on our Königsberg Bridges:

$ ./eulerian --verbose königsberg.def
Not an Eulerian path/trail nor a cycle/circuit.
$ ./eulerian --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 nodes 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.

Paris is also dived by a river (the Seine), and it has two islands as well (Île de la Cité and Île Saint-Louis):

The configuration file, with the bridge names:

File: paris-bridges.defR: Right Bank (Rive Droite)
L: Left Bank (Rive Gauche)
C: Île de la Cité
S: Île Saint-Louis
R C Pont Neuf (R) # 1
L C Pont Neuf (L) # 2
L C Pont Saint-Michel # 3
R C Pont au Change # 4
R C Pont Notre-Dame # 5
L C Petit Pont # 6
L C Pont au Double # 7
R C Pont d'Arcole # 8
R S Pont Louis Philippe # 9
S C Pont Saint-Louis # 10
L C Pont de l'Archevêché # 11
L S Pont de la Tournelle # 12
R S Pont Marie # 13
R S Pont de Sully (R) # 14
L S Pont de Sully (L) # 15

Making the graph:

$ ./bridges2svg paris-bridges.def

Or manually, if you enjoy excessive typing:

$ ./bridges-graphviz paris-bridges.def > paris-bridges.dot
$ dot -Tsvg paris-bridges.dot > paris-bridges.svg

The resulting graph (which you can click on to get a larger version):

Fun Fact: «Pont Neuf» («The New Bridge» in English) is the oldest standing bridge across the Seine in Paris.

Checking it:

$ ./eulerian paris-bridges.def
An Eulerian path/trail.
$ ./eulerian --verbose paris-bridges.def
: Île de la Cité has 10 bridges.
: Left Bank (Rive Gauche) has 7 bridges.
: Right Bank (Rive Droite) has 7 bridges.
: Île Saint-Louis has 6 bridges.
: Bridges: 10 7 6 7
: Number of nodes with odd bridges: 2
: Number of nodes: 4
: Number of nodes reachable from Île de la Cité: 4
An Eulerian path/trail.

We got a real world match, albeit only for an *Eulerian path*!

See www.ratp.fr/plans for the official Paris Metro map, or metromap.fr/en for an unofficial but (in my view) better looking version.

I have only included metro lines connecting any two railway stations (without a transfer); line 4, 5, 12, 13 and 14.

File: paris-termini.defS: Gare Saint-Lazare
N: Gare du Nord
E: Gare du l'Est
L: Gare du Lyon
A: Gare d'Austerlitz
M: Gare Montparnasse
M E Metro 4
E N Metro 4
A E Metro 5
E N Metro 5
M S Metro 12
M S Metro 13
L S Metro 14

Making the graph:

$ ./bridges2svg paris-termini.def

Checking it:

$ ./eulerian paris-termini.def
Not an Eulerian path/trail nor a cycle/circuit.
$ ./eulerian --verbose paris-termini.def
: Gare d'Austerlitz has 1 edges.
: Gare du l'Est has 4 edges.
: Gare du Lyon has 1 edges.
: Gare Montparnasse has 3 edges.
: Gare du Nord has 2 edges.
: Gare Saint-Lazare has 3 edges.
: Edges: 1 3 3 2 1 4
: Number of nodes with odd edges: 4
: Number of nodes: 6
: Number of nodes reachable from Gare du Lyon: 6
Not an Eulerian path/trail nor a cycle/circuit.

What about buses, instead of the metro? The same rule applies; only bus lines connecting any two railway terminals are applicable:

File: paris-termini-bus.defS: Gare Saint-Lazare
N: Gare du Nord
E: Gare du l'Est
L: Gare du Lyon
A: Gare d'Austerlitz
M: Gare Montparnasse
A L Bus 24
S N Bus 26
M S Bus 28
L S Bus 29
N E Bus 31
S E Bus 32
M E Bus 39
E N Bus 39
S E Bus 43
E N Bus 43
E N Bus 46
N E Bus 56
A L Bus 61
A L Bus 63
M A Bus 89
M A Bus 91
A L Bus 91
L E Bus 91
E N Bus 91
M S Bus 94

See www.ratp.fr/plan-bus for the official Paris Bus map.

I may have made mistakes compiling the
connections whilst consulting the map. But the bus lines may change at any time, so
may not be correct when you read this *anyway* - even if I got it right .

$ ./bridges2svg paris-termini-bus.def

The resulting graph:

Checking it:

$ ./eulerian paris-termini-bus.def
An Eulerian path/trail.
$ ./eulerian --verbose paris-termini-bus.def
: Gare d'Austerlitz has 6 edges.
: Gare du l'Est has 10 edges.
: Gare du Lyon has 6 edges.
: Gare Montparnasse has 5 edges.
: Gare du Nord has 7 edges.
: Gare Saint-Lazare has 6 edges.
: Edges: 10 7 6 6 5 6
: Number of nodes with odd edges: 2
: Number of nodes: 6
: Number of nodes reachable from Gare du l'Est: 6
An Eulerian path/trail.

See tfl.gov.uk/maps/track/tube for the official London Tube map.

File: london-termini.defP: Paddington Station
M: Marylebone Station
E: Euston Station
K: Kings Cross & St Pancras Stations
L: Liverpool Street Station
LB: London Bridge Station
C: Cannon Street Station
B: Blackfriars Station
W: Waterloo Station
CC: Charing Cross Station
V: Victoria Station
P K Circle/H&C Line
K L Circle/H&C/Metropolitan Line
L C Circle Line
C B Circle/District Line
B V Circle/District Line
V P Circle Line
P M Bakerloo Line
M CC Bakerloo Line
CC W Bakerloo Line
K E Victoria Line
E V Victoria Line
E K Northern Line
E CC Northern Line
CC W Northern Line
K LB Northern Line
W LB Jubilee Line

Tracks shared by several lines are only shown as one connection, with the combined line names (the Circle, District, H&C (Hammersmith & City), Metropolitan).

$ ./bridges2svg london-termini.def

The resulting graph (which you can click on to get a larger version):

Checking it:

$ ./eulerian london-termini.def
Not an Eulerian path/trail nor a cycle/circuit.
$ ./eulerian --verbose london-termini.def
: Blackfriars Station has 2 edges.
: Cannon Street Station has 2 edges.
: Charing Cross Station has 4 edges.
: Euston Station has 4 edges.
: Kings Cross & St Pancras Stations has 5 edges.
: Liverpool Street Station has 2 edges.
: London Bridge Station has 2 edges.
: Marylebone Station has 2 edges.
: Paddington Station has 3 edges.
: Victoria Station has 3 edges.
: Waterloo Station has 3 edges.
: Edges: 3 2 2 2 2 3 4 3 5 2 4
: Number of nodes with odd edges: 4
: Number of nodes: 11
: Number of nodes reachable from Paddington Station: 11
Not an Eulerian path/trail nor a cycle/circuit.

Doing the London Bus Network is *much harder* than
the Paris buses, as there are so many routes. (More than 700 of them, according to
en.wikipedia.org/wiki/London_Buses.)

London has stopped publishing the map showing *all* the routes in central London,
so I had to consult individual maps
for each railway station. I am sure that I have made several mistakes... But that
doesn't really matter as bus routes are changed every now and then *anyway*.

P: Paddington Station
M: Marylebone Station
E: Euston Station
K: Kings Cross & St Pancras Stations
L: Liverpool Street Station
LB: London Bridge Station
C: Cannon Street Station
B: Blackfriars Station
W: Waterloo Station
CC: Charing Cross Station
V: Victoria Station
M V Bus 2
V CC Bus 11
CC L Bus 11
CC C Bus 15
LB C Bus 17
C K Bus 17
M E Bus 18
E K Bus 18
W L Bus 26
P M Bus 27
E K Bus 30
L LB Bus 35
P V Bus 36
L LB Bus 47
W E Bus 59
B K Bus 63
W E Bus 68
E K Bus 73
E K Bus 91
L LB Bus 133
CC W Bus 139
L LB Bus 149
W E Bus 168
CC W Bus 176
P M Bus 205
M E Bus 205
E K Bus 205
K L Bus 205
V W Bus 211
LB L Bus 341
W L Bus 381
L LB Bus 388
V E Bus 390
E K Bus 390
V W Bus 507
W C Bus 521
C LB Bus 521

$ ./bridges2svg london-termini-bus.def

The resulting graph (which you can click on to get a larger version):

Checking it:

$ ./eulerian london-termini-bus.def
Not an Eulerian path/trail nor a cycle/circuit.
$ ./eulerian --verbose london-termini-bus.def
: Blackfriars Station has 1 edges.
: Cannon Street Station has 5 edges.
: Charing Cross Station has 5 edges.
: Euston Station has 12 edges.
: Kings Cross & St Pancras Stations has 9 edges.
: Liverpool Street Station has 10 edges.
: London Bridge Station has 8 edges.
: Marylebone Station has 5 edges.
: Paddington Station has 3 edges.
: Victoria Station has 6 edges.
: Waterloo Station has 10 edges.
: Edges: 5 12 1 9 6 5 10 3 5 8 10
: Number of nodes with odd edges: 6
: Number of nodes: 11
: Number of nodes reachable from Charing Cross Station: 11
Not an Eulerian path/trail nor a cycle/circuit.

See www.metro.spb.ru/uploads/img/map/metromap2019.jpg for the official map.

The graph is rather boring, as the railway terminals all lie on the same metro line M1.

File: st-petersburg-termini.defF: Финляндский вокзал\n(Finlandic station)
M: Главный вокзал\n(Moscow station)
V: Витебский вокзал\n (Vitebsky station)
B: Балтийский вокзал\n(Baltic station)
F M Metro 2
M V Metro 2
V B Metro 2

Note the embedded newlines in the names, as some of them are quite long. Graphviz honours newlines, making a nicer looking graph.

Making the graph:

$ ./bridges2svg st-petersburg-termini.def

Checking it:

$ ./eulerian st-petersburg-termini.def
An Eulerian path/trail.
$ ./eulerian --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 (Vitebsky station): 4
An Eulerian path/trail.

St. Petersburg has a large tram network, but none of the lines connect two railway terminals, according to www.urbanrail.net/eu/ru/pet/tram/petersburg-tram.htm.

See
transport.mos.ru/en/how-to-get »
**Moscow Metro Map** for the official Moscow Metro map. The railway terminals are
poorly marked on the map (in my view), but
en.wikipedia.org/wiki/Moscow_Railway
lists them.

Only metro lines 2, 3 and 5, and suburban train lines D1 and D2 connect two or more terminals.

File: moscow-termini.defBe: Белорусский вокзал\n(Belorussky Station)
KLY: Казанский/Ленинградский/Ярославский вокзал\n(Kazansky/… Station)
Ki: Киевский вокзал\n(Kiyevsky Station)
Ku: Курский вокзал\n(Kursky Station)
Pa: Павелецкий вокзал\n(Paveletsky Station)
Ri: Рижский вокзал\n(Rizhsky Station)
Sa: Савёловский вокзал\n(Savyolovsky Station)
Be Pa Metro 2
Ki Ku Metro 3
Be Ki Metro 5
Ki Pa Metro 5
Pa Ku Metro 5
Ku KLY Metro 5
KLY Be Metro 5
Be Sa D1
Ri KLY D2
KLY Ku D2

Making the graph:

$ ./bridges2svg moscow-termini.def

Checking it:

$ ./eulerian moscow-termini.def
Not an Eulerian path/trail nor a cycle/circuit.
$ ./eulerian --verbose moscow-termini.def
: Белорусский вокзал\n(Belorussky Station) has 4 edges.
: Казанский/Ленинградский/Ярославский вокзал\n(Kazansky/…) has 4 edges.
: Киевский вокзал\n(Kiyevsky Station) has 3 edges.
: Курский вокзал\n(Kursky Station) has 4 edges.
: Павелецкий вокзал\n(Paveletsky Station) has 3 edges.
: Рижский вокзал\n(Rizhsky Station) has 1 edges.
: Савёловский вокзал\n(Savyolovsky Station) has 1 edges.
: Edges: 1 3 4 1 4 3 4
: Number of nodes with odd edges: 4
: Number of nodes: 7
: Number of nodes reachable from Рижский вокзал\n(Rizhsky Station): 7
Not an Eulerian path/trail nor a cycle/circuit.

I'll stop there. Feel free to check the Moscow bus and/or tram network yourself.

See bkk.hu/apps/docs/terkep/turisztikai_tkp.pdf for the official route map.

Let us see if we can connect them with metro and tram lines:

File: budapest-termini.def (without the H lines)D: Déli pályaudvar
K: Keleti pályaudvar
N: Nyugati pályaudvar
D K Metro 2

File: budapest-termini+H.def (with the H lines)
D: Déli pályaudvar
K: Keleti pályaudvar
N: Nyugati pályaudvar
BA: Batthyány tér
BO: Boráros tér
KÖ: Közvágóhíd
ÖR: Örs vezér tere
D BA Metro 2
BA K Metro 2
K ÖR Metro 2
N BO Tram 4
N BO Tram 6
K KÖ Tram 24

Making the graphs:

$ ./bridges2svg budapest-termini.def budapest-termini+H.def
: budapest-termini.def -> budapest-termini.dot
: budapest-termini.dot -> budapest-termini.svg
: budapest-termini+H.def -> budapest-termini+H.dot
: budapest-termini+H.dot -> budapest-termini+H.svg

Without the H lines:

$ ./eulerian budapest-termini.def
Not an Eulerian path/trail nor a cycle/circuit (as we have at least two \
graphs).
$ ./eulerian --verbose budapest-termini.def
: Déli pályaudvar has 1 edges.
: Keleti pályaudvar has 1 edges.
: Nyugati pályaudvar has 0 edges.
: Edges: 0 1 1
: Number of nodes with odd edges: 2
: Number of nodes: 3
: Number of nodes reachable from Nyugati pályaudvar: 0
Not an Eulerian path/trail nor a cycle/circuit (as we have at least two \
graphs).

With the H lines:

$ ./eulerian budapest-termini+H.def
Not an Eulerian path/trail nor a cycle/circuit (as we have at least two \
graphs).
$ ./eulerian --verbose budapest-termini+H.def
: Batthyány tér has 2 edges.
: Boráros tér has 2 edges.
: Déli pályaudvar has 1 edges.
: Keleti pályaudvar has 3 edges.
: Közvágóhíd has 1 edges.
: Nyugati pályaudvar has 2 edges.
: Örs vezér tere has 1 edges.
: Edges: 3 1 2 2 2 1 1
: Number of nodes with odd edges: 4
: Number of nodes: 7
: Number of nodes reachable from Keleti pályaudvar: 5
Not an Eulerian path/trail nor a cycle/circuit (as we have at least two \
graphs).

According to the map there are no bus routes connecting any two stations.

See urbanrail.net/eu/cz/praha/praha.htm (metro) and urbanrail.net/eu/cz/praha/prahatram.htm (tram) for maps. See czech-transport.com/index.php?id=269 for a description of the railway stations.

Let us see if we can connect them with metro and tram lines:

File: prague-termini.defH: Hlavní nádraží (Praha hl.n)
N: Nádraží Holešovice (Praha-Holešovice)
M: Masarykovo nádraží
N H Metro C
N M Tram 6

Making the graph:

$ ./bridges2svg prague-termini.def
: prague-termini.def -> prague-termini.dot
: prague-termini.dot -> prague-termini.svg

Checking it:

$ ./eulerian prague-termini.def
An Eulerian path/trail.
$ ./eulerian --verbose prague-termini.def
: Hlavní nádraží (Praha hl.n) has 1 edges.
: Masarykovo nádraží has 1 edges.
: Nádraží Holešovice (Praha-Holešovice) has 2 edges.
: Edges: 1 2 1
: Number of nodes with odd edges: 2
: Number of nodes: 3
: Number of nodes reachable from Hlavní nádraží (Praha hl.n): 3
An Eulerian path/trail.

Graph |
One Graph |
Eulerian path |
Eulerian cycle |

Königsberg Bridges | |||

Paris Bridges | |||

Paris Termini/Metro | |||

Paris Termini/Bus | |||

London Termini/Tube | |||

London Termini/Bus | |||

St. Peterburg Termini/Metro | |||

Moscow Termini/Metro | |||

Budapest Termini | |||

Budapest Termini + H | |||

Prague Termini |

**Manhattan** is described in the
Mathematics: A Practical Odyssey text book, with some missing bridges in the north.
(So it can be said that this is an abridged example...) It includes tunnels, though. You
can identify, and add, the missing bridges, exclude the tunnels, or use tunnels only.

**Berlin** has only one island (the northern part is called «Museumsinsel»), but it has
a high number of bridges. See
en.wikipedia.org/wiki/Museum_Island
for a map with *some* of the bridges. (There are more...)

**Cairo** has a lot of islands in the Nile, but they are not bridged to each other (so to
speak), so they are not much fun to do.

Feel free to find other examples, and test them. It would be nice to get a real life
life example of an **Eulerian cycle**!

See the next part; Part 3: Hamilton.