Seven Bridges to Raku - Part 2: Euler

[81.2] Published 9. July 2020.

Eulerian Path & Circuit

Now we can write a program that decides if a given graph is an Eulerian Path (also called Eulerian Trail) and an Eulerian Circuit (also called Eulerian Cycle).

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 name of the node this time, as we need to look it up later.

File: eulerian-bridges (the rest)

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.

Abstract Bridges

Testing the program is a good idea. Let us create some graphs that may or may not satisfy Euler:

File: test-1.def:

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.def

S: 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?

File: test-3.def

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.def

S: 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

There are other cities with a similar topology to Königsberg that you can look at, if you find Königsberg too obscure.

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.def

R: 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!

Paris Termini

We can apply Euler on other structures than land masses and bridges. E.g. the Paris railway terminals, and the metro network connecting them.

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.def

S: 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.def

S: 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.

London Termini

We can do this for London as well. I have excluded Moorgate Station (which I don't consider a significant enough terminal) and Fenchurch Street Station (as it isn't served by the tube).

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

File: london-termini.def

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

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.

File: london-termini-bus.def

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.

St. Petersburg Termini

St. Petersburg has 4 railway terminals.

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.def

F: Финляндский вокзал\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.

Moscow Termini

Moscow has 9 railway terminals, 3 of which are bundled together.

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.def

Be: Белорусский вокзал\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.

Budapest Termini

Budapest has 3 railway terminals, or 7 if we include the H lines (H5-H8).

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.

Prague (Praha)

Prague has 1 railway terminal (of local interest only) and two through‐running stations served by international trains:

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.def

H: 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.

Summary

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

Other Cites

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!

Part 3: Hamilton

See the next part; Part 3: Hamilton.

Links

About me
Keyword Index
Raku Courses
Beginning Raku (book)
RSS Feed
Code (zip)
Reddit Comments