Subway Route Planner
This  workspace demonstrates "Graph Searching". See dfns.dws/notes.Graphs for an
introduction to graphs.

Source Coding
A subway network is coded in sections, with lists of "stops" (or stations) head-
ed  by  an _exdented_ service or "line" label. For example, London's Circle line
can be coded in one shot as there are no branches:

    South Kensington
    Gloucester Road
    High Street Kensington
    Sloane Square
    South Kensington

The line label is distinguished by appearing in the _first_ column of the source
and the stations that follow must be indented by at least one column.

More  complex  lines  containing branches are coded as separate simple sections,
each headed by the section's line label:

    Ealing Broadway
    Ealing Common
    Acton Town
    Chiswick Park
    Turnham Green

    Kew Gardens
    Turnham Green

    Turnham Green
    Stamford Brook
    Ravenscourt Park
    Barons Court
    West Kensington
    Earl's Court

The  compiler  links  these sections by joining stations with the same name, for
example, Turnham Green in the above.

The comment '//', and all characters to its right, are ignored.

Forks,  such as the one at Turnham Green, should be indicated in the source code
for two reasons. Firstly, without the coding, a trip from one "tine" of the fork
to  another  would  give  no  indication that we must de-train [1] at the fork's
handle  in  order  to continue in the opposite direction. Secondly, there may be
cases where the optimal choice of route should avoid a fork.

[1] For the Brits, "de-train" means "disembark" [2]
[2] For Americans, "disembark" means "un-get-on-the-boat".

For example:

   X───────Y   A trip from A to B would be quicker via X and Y than via F.
   │       │
   A       B   A→X→Y→B takes 3 units, whereas A→F→[change]→F→B takes 4. It seems
   │       │   preferable  to  stay  on the train for an extra stop via X and Y,
   └───┬───┘   than  to get off at F, change platform, and then wait for a train
       │       to B in the opposite direction.

    │ Dyalog's restricted set of line-drawing characters make it  A       B │
    │ difficult to draw a convincing picture of a fork. The dia-  │       │ │
    │ gram  opposite  is intended to show a fork when travelling  └───┬───┘ │
    │ north from C to A or B. In other words, there is no direct      │     │
    │ connection from A to B; we must change trains at C.             C     │

The  following  picture  shows  a fork on London's Northern line. To travel from
Chalk  Farm to Kentish Town, we must change at Camden Town to a north-east-bound
train.  This configuration is indicated in the source code, by symbol '∊' on the
handle of the fork:
                        //               │     │
    Northern            //    Chalk Farm ∘     ∘ Kentish Town
        Chalk Farm      //               │     │
      ∊ Camden Town     //               └──┬──┘
        Kentish Town    //                  │
                        //                  ∘ Camden Town
                        //                  │

This  coding would suggest the following trip. De-training at Camden town is in-
dicated by exdentation (we should leave the train at exdented stations):

          london trip 'Chalk Farm' 'Kentish Town'
    Chalk Farm
        Chalk Farm   Northern
        Camden Town  Northern
    Camden Town
        Camden Town  Northern
        Kentish Town Northern
    Kentish Town

A  4-way-cross, such as the one at "Poplar" on London's Docklands Light Railway,
is  indicated  by a '+'. A trip from All Saints to Blackwall would then show de-
training at Poplar, whereas a trip from All Saints to West India Quay, wouldn't.

                                //                │
    Docklands Light Railway     //                ∘All Saints
        Westferry               //                │
      + Poplar                  //                │
        Blackwall               //                │Poplar
                                //     ───∘───────∘───────∘────
    Docklands Light Railway     //     Westferry  │       Blackwall
        All Saints              //                │
      + Poplar                  //                │
        West India Quay         //                ∘West India Quay
                                //                │

This coding produces the following trip suggestions:

          london trip 'All Saints' 'West India Quay'
    All Saints
        All Saints      Docklands Light Railway
        Poplar          Docklands Light Railway
        West India Quay Docklands Light Railway
    West India Quay

          london trip 'All Saints' 'Blackwall'
    All Saints
        All Saints Docklands Light Railway
        Poplar     Docklands Light Railway
        Poplar     Docklands Light Railway
        Blackwall  Docklands Light Railway

One-Way Sections
A  one-way  section is indicated by an arrow ↓, on the stop at the _entrance_ to
the  section. An example is the loop at the south-west end of London's Picadilly
line. Note that Hatton Cross is also a fork:

      ↓ Heathrow 4              //   ┌─H123─→┐
      ↓ Heathrow 1,2,3          //   ↑       ├──HX──
      ↓∊Hatton Cross            //   └─H4──←─┘
        Heathrow 4


          london trip '4' 'Hat'     ⍝ Heathrow: Terminal 4 → Hatton Cross.
    Heathrow Terminal 4
        Heathrow Terminal 4      Piccadilly
        Heathrow Terminals 1-2-3 Piccadilly
        Hatton Cross             Piccadilly
    Hatton Cross

          london trip '3' '4'       ⍝ Heathrow: Terminal 3 → Terminal 4. (*)
    Heathrow Terminals 1-2-3
        Heathrow Terminals 1-2-3 Piccadilly
        Hatton Cross             Piccadilly
    Hatton Cross
        Hatton Cross             Piccadilly
        Heathrow Terminal 4      Piccadilly
    Heathrow Terminal 4

          london trip '4' '3'       ⍝ Heathrow: Terminal 4 → Terminal 3.
    Heathrow Terminal 4
        Heathrow Terminal 4      Piccadilly
        Heathrow Terminals 1-2-3 Piccadilly
    Heathrow Terminals 1-2-3

(*) There  are better ways to travel between London Heathrow's terminals than by
    taking the tube via Hatton Cross.


// comment


  ∊ on handle of [fork].
  ↓ at start of [one-way section].
  + on [cross].

A simple network can be found in →source←. Try:

      ed notes                          ⍝ review source vector.
      notes trip 'Apple' 'Banana'       ⍝ journey through a fork.
      notes trip 'Pear'  'Onion'        ⍝ show one-way restrictions.

Technical Notes
A [line] typically passes through a number of [stations]:

    Circle: Paddington, Edgware Road, Baker Street, ...

A [station] may host a number of [lines]:

    Baker Street: Circle, Bakerloo, Jubilee, ...

A [stop] is a (line station) pair:

    (Circle Paddington) (Bakerloo Paddington) (Victoria Victoria) ...

A [platform] is a (line station direction) triple:

    (Central Holborn Eastbound) (Northern Archway Southbound) ...

A subway network is represented as a graph with platforms as vertices and tracks
between  platforms as edges. In addition, there is an extra vertex corresponding
with  each station, and extra edges between the station to each platform within.
In other words, there is a notional journey between the station entrance and the
platform on which the train departs or arrives. A trip that involves de-training
to change lines, or in the case of a fork, to change direction on the same line,
is  routed  via the [station] vertex. This routing has the effect of emphasising
line  and  direction  changes  as  exdented  station  names in the final output.
Further, the extra edges between lines provide a weighting against the searching
algorithm's  suggesting  indiscriminate  "line jockeying". It is this extra link
that models the behavioural cost of changing trains.

A  simpler  version of this workspace used only single-track links between stat-
ions.  This  meant  that  there was only a single platform per station per line,
rather  than one for each direction. One-way sections could be accommodated, but
forks  and  crosses  presented  a problem. The current version, which represents
separate  station platforms for each direction, generates approximately twice as
many graph vertices (but the same number of edges).

Line Topology
A subway network can be built from a set of primitive elements, in a way similar
to  a model railway. The detail of the topology is important, as it is this that
directs  the  graph-searching algorithm to find shortest routes. For example, in
the  [fork]  below, we can see that the shortest way from a station on one tine,
to a station on the other, is via the [station] at the handle.


    ⎕ station
    ∘ platform
    ·───→───· directional edge                    ┌───→───┐
    ·───────· bi-directional edge, shorthand for: ·       ·
Simple multi-station two-way line section:

                │       │       │
    Line A:     ⎕       ⎕       ⎕
                │       │       │

One-way line section:

                │       │       │
    Line A:     ⎕       ⎕       ⎕

Multi-line Station:

                │       │       │
    Line A:     ⎕     ┌─┘       ⎕  <= Station serves line A.
                │     │         │
                      │ │
                      └─⎕─┐ <= Station serves lines A and B.
                        │ │
                │         │     │
    Line B:     ⎕       ┌─┘     ⎕  <= Station serves line B.
                │       │       │

                        │       │       │
                        ↑       ⎕       ⎕   Line A:
                        │       │       │
      ···───→───∘───→───∘──┐ ┌←─∘───←───∘───←───···
                │       │  │ │
    Line A:     ⎕       ⎕  └─→──┐
                │       │    │  │
      ···───←───∘───←───∘──←─┘  ∘───→───∘───→───···
                        │       │       │
                        ↑       ⎕       ⎕   Line A:
                        │       │       │


A  cross  is  equivalent  to  a Multi-line station, with the difference that the
station  serves  two  (or  more)  sections of the _same_ line. A figure-of-eight
model railway layout, might include a cross.

                ·       ·
                ↑       ↓
                │       │   Line A:
                │       │
            │   │   │   │   │
            ⎕   ∘───⎕───∘   ⎕   Line A:
            │   │   │   │   │
                │       │
                │       │
                ↑       ↓
                ·       ·

Dyalog APL Navigator
DAN,  the  "Dyalog  APL  Navigator" workspace supplied with Pocket APL, uses the
same  line  topology  as  this  but employs "weighted" graphs to model differing
train  frequencies,  line  closures,  reluctance to change trains, and so forth.
See: dfns.dws/notes.wGraphs.

Auxiliary  function "replaces" is used to update Pocket APL's DAN component file
using the following steps:

  )load tube                    ⍝ start with this workspace.
  gotham←⎕ns''                  ⍝ create namespace for new city.
  ed gotham                     ⍝ create metro map source for new city.
  compile gotham                ⍝ compile graph.
  gotham replaces 'Gotham City' ⍝ install new city in DAN.DCF.
  )save                         ⍝ remember to save changes.
  )load dan                     ⍝ load DAN workspace and
  ...                           ⍝ test changes.
  )load tube                    ⍝ reload tube workspace.
  ed gotham                     ⍝ make changes.
  compile gotham                ⍝ recompile graph.
  gotham replaces 'Gotham City' ⍝ replace city.
  ...                           ⍝ test using DAN workspace and so on ...

To remove a city from DAN's component file:

  replaces 'Gotham City'        ⍝ remove city (no left argument).

#.notes.test is a function that takes test script #.notes.script to exercise the
workspace. To run the test, type:

    notes.test'script'      ⍝ run test script. No news => good news.

Any differences from expected result are displayed in the session.

Thanks to the following people for suggestions and subway source codings:

Dick Bowman
Gianluigi Quario
Klaus Klug Christiansen
Stefano Lanzavecchia

See also: →source← →trip← →compile← →path← →ed←

Back to: contents