Seven Bridges to Raku - Part 5: Paris Metro
[81.5] Published 25. August 2020.See also: The Introduction | Part 1: Königsberg | Part 2: Euler | Part 3: Hamilton | Part 4: Executive Order.
Paris Metro
In this part we'll look at how to describe a public transportation network as a graph. The Paris Metro Network is a good candidate, as it was introduced in Part 2: Euler, and as it is quite complex.The complexity (mainly a result of the size of it) makes this a daunting task, but we can get away with doing a few stations only. Initially, at least. I have chosen all of line 3b (which sounds more impressive than it is, as it is a very short line with 4 stations only), and the connecting lines 3 and 11 westwards to République (where they connect with each other), shown here as a rectangle shaped graph:
The intermediary stations are only shown with abbreviated names.
The configuration file, with the full names (as well as the abbreviations):
File: paris-shortest-3bis.def
Re: République
Go: Goncort
Be: Belleville
Py: Pyrénées
Jo: Jourdain
PF: Place des Fêtes
Te: Télegraphe
PdL: Porte des Lilas
Pa: Parmentier
RS: Rue Saint-Maur
PL: Père Lachaise
Ga: Gambetta
Pe: Pelleport
SF: Saint-Fergeau
Re Go Metro 11
Go Be Metro 11
Be Py Metro 11
Py Jo Metro 11
Jo PF Metro 11
PF Te Metro 11
Te PdL Metro 11
Re Pa Metro 3
Pa RS Metro 3
RS PL Metro 3
PL Ga Metro 3
Ga Pe Metro 3bis
Pe SF Metro 3bis
SF PdL Metro 3bis
Then we run the (somewhat unfortunately named) script «bridges2svg» to generate a Graphviz configuration file, and the resulting graph:
./bridges2svg paris-shortest-3bis.def
The graph:
Graphviz has given us a graph showing (quite by accident) that both paths from République to Porte des Lilas have the same number of intermediary nodes (6). The fact that the rightmost path (in the graph) have a transfer between lines 3 and 3bis at Gambetta is not very visible. But a parsing program (i.e. a travel planner) should recognize that the line number has changed, and add a transfer time to make that path more costly.
Conclusion: We were able to describe this part if the Paris Metro network without problem.
But what about other parts?
Let us take a look at the western end of line 10 (and the connecting part of line 9), where line 10 has two single track sections:
We have no way of describing a one directional connection (which is a directed graph), but let us try anyway:
File: paris-shortest-10.def
BP: Boulogne\nPont de Saint Cloud
BJJ: Boulogne Jean Jaurès
MAM: Michel-Ange Molitor
CL: Chardon Lagache
M: Mirabeau
JAC: Javel André Citroën
CM: Charles Michels
AEZ: Avenue Émile Zola
LMPG: La Motte Piquet-Grenelle
EA: Église d'Auteuil
MAA: Michel-Ange Auteuil
PA: Porte d'Auteuil
Ex: Exelmans
J: Jasmin
BP BJJ Metro 10
BJJ MAM Metro 10
MAM CL Metro 10
CL M Metro 10
M JAC Metro 10
JAC CM Metro 10
CM AEZ Metro 10
AEZ LMPG Metro 10
JAC EA Metro 10
EA MAA Metro 10
MAA PA Metro 10
PA BJJ Metro 10
J MAA Metro 9
MAA MAM Metro 9
MAM Ex Metro 9
./bridges2svg paris-shortest-10.def
The resulting graph (which looks nothing like the real world metro network):
Now, can you find the shortest path from «Javel André Citroën» (almost in the middle) to «Jasmin» (slightly below to the right) using this graph?
The answer: Metro 10 from «Javel André Citroën» to «Église d'Auteuil» and «Michel-Ange Auteuil», then change to metro 9 and go on to «Jasmin».
We can highlight the path like this:
$ ./bridges-graphviz-directional --highlight="JAC EA MAA J" paris-shortest-10.def > paris-shortest-10-path.dot
$ dot -Tsvg paris-shortest-10-path.dot > paris-shortest-10-path.svg
The highlighting functionaly was added in Part 3: Hamilton to highlight Hamiltonian paths and Circuits, but we can use it to highlight (almost) anything. As we just did.
The other direction is a problem, as metro line 10 is on a one way loop through the area. So we need a way of differentiating between the directions. Here is the network diagram again, zoomed in, and with the two paths shown:
We need a way of specifying a directed edge (a one way connection). This seems like a good idea:
BP BJJ Metro 10 # Both directions, as before
M>JAC Metro 10 # From left to right only
Note that we do not need one from the right to
the left (<), as we can swap the node IDs to do that with the right
arrow, which reads better. (In other words use B>A instead of
A<B.)
Applied to the configuration file:
File: paris-shortest-10-directed.def
BP: Boulogne\nPont de Saint Cloud
BJJ: Boulogne Jean Jaurès
MAM: Michel-Ange Molitor
CL: Chardon Lagache
M: Mirabeau
JAC: Javel André Citroën
CM: Charles Michels
AEZ: Avenue Émile Zola
LMPG: La Motte Piquet-Grenelle
EA: Église d'Auteuil
MAA: Michel-Ange Auteuil
PA: Porte d'Auteuil
Ex: Exelmans
J: Jasmin
BP BJJ Metro 10
BJJ>MAM Metro 10
MAM>CL Metro 10
CL>M Metro 10
M>JAC Metro 10
JAC CM Metro 10
CM AEZ Metro 10
AEZ LMPG Metro 10
JAC>EA Metro 10
EA>MAA Metro 10
MAA>PA Metro 10
PA>BJJ Metro 10
J MAA Metro 9
MAA MAM Metro 9
MAM Ex Metro 9
That was the easy part. Now we have to fix the program...
File: bridges-graphviz-directional (with changes from «bridges-graphviz-turbo» highlighted)
#! /usr/bin/env raku
unit sub MAIN ($file where $file.IO.e && $file.IO.r, :$highlight);
my %nodes;
my %highlight;
my %highlight-node;
if $highlight
{
my @nodes = $highlight.words;
%highlight-node{@nodes[0]} = %highlight-node{@nodes[*-1]} = True
if @nodes[0] ne @nodes[*-1];
my $current = @nodes.shift;
while @nodes
{
my $next = @nodes.shift;
%highlight{"$current $next"} = True;
$current = $next;
}
}
my $directed = False; # [1]
my @input = $file.IO.lines;
for @input -> $line # [1a]
{
if $line ~~ /^(\w+) (\>) (\w+) \s (.*) /
{
$directed = True;
last;
}
}
say $directed # [1b]
?? 'digraph foogrph {'
!! 'graph foogrph {';
for @input -> $line
{
if $line ~~ /^(\w+) \: (.*)/
{
my ($id, $name) = ($0, $1.trim);
$name = $0.trim if $name ~~ /(.*?)\#/;
if $highlight && %highlight-node{$id}
{
say " $id [label = \"$name\" color=\"red\" penwidth=2.0]";
}
else
{
say " $id [label = \"$name\"]";
}
%nodes{$id} = True;
}
elsif $line ~~ /^(\w+) (<[\s\>]>) (\w+) \s (.*) / # [2]
{
my ($from, $direction, $to, $name) = ($0, $1, $2, $3.trim); # [2]
die "No such node $from" unless %nodes{$from};
die "No such node $to" unless %nodes{$to};
$name = $0.trim if $name ~~ /(.*?)\#/;
if $directed # [3}
{
if $highlight # [4]
{
if %highlight{"$from $to"}
{
say " $from -> $to [label = \"$name\" color=\"blue\" penwidth=2.0]";
%highlight{"$from $to"} = False;
}
else
{
say " $from -> $to [label = \"$name\"]";
}
if %highlight{"$to $from"} && $direction ne ">"
{
say " $to -> $from [label = \"$name\" color=\"blue\" penwidth=2.0]";
%highlight{"$to $from"} = False;
}
elsif $direction ne ">"
{
say " $to -> $from [label = \"$name\"]";
}
}
else # [5]
{
say " $from -> $to [label = \"$name\"]"; # [5a]
say " $to -> $from [label = \"$name\"]" if $direction ne ">"; # [5b]
}
}
elsif $highlight && %highlight{"$from $to"} || %highlight{"$to $from"}
{
say " $from -- $to [label = \"$name\" color=\"blue\" penwidth=2.0]";
%highlight{"$from $to"} = %highlight{"$to $from"} = False;
}
else
{
say " $from -- $to [label = \"$name\"]";
}
}
}
say '}';
[1] We have used the undirectional Graphviz «graph». The directional version is called «digraph». The loop (in [1a]) looks for a directional connection, and uses the directional graph if it finds one (in [1b]).
[2] The (<[\s\>]>) part is new. It looks for a space or a >
character. This denotes either an undirectional edge (the space) or a directional edge
(>).
[3] This entire block applies if we have directed graph, where Graphviz requires us to specify both directions separately.
[4] If highlighting has been activated,
[5] No highlighting: Print the first direction [5a], and the second one unless it is a one-directional connection [5b]
The code looks more complicated than it really is. It forms a matrix, where the dimensions are: directed vs undirected (and a connection in one or both directions), and no highlighting vs highlighting (and the connections to highlight).
Then a new version of the shell script wrapper, using this new program:
File: bridges3svg
#! /bin/bash
for file in "$@"
do
ext=${file##*.}
if [ $ext == 'def' ]; then
if [ -f "$file" ]; then
name=${file%.*}
raku bridges-graphviz-directional $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
Generating the graph:
./bridges3svg paris-shortest-10-directed.def
Note that we still have a problem, as it looks like we can travel on line 10 from «Mirabeau» to «Javel André Citroën» and «Église d'Auteuil» without a transfer. The problem is that we don't differentiate between the two directions of travel. A travel planner will trip up over this.
The solution is to split the lines in two logically seperate entities, one for each direction. Let us call them 9w and 10w (in the western direction), and 9e and 10e (in the eastern direction). It doesn't really matter what we call them, as long as the directions are distinctly named (or identified).
File: paris-shortest-10-directed-really.def
BP: Boulogne\nPont de Saint Cloud
BJJ: Boulogne Jean Jaurès
MAM: Michel-Ange Molitor
CL: Chardon Lagache
M: Mirabeau
JAC: Javel André Citroën
CM: Charles Michels
AEZ: Avenue Émile Zola
LMPG: La Motte Piquet-Grenelle
EA: Église d'Auteuil
MAA: Michel-Ange Auteuil
PA: Porte d'Auteuil
Ex: Exelmans
J: Jasmin
BP>BJJ Metro 10e
BJJ>MAM Metro 10e
MAM>CL Metro 10e
CL>M Metro 10e
M>JAC Metro 10e
JAC>CM Metro 10e
CM>AEZ Metro 10e
AEZ>LMPG Metro 10e
LMPG>AEZ Metro 10w
AEZ>CM Metro 10w
CM>JAC Metro 10w
JAC>EA Metro 10w
EA>MAA Metro 10w
MAA>PA Metro 10w
PA>BJJ Metro 10w
BJJ>BP Metro 10w
J>MAA Metro 9w
MAA>MAM Metro 9w
MAM>Ex Metro 9w
Ex>MAM Metro 9e
MAM>MAA Metro 9e
MAA>J Metro 9e
Note that this removed all the undirectional (bidirectional) edges in the definition file. I'll keep the support for undirectional edges, as it is useful in other situations. E.g. the original bridges.
./bridges3svg paris-shortest-10-directed-really.def
We can highlight the path on this one as well:
$ ./bridges-graphviz-directional --highlight="JAC EA MAA J" \
paris-shortest-10-directed-really.def \
> paris-shortest-10-directed-really-path.dot
$ dot -Tsvg paris-shortest-10-directed-really-path.dot \
> paris-shortest-10-directed-really-path.svg
Note that the highlighter will highlight edges in the given direction, if we have a directed graph. But it may choose a different line.
We can fix that. Let us consider Metro lines 8 and 9, and their common section between «Richelieu Drouot» and «République» (north of the city centre). The lines have their own tracks (with line 8 above line 9), so it is perhaps unwise to call it a common section.
./bridges3svg paris-shortest-8+9.def
Now let us try to highlight the entire route of line 8 eastwards:
$ ./bridges-graphviz-directional --highlight="Op RD GB BN SSD R FdC" \
paris-shortest-8+9.def > paris-shortest-8+9A.dot
$ dot -Tsvg paris-shortest-8+9A.dot > paris-shortest-8+9A.svg
That looks reasonable.
If we try to highlight line 9 instead, we are in for a surprise (well, not really, as you were warned):
$ ./bridges-graphviz-directional --highlight="CdALF RD GB BN SSD R Ob" \
paris-shortest-8+9.def > paris-shortest-8+9B.dot
$ dot -Tsvg paris-shortest-8+9B.dot > paris-shortest-8+9B.svg
It still uses line 8 on the common section, simply because it came before line 9 in the configuration file (and the program takes the first edge that fits).
The best way to fix this is adding a way to specify the line. If we do it before a station, it applies from that station onwards:
--highlight="[Metro_8e] CdALF RD GB BN SSD R Ob"
We can get the path we got above manually, like this:
--highlight="[Metro_8e] CdALF [Metro_9e] RD GB BN SSD R [Metro_8e] Ob"
The first one is not necessary, as there is only one line between the those stations. We can get rid of the last one as well, by turning off the line specification:
--highlight="CdALF [Metro_9e] RD GB BN SSD R [] Ob"
Note that splitting on spaces to get the list of station IDs (as the program does) makes it impossible to have spaces in the line names. So I used an underscore instead of a space, actually renaming the lines. I'll get back to fixing that later.
Here is the program, with the changes highlighted:
File: bridges-graphviz-omnidirectional
#! /usr/bin/env raku
unit sub MAIN ($file where $file.IO.e && $file.IO.r, :$highlight);
my %nodes;
my %highlight;
my %highlight-line;
my $highlight-line;
my %highlight-node;
if $highlight
{
my @nodes = $highlight.words;
my $first = @nodes[0] ~~ /^\[(.*)\]$/ ?? @nodes[1] !! @nodes[0];
my $last = @nodes[*-1];
%highlight-node{$first} = %highlight-node{$last} = True if $first ne $last;
my $current = @nodes.shift;
while @nodes
{
if $current ~~ /^\[(.*)\]$/
{
$highlight-line = $0.Str;
$current = @nodes.shift // last;
}
my $next = @nodes.shift // last;
if $next ~~ /^\[(.*)\]$/
{
$highlight-line = $0.Str;
$next = @nodes.shift // last;
}
%highlight{"$current $next"} = True;
%highlight-line{"$current $next"} = $highlight-line if $highlight-line;
$current = $next;
}
}
my $directed = False;
my @input = $file.IO.lines;
for @input -> $line
{
if $line ~~ /^(\w+) (\>) (\w+) \s (.*) /
{
$directed = True;
last;
}
}
say $directed
?? 'digraph foogrph {'
!! 'graph foogrph {';
for @input -> $line
{
if $line ~~ /^(\w+) \: (.*)/
{
my ($id, $name) = ($0, $1.trim);
$name = $0.trim if $name ~~ /(.*?)\#/;
if $highlight && %highlight-node{$id}
{
say " $id [label = \"$name\" color=\"red\" penwidth=2.0]";
}
else
{
say " $id [label = \"$name\"]";
}
%nodes{$id} = True;
}
elsif $line ~~ /^(\w+) (<[\s\>]>) (\w+) \s (.*) /
{
my ($from, $direction, $to, $name) = ($0, $1, $2, $3.trim);
die "No such node $from" unless %nodes{$from};
die "No such node $to" unless %nodes{$to};
$name = $0.trim if $name ~~ /(.*?)\#/;
if $directed
{
if $highlight
{
if ( %highlight{"$from $to"} && ! %highlight-line{"$from $to"} )
|| ( %highlight{"$from $to"} && %highlight-line{"$from $to"}
eq $name )
{
say " $from -> $to [label = \"$name\" color=\"blue\" penwidth=2.0]";
%highlight{"$from $to"} = False;
}
else
{
say " $from -> $to [label = \"$name\"]";
}
if ( %highlight{"$to $from"} && $direction ne ">"
&& ! %highlight-line{"$to $from"} )
|| ( %highlight{"$to $from"} && $direction ne ">"
&& %highlight-line{"$to $from"} eq $name)
{
say " $to -> $from [label = \"$name\" color=\"blue\" penwidth=2.0]";
%highlight{"$to $from"} = False;
}
elsif $direction ne ">"
{
say " $to -> $from [label = \"$name\"]";
}
}
else
{
say " $from -> $to [label = \"$name\"]";
say " $to -> $from [label = \"$name\"]" if $direction ne ">";
}
}
elsif $highlight && %highlight{"$from $to"} || %highlight{"$to $from"}
{
if %highlight-node{"$from $to"} || %highlight-node{"$to $from"}
{
if any(%highlight-line{"$from $to"}, %highlight-line{"$to $from"})
eq $name
{
say " $from -- $to [label = \"$name\" color=\"blue\" penwidth=2.0]";
%highlight{"$from $to"} = %highlight{"$to $from"} = False;
}
else
{
say " $from -- $to [label = \"$name\"]";
}
}
else
{
say " $from -- $to [label = \"$name\" color=\"blue\" penwidth=2.0]";
%highlight{"$from $to"} = %highlight{"$to $from"} = False;
}
}
else
{
say " $from -- $to [label = \"$name\"]";
}
}
}
say '}';
$ ./bridges-graphviz-omnidirectional \
--highlight="[Metro_9e] CdALF RD GB BN SSD R Ob" \
paris-shortest-8+9-fixed.def > paris-shortest-8+9B-fixed.dot
$ dot -Tsvg paris-shortest-8+9B-fixed.dot > paris-shortest-8+9B-fixed.svg
Let us be silly:
$ ./bridges-graphviz-omnidirectional
--highlight="[Metro_9e] CdALF [Metro_8e] RD [Metro_9e] GB [Metro_8e] BN \
[Metro_9e] SSD [Metro_8e] R [] Ob" paris-shortest-8+9-fixed.def \
> paris-shortest-8+9B-silly.dot
$ dot -Tsvg paris-shortest-8+9B-silly.dot > paris-shortest-8+9B-silly.svg
The Space problem
The problem with using underscores in the line IDs is that it shows up in the graph, as shown above. There are several ways of fixing this. We could simply replace underscores with spaces when generating the graph, but I have chosen to introduce line aliases instead.
File: paris-shortest-8+9-alias.def
Op: Opéra
RD: Richelieu Drouot
GB: Grands Boulevards
BN: Bonne Nouvelle
SSD: Strasbourg Saint-Denis
R: République
FdC: Filles du Calvaire
CdALF: Chaussée d'Antin La Fayette
Ob: Oberkampf
:8e: Metro 8\n»Créteil
:8w: Metro 8\n»Boulogne
:9e: Metro 9\n»Montreuil
:9w: Metro 9\n»Sèvres
Op>RD 8e
RD>GB 8e
GB>BN 8e
BN>SSD 8e
SSD>R 8e
R>FdC 8e
FdC>R 8w
R>SSD 8w
SSD>BN 8w
BN>GB 8w
GB>RD 8w
RD>Op 8w
CdALF>RD 9e
RD>GB 9e
GB>BN 9e
BN>SSD 9e
SSD>R 9e
R>Ob 9e
Ob>R 9w
R>SSD 9w
SSD>BN 9w
BN>GB 9w
GB>RD 9w
RD>CdALF 9w
I have used the destinations (final stop) this time, insteaf of «w» (west) and «e» (east), as that is what is signposted on the stations and trains on the Paris Metro.
The final version of the program looks like this, with the changes implementing line aliases highlighted:
File: bridges-graphviz-omnidirectional-alias
#! /usr/bin/env raku
unit sub MAIN ($file where $file.IO.e && $file.IO.r, :$highlight);
my %nodes;
my %highlight;
my %highlight-line;
my $highlight-line;
my %highlight-node;
if $highlight
{
my @nodes = $highlight.words;
my $first = @nodes[0] ~~ /^\[(.*)\]$/ ?? @nodes[1] !! @nodes[0];
my $last = @nodes[*-1];
%highlight-node{$first} = %highlight-node{$last} = True if $first ne $last;
my $current = @nodes.shift;
while @nodes
{
if $current ~~ /^\[(.*)\]$/
{
$highlight-line = $0.Str;
$current = @nodes.shift // last;
}
my $next = @nodes.shift // last;
if $next ~~ /^\[(.*)\]$/
{
$highlight-line = $0.Str;
$next = @nodes.shift // last;
}
%highlight{"$current $next"} = True;
%highlight-line{"$current $next"} = $highlight-line if $highlight-line;
$current = $next;
}
}
my %alias;
my $directed = False;
my @input = $file.IO.lines;
for @input -> $line
{
if $line ~~ /^(\w+) (\>) (\w+) \s (.*) /
{
$directed = True;
last;
}
}
say $directed
?? 'digraph foogrph {'
!! 'graph foogrph {';
for @input -> $line
{
if $line ~~ /^(\w+) \: (.*)/
{
my ($id, $name) = ($0, $1.trim);
$name = $0.trim if $name ~~ /(.*?)\#/;
if $highlight && %highlight-node{$id}
{
say " $id [label = \"$name\" color=\"red\" penwidth=2.0]";
}
else
{
say " $id [label = \"$name\"]";
}
%nodes{$id} = True;
}
elsif $line ~~ /^\:(\w+)\: \s+ (.*) /
{
my $alias = $0.Str;
my $name = $1.Str.trim;
$name = $0.trim if $name ~~ /(.*?)\#/;
%alias{$alias} = $name;
}
elsif $line ~~ /^(\w+) (<[\s\>]>) (\w+) \s (.*) /
{
my ($from, $direction, $to, $name) = ($0, $1, $2, $3.trim);
die "No such node $from" unless %nodes{$from};
die "No such node $to" unless %nodes{$to};
$name = $0.trim if $name ~~ /(.*?)\#/;
if $directed
{
if $highlight
{
if (%highlight{"$from $to"} && ! %highlight-line{"$from $to"}) ||
(%highlight{"$from $to"} && %highlight-line{"$from $to"} eq $name)
{
say " $from -> $to [label = \"{ %alias{$name} // $name }\" \
color=\"blue\" penwidth=2.0]";
%highlight{"$from $to"} = False;
}
else
{
say " $from -> $to [label = \"{ %alias{$name} // $name }\"]";
}
if (%highlight{"$to $from"} && $direction ne ">"
&& ! %highlight-line{"$to $from"} )
|| ( %highlight{"$to $from"} && $direction ne ">"
&& %highlight-line{"$to $from"} eq $name)
{
say " $to -> $from [label = \"{ %alias{$name} // $name }\" \
color=\"blue\" penwidth=2.0]";
%highlight{"$to $from"} = False;
}
elsif $direction ne ">"
{
say " $to -> $from [label = \"{ %alias{$name} // $name }\"]";
}
}
else
{
say " $from -> $to [label = \"{ %alias{$name} // $name }\"]";
say " $to -> $from [label = \"{ %alias{$name} // $name }\"]"
if $direction ne ">";
}
}
elsif $highlight && %highlight{"$from $to"} || %highlight{"$to $from"}
{
if %highlight-node{"$from $to"} || %highlight-node{"$to $from"}
{
if any(%highlight-line{"$from $to"}, %highlight-line{"$to $from"})
eq $name
{
say " $from -- $to [label = \"{ %alias{$name} // $name }\" \
color=\"blue\" penwidth=2.0]";
%highlight{"$from $to"} = %highlight{"$to $from"} = False;
}
else
{
say " $from -- $to [label = \"{ %alias{$name} // $name }\"]";
}
}
else
{
say " $from -- $to [label = \"{ %alias{$name} // $name }\" \
color=\"blue\" penwidth=2.0]";
%highlight{"$from $to"} = %highlight{"$to $from"} = False;
}
}
else
{
say " $from -- $to [label = \"{ %alias{$name} // $name }\"]";
}
}
}
say '}';
$ ./bridges-graphviz-omnidirectional-alias \
--highlight="[9e] CdALF RD GB BN SSD R Ob" \
paris-shortest-8+9-alias.def > paris-shortest-8+9B-alias.dot
$ dot -Tsvg paris-shortest-8+9B-alias.dot > paris-shortest-8+9B-alias.svg
It does not look very nice in practice. A better solution would perhaps have been to use different colours for each line, as in a normal metro map. But then we'd loose the information about the direction again (as described in the 10 & 9 example).
The graph is really meant as a way of making sure that we got the definition file right, so it does not really matter that the readability and user friendliness of the graphs are missing.
Lines causing problems
Line 7bis, the other short line (in addidion to 3bis, which we started this article with), has a one-way loop at the eastern end:
But this does not cause any new problems, as «Place des Fetes» is regarded as the eastern terminus. (That means that each direction is distinct, and it works out.)
Lines 7 and 13 have branches, line 13 in the northern end, and line 7 in the southern end, shown here without intermediary stations:
We are unable to cope with branches, so must specify them as separate lines. E.g. «13Ln», «13Ls», «13Sn» and «13Ss» for line 13. The downside is that they will show up as separate lines on the shared section (between «Châtillon Montrogue» and «La Fourche»). We can perhaps fix that by specifying a list of lines on the shared section, like this, in the configuration file:
LC>LF 13Ls
SDU>LF 13Ss
LF>CM 13Ls|13Ss
CM>LF 13Ln|13Sn
LF>SDU 13Sn
LF>LC 13Ln
But I'll leave that undecided until the next article...
Wrapping it Up
This article has shown a way of specifying a metro network, with lines and stations. The description file is cumbersome when we have a lot of stations, as we typically do in a metro network. But considering that we started with 7 bridges in Königsberg, the fact that it works out at all is quite impressive.This article is really paving the way for Part 6: Shortest Path, where we'll look into (program) a travel planner for a Metro network. Specify two stations, and it will hopefully give you the shortest path (fastest way to travel) between those stations.
That part is not finished yet.