notes/tube.txt

--------------------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←