Seven Bridges to Raku

Part 5:
Paris Metro

by Arne Sommer

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.