DEV Community

Cover image for Building Map::Tube::<*> maps, a HOWTO: routing relative reality
Paul Cochrane đŸ‡ȘđŸ‡ș
Paul Cochrane đŸ‡ȘđŸ‡ș

Posted on • Originally published at peateasea.de on

Building Map::Tube::<*> maps, a HOWTO: routing relative reality

#perl #git

The previous post focused on adding more lines to the network and adding colour to those lines. This time, we’ll add another line, but now the map will better match reality. This will allow us to start finding routes between stations on the network.

Building complexity

It’s time to get a bit trickier. In the real tram network in Hannover, the main hub is actually the station Kröpcke and not Hauptbahnhof as we’ve been using so far. Therefore, if we want to add further lines, we’ll have to add this station and route the lines through it correctly. Doing so allows us to do some cool things, like planning routes between seemingly disjoint parts of the network.

The plan right now is to add Linie 4 from Garbsen to Roderbruch.1 Here are the stations we want to add along with their IDs and their station links:

Station ID Links
Garbsen H10 H11
Laukerthof H11 H10, H12
Kröpcke H12 H11, H13, H3, H4, H7
Kantplatz H13 H12, H14
Roderbruch H14 H13

As in previous posts, I’ve continued the numbering from where I left off. This time, Garbsen is the westernmost station along Linie 4 and hence the “first” one along that line.

Looking at the links we have for Kröpcke in the table, we can see that things are getting more complicated, especially at this particular station. Since this node is so central to the network, we expect complexity to be concentrated here. To manage this increase in complexity we’ll continue using tests to guide the map’s evolution. Also, note that the links connecting Laatzen and Allerweg to Hauptbahnhof will need to change because these stations will now be connected to Kröpcke.

Many more much smaller steps

To start making these changes, we’ll need some tests. Fortunately, we already have a good structure in t/map-tube-hannover.t that we can build upon.

What’s the smallest incremental change that we can think of? Well, the network should now have three lines, so we update the “number of lines” test to check for that condition:

my $num_lines = scalar @{$hannover->get_lines};
is( $num_lines, 3, "Number of lines in network correct" );
Enter fullscreen mode Exit fullscreen mode

Running the test file, we see that this will cause the first test failure:

$ prove -lr t/map-tube-hannover.t
t/map-tube-hannover.t .. 1/?
# Failed test 'Number of lines in network correct'
# at t/map-tube-hannover.t line 15.
# got: '2'
# expected: '3'
# Looks like you failed 1 test of 4.
Enter fullscreen mode Exit fullscreen mode

and drive us to add the new line, Linie 4:

    "lines" : {
        "line" : [
            {
                "id" : "L1",
                "name" : "Linie 1",
                "color" : "red"
            },
            {
                "id" : "L7",
                "name" : "Linie 7",
                "color" : "blue"
            },
            {
                "id" : "L4",
                "name" : "Linie 4",
                "color" : "#f9a70c"
            }
        ]
    },
Enter fullscreen mode Exit fullscreen mode

Here I’ve used an RGB colour for the line to show how this variant of specifying colour works. I found the colour by loading the PDF of the Üstra “Netzplan U” into Gimp and using the colour picker tool.

Managing expectations

From prior experience, we expect the tests to continue to fail, but for a different reason:

$ prove -lr t/map-tube-hannover.t
t/map-tube-hannover.t .. # Line id L4 consists of 0 separate components

    # Failed test 'Hannover'
    # at /home/cochrane/perl5/perlbrew/perls/perl-5.38.3/lib/site_perl/5.38.3/Test/Map/Tube.pm line 196.
    # Line id L4 defined but serves no stations (not even as other_link)

    # Failed test 'Hannover'
    # at /home/cochrane/perl5/perlbrew/perls/perl-5.38.3/lib/site_perl/5.38.3/Test/Map/Tube.pm line 196.
    # Looks like you failed 2 tests of 14.
Enter fullscreen mode Exit fullscreen mode

These errors are what we expect: the validation tests are telling us that Linie 4 isn’t connected to anything and doesn’t have a station attached to it.

To build the new line incrementally, we’ll first add only the stations from Garbsen to Kröpcke. Then we’ll connect the new line to the network by connecting Kröpcke to Hauptbahnhof. Later, we’ll add the remaining stations.

To begin, add these station entries after Misburg:

            {
                "id" : "H10",
                "name" : "Garbsen",
                "line" : "L4",
                "link" : "H11"
            },
            {
                "id" : "H11",
                "name" : "Laukerthof",
                "line" : "L4",
                "link" : "H10,H12"
            },
            {
                "id" : "H12",
                "name" : "Kröpcke",
                "line" : "L1,L4,L7",
                "link" : "H3,H11"
            }
Enter fullscreen mode Exit fullscreen mode

Running the test file gives this error:

$ prove -lr t/map-tube-hannover.t
t/map-tube-hannover.t .. # Not every station reachable from every other station -- map has 2 separate components; e.g., stations with ids H1//H10

    # Failed test 'Hannover'
    # at /home/cochrane/perl5/perlbrew/perls/perl-5.38.3/lib/site_perl/5.38.3/Test/Map/Tube.pm line 196.
    # Looks like you failed 1 test of 14.
Enter fullscreen mode Exit fullscreen mode

That’s very odd. That wasn’t an error I was expecting after this change. After all, the new line should connect to the previously defined lines.

What can the message

map has 2 separate components; e.g., stations with ids H1//H10
Enter fullscreen mode Exit fullscreen mode

mean? How could we debug this situation?

Visual debugging

One thing we can do is to convert the map into an image with map2image.pl and see if anything looks out of place:

$ perl bin/map2image.pl
Enter fullscreen mode Exit fullscreen mode

Running the above command generates this image:

Graphviz graph showing nodes and their connectivity in the Hannover tram network for Linie 1, 4 and 7 with a broken connection between Kröpcke and Hauptbahnhof

The problem is much clearer now! We can see that although there’s a link from Kröpcke to Hauptbahnhof, there’s no link from Hauptbahnhof back to Kröpcke. Adding that link (i.e. H12) to Hauptbahnhof:

            {
                "id" : "H3",
                "name" : "Hauptbahnhof",
                "line" : "L1,L7",
                "link" : "H2,H4,H7,H8,H12"
            },
Enter fullscreen mode Exit fullscreen mode

gets the test suite to pass again:

$ prove -lr t/map-tube-hannover.t
t/map-tube-hannover.t .. ok
All tests successful.
Files=1, Tests=4, 0 wallclock secs ( 0.03 usr 0.00 sys + 0.54 cusr 0.06 csys = 0.63 CPU)
Result: PASS
Enter fullscreen mode Exit fullscreen mode

Great!

Threading the new line through the network

Now we’re in a position to add the remaining stations on Linie 4. We drive this change by adding a route from Garbsen to Roderbruch to our routes tests. This then checks that these stations are part of the network:

my @routes = (
    "Route 1|Langenhagen|Sarstedt|Langenhagen,Kabelkamp,Hauptbahnhof,Laatzen,Sarstedt",
    "Route 4|Garbsen|Roderbruch|Garbsen,Laukerthof,Kröpcke,Kantplatz,Roderbruch",
    "Route 7|Wettbergen|Misburg|Wettbergen,Allerweg,Hauptbahnhof,Vier Grenzen,Misburg",
);

ok_map_routes($hannover, \@routes);
Enter fullscreen mode Exit fullscreen mode

This test will hopefully fail because we haven’t added the Roderbruch station yet:

$ prove -lr t/map-tube-hannover.t
t/map-tube-hannover.t .. 1/? Map::Tube::get_node_by_name(): ERROR: Invalid Station Name [Roderbruch]. (status: 101) file /home/cochrane/perl5/perlbrew/perls/perl-5.38.3/lib/site_perl/5.38.3/Map/Tube.pm on line 897
# Tests were run but no plan was declared and done_testing() was not seen.
# Looks like your test exited with 255 just after 3.
Enter fullscreen mode Exit fullscreen mode

Expectations met again! Failing for the right reason means we’re on the right track.2

To continue, we add the remaining stations along Linie 4 and update the list of links for Kröpcke to link to the station Kantplatz:

            {
                "id" : "H12",
                "name" : "Kröpcke",
                "line" : "L1,L4,L7",
                "link" : "H3,H11,H13"
            },
            {
                "id" : "H13",
                "name" : "Kantplatz",
                "line" : "L4",
                "link" : "H12,H14"
            },
            {
                "id" : "H14",
                "name" : "Roderbruch",
                "line" : "L4",
                "link" : "H13"
            }
Enter fullscreen mode Exit fullscreen mode

Running the test suite gives:

$ prove -lr t/map-tube-hannover.t
t/map-tube-hannover.t .. 1/? Map::Tube::get_node_by_name(): ERROR: Invalid Station Name [Kröpcke]. (status: 101) file /home/cochrane/perl5/perlbrew/perls/perl-5.38.3/lib/site_perl/5.38.3/Test/Map/Tube.pm on line 1434
# Tests were run but no plan was declared and done_testing() was not seen.
# Looks like your test exited with 255 just after 3.
Enter fullscreen mode Exit fullscreen mode

Erm, what?? I expected this test to pass. Unfortunately, we got the error

Invalid Station Name [Kröpcke]
Enter fullscreen mode Exit fullscreen mode

What’s going on here?

Scheiïżœ Encoding

As is my wont, this led me down quite the rabbit hole. Yes, another one. To cut a very long story short, the issue here is that the station name contains a non-ascii character, in particular the umlaut â€˜Ă¶â€™.3 If we change the route test to

    "Route 4|Garbsen|Roderbruch|Garbsen,Laukerthof,Kroepcke,Kantplatz,Roderbruch",
Enter fullscreen mode Exit fullscreen mode

and update the station entry in the map file:

            {
                "id" : "H12",
                "name" : "Kroepcke",
                "line" : "L1,L4,L7",
                "link" : "H3,H11,H13"
            },
Enter fullscreen mode Exit fullscreen mode

so that they use oe in place of ö, then the test suite will pass:4

$ prove -lr t/map-tube-hannover.t
t/map-tube-hannover.t .. ok
All tests successful.
Files=1, Tests=4, 1 wallclock secs ( 0.03 usr 0.00 sys + 0.58 cusr 0.06 csys = 0.67 CPU)
Result: PASS
Enter fullscreen mode Exit fullscreen mode

I first mentioned this behaviour in an issue in Map::Tube::Frankfurt. It seems that the Map::Tube version I’m using here (4.03) doesn’t always process UTF-8 input correctly. I haven’t yet worked out the exact reason for this, hence the only way is to avoid umlauts and the sharp-s (ß) and use their ASCII-compatible versions. For German, this means that Ă€ becomes ae, ö becomes oe, ĂŒ becomes ue, and ß becomes ss.5

What’s weird here is that most of the validation tests work. It’s only as soon as one has a non-ASCII character like an umlaut or a sharp-s (ß) in the route name (at least for German maps) that problems seem to appear.

Since we’ve extended the network and now have a working configuration, it’s a good time for a commit:

$ git commit -m "Add Linie 4 from Garbsen to Roderbruch via Kröpcke" share/hannover-map.json t/map-tube-hannover.t
[main 22d482e] Add Linie 4 from Garbsen to Roderbruch via Kröpcke
 2 files changed, 38 insertions(+), 2 deletions(-)
Enter fullscreen mode Exit fullscreen mode

If you convert the map to an image, you’ll find that everything is connected:

Graphviz graph showing nodes and their connectivity in the Hannover tram network for Linie 1, 4 and 7 but with incorrect Hauptbahnhof-Kröpcke connection

The lines do seem to be a bit jumbled up in the graph now, but that’s just an artefact of generating this graph automatically.

Keeping a critical eye open

Looking at this graph made me realise something: it’s wrong.

But Paul! Our tests are passing, it must be correct!

The thing is, the expectations in our tests are incorrect and we need to fix them. If you compare the Üstra “Netzplan U” with the graph above, then you’ll find that Laatzen and Allerweg should connect to Kröpcke and not to Hauptbahnhof as they are currently.

How do we solve this issue? We update the expectations in our routes tests. These tests now look like so:

my @routes = (
    "Route 1|Langenhagen|Sarstedt|Langenhagen,Kabelkamp,Hauptbahnhof,Kroepcke,Laatzen,Sarstedt",
    "Route 4|Garbsen|Roderbruch|Garbsen,Laukerthof,Kroepcke,Kantplatz,Roderbruch",
    "Route 7|Wettbergen|Misburg|Wettbergen,Allerweg,Kroepcke,Hauptbahnhof,Vier Grenzen,Misburg",
);

ok_map_routes($hannover, \@routes);
Enter fullscreen mode Exit fullscreen mode

where, if you look closely, you’ll notice that we’ve squashed Kroepcke between Hauptbahnhof and Laatzen and Allerweg, respectively:6

my @routes = (
    "Route 1|Langenhagen|Sarstedt|Langenhagen,Kabelkamp,Hauptbahnhof,Kroepcke,Laatzen,Sarstedt",
                                                                     ^^^^^^^^^
    "Route 4|Garbsen|Roderbruch|Garbsen,Laukerthof,Kroepcke,Kantplatz,Roderbruch",
    "Route 7|Wettbergen|Misburg|Wettbergen,Allerweg,Kroepcke,Hauptbahnhof,Vier Grenzen,Misburg",
                                                    ^^^^^^^^^
);
Enter fullscreen mode Exit fullscreen mode

Getting by with a little help from our tests

The test suite will now fail right royally. However, the routes test from Test::Map::Tube gives us lots of informative output about what went wrong. We thus get many hints about how to correct things.

$ prove -lr t/map-tube-hannover.t
t/map-tube-hannover.t .. 1/?
# Failed test 'Route 1'
# at t/map-tube-hannover.t line 23.
# got: 'Langenhagen (Linie 1)
# Kabelkamp (Linie 1)
# Hauptbahnhof (Linie 1, Linie 7)
# Laatzen (Linie 1)
# Sarstedt (Linie 1)'
# expected: 'Langenhagen (Linie 1)
# Kabelkamp (Linie 1)
# Hauptbahnhof (Linie 1, Linie 7)
# Kroepcke (Linie 1, Linie 4, Linie 7)
# Laatzen (Linie 1)
# Sarstedt (Linie 1)'

# Failed test 'Route 7'
# at t/map-tube-hannover.t line 23.
# got: 'Wettbergen (Linie 7)
# Allerweg (Linie 7)
# Hauptbahnhof (Linie 1, Linie 7)
# Vier Grenzen (Linie 7)
# Misburg (Linie 7)'
# expected: 'Wettbergen (Linie 7)
# Allerweg (Linie 7)
# Kroepcke (Linie 1, Linie 4, Linie 7)
# Hauptbahnhof (Linie 1, Linie 7)
# Vier Grenzen (Linie 7)
# Misburg (Linie 7)'
# Looks like you failed 2 tests of 5.
t/map-tube-hannover.t .. Dubious, test returned 2 (wstat 512, 0x200)
Failed 2/5 subtests
Enter fullscreen mode Exit fullscreen mode

By the way: converting the map to an image with map2image.pl is very helpful in debugging connection-related problems such as those appearing in the test failures above.

To solve these errors, we need to update Hauptbahnhof to look like the following (we remove H4 and H7 as they should link to Kröpcke):

            {
                "id" : "H3",
                "name" : "Hauptbahnhof",
                "line" : "L1,L7",
                "link" : "H2,H8,H12"
            },
Enter fullscreen mode Exit fullscreen mode

and Kröpcke to look like this (we add in H4 and H7):

            {
                "id" : "H12",
                "name" : "Kroepcke",
                "line" : "L1,L4,L7",
                "link" : "H3,H4,H7,H11,H13"
            },
Enter fullscreen mode Exit fullscreen mode

as well as Laatzen, where we replace H3 (Hauptbahnhof) with H12 (Kröpcke):

            {
                "id" : "H4",
                "name" : "Laatzen",
                "line" : "L1",
                "link" : "H5,H12"
            },
Enter fullscreen mode Exit fullscreen mode

and Allerweg (again, H12 replaces H3):

            {
                "id" : "H7",
                "name" : "Allerweg",
                "line" : "L7",
                "link" : "H6,H12"
            },
Enter fullscreen mode Exit fullscreen mode

The tests should now pass:

$ prove -lr t/map-tube-hannover.t
t/map-tube-hannover.t .. ok
All tests successful.
Files=1, Tests=4, 1 wallclock secs ( 0.03 usr 0.01 sys + 0.54 cusr 0.04
csys = 0.62 CPU)
Result: PASS
Enter fullscreen mode Exit fullscreen mode


 and they do! Yay!

Converting the map into an image with map2image.pl, you should see this output:

Graphviz graph showing nodes and their connectivity in the Hannover tram network for Linie 1, 4 and 7

where most of the connections go through Kröpcke as we’d expect for such a central node.

What’s nice about the network graph now is that it’s starting to look more and more like the actual network graph in the Üstra “Netzplan U”.

Since we’ve reached a new stable state of the code, let’s commit this change and move on.

$ git commit share/hannover-map.json t/map-tube-hannover.t -m "Fix connections through Kröpcke
>
> Routes 1 and 7 in the tests were no longer correct as they didn't reflect
> reality. The stations Allerweg and Laatzen were actually connected to
> Kröpcke and not to Hauptbahnhof. This change fixes the issue and ensures
> the network better reflects the actual tram network in Hannover."
[main f931ec1] Fix connections through Kröpcke
 2 files changed, 6 insertions(+), 6 deletions(-)
Enter fullscreen mode Exit fullscreen mode

Getting to the route of the problem

Now that our map has gained more complexity, it means that we can start to do interesting things. Map::Tube is, after all, a routing framework. Thus, we can start planning routes across lines, not only within lines as we’ve been doing so far. In other words, we can now look for a route requiring us to change trains and transfer to another line. To search for routes, we use the get_shortest_route() method.

Let’s build a small program that we can use to find routes within our network. Then we can try finding a route from Garbsen (on Linie 4) to Sarstedt (on Linie 1) as an example.

I’m going to avoid creating tests for the program and I’ll skip input validation7 so that we can get things up and running quickly. These skipped steps are left as an exercise for the reader. 😉

Create a file called bin/get_route.pl in your favourite editor and enter this code:

use strict;
use warnings;

use lib qw(lib);

use Map::Tube::Hannover;

# grab the start and end stations of the route
my $from = $ARGV[0];
my $to = $ARGV[1];

# show how to get from one to the other
my $hannover = Map::Tube::Hannover->new;
print $hannover->get_shortest_route($from, $to), "\n";

# vim: expandtab shiftwidth=4
Enter fullscreen mode Exit fullscreen mode

This should be sufficient for our needs. As with map2image.pl, we set the lib path explicitly so that we don’t have to mention -I lib on the command line. Then we import the Map::Tube::Hannover module. We grab the start and end stations of our route from the @ARGV array because we’re supplying this information via command line arguments. Thus, we’ll run the program like so:

$ perl get_route.pl 'start station name' 'end station name'
Enter fullscreen mode Exit fullscreen mode

We then create an instance of a Map::Tube::Hannover object and call the get_shortest_route() method on that. The names of our start and end stations are passed as arguments to get_shortest_route(). We print the result of this method call to the terminal, thus showing the route to take.

Let’s see it in action. In our first example, we want to find a route from Garbsen to Sarstedt:

$ perl bin/get_route.pl Garbsen Sarstedt
Garbsen (Linie 4), Laukerthof (Linie 4), Kroepcke (Linie 1, Linie 4, Linie 7), Laatzen (Linie 1), Sarstedt (Linie 1)
Enter fullscreen mode Exit fullscreen mode

That was easy, wasn’t it? Now we know that to get from Garbsen to Sarstedt, we have to change trains at Kröpcke.

How do we handle stations with spaces in their names, such as Vier
Grenzen? Simply add quotes around the name when calling the program:

$ perl bin/get_route.pl Garbsen 'Vier Grenzen'
Garbsen (Linie 4), Laukerthof (Linie 4), Kroepcke (Linie 1, Linie 4, Linie 7), Hauptbahnhof (Linie 1, Linie 7), Vier Grenzen (Linie 7)
Enter fullscreen mode Exit fullscreen mode

This example highlights two options for the shortest route: one could change to Linie 1 at Kroepcke and then change to Linie 7 at Hauptbahnhof, or one could change directly to Linie 7 at Kroepcke. Both paths are equivalent ways of getting from Garbsen to Vier Grenzen.

Cool!

That looks like a handy program to have around. Let’s add it to the repository and commit the change:

$ git add bin/get_route.pl
$ git commit -m "Add program to get a route from one station to another"
[main ff27347] Add program to get a route from one station to another
 1 file changed, 17 insertions(+)
 create mode 100644 bin/get_route.pl
Enter fullscreen mode Exit fullscreen mode

Wrapping up

We’ve finally been able to use our module for what we intended it to do: find routes through the railway network. We’ve also seen that it’s useful to have a visual representation of the map as a debugging aid. Also, we’ve maintained our flow, using tests to drive new features and committing changes to Git as soon as the code achieves a suitable stable state.

In the final post in this series, we’ll see how to build connections between stations that aren’t connected directly.

  1. It turns out that suburb of Roderbruch doesn’t have a coat of arms. One of its well-known landmarks is the Telemax tower, hence I used it to make a coat-of-arms-like image for this station in the article’s cover image. ↩

  2. I really, honestly, didn’t intend that pun! ↩

  3. In case you’ve ever wondered, the question mark inside a rotated square is called the replacement character and has the Unicode value U+FFFD. ↩

  4. In German, umlauts can be written with their ASCII equivalents. In other words, one can write the umlauts Ă€, ö and ĂŒ as “ae”, “oe” and “ue”, respectively. ↩

  5. Since I wrote the initial draft of this series, Mohammad has already fixed the issue. If you want to avoid the UTF-8 problems, then you’ll need to install Map::Tube with at least version 4.08. ↩

  6. It turned out to be difficult to show a nice word diff of the change, so this was the best I could do to highlight what was added. ↩

  7. Naughty me! Bad Paul! ↩

Top comments (0)