--------------------
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:
Circle
South Kensington
Gloucester Road
High Street Kensington
···
Victoria
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:
District
Ealing Broadway
Ealing Common
Acton Town
Chiswick Park
Turnham Green
District
Richmond
Kew Gardens
Gunnersbury
Turnham Green
District
Turnham Green
Stamford Brook
Ravenscourt Park
Hammersmith
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
-----
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.
F
┌───────────────────────────────────────────────────────────────────────┐
│ 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
-------
Crosses
-------
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
Poplar Docklands Light Railway
Blackwall Docklands Light Railway
Blackwall
----------------
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:
Picadilly
↓ Heathrow 4 // ┌─H123─→┐
↓ Heathrow 1,2,3 // ↑ ├──HX──
↓∊Hatton Cross // └─H4──←─┘
Heathrow 4
suggesting:
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.
-------
Summary
-------
// comment
Line
station
station
...
∊ on handle of [fork].
↓ at start of [one-way section].
+ on [cross].
-------
Example
-------
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.
Key:
⎕ 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.
│ │ │
···───←───∘───←───∘───←───∘───←───···
Fork:
┌───→───∘───→───∘───→───···
│ │ │
↑ ⎕ ⎕ Line A:
│ │ │
···───→───∘───→───∘──┐ ┌←─∘───←───∘───←───···
│ │ │ │
Line A: ⎕ ⎕ └─→──┐
│ │ │ │
···───←───∘───←───∘──←─┘ ∘───→───∘───→───···
│ │ │
↑ ⎕ ⎕ Line A:
│ │ │
└───←───∘───←───∘───←───···
Cross:
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).
-------
Testing
-------
#.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.
---------------
Acknowledgments
---------------
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