route ← subway #.trip (fm via ··· to)       ⍝ Trip from/to ⍵ in network space ⍺.

[subway]  is  a  namespace containing character array: [source], a definition of
the subway network. Character vectors [fm], [via] ··· [to] are the start and end
points  of  the  various "legs" of the trip. Resulting character matrix [route],
shows  a  shortest route between [fm] and [to]. There may be other equally short
routes but the graph searching code guarantees that none is shorter.

[trip]  examines  its  [subway]  namespace  left  argument  for  the presence of
[subway.graph] and compiles one from [subway.source], if it is missing.

Technical details:

[trip] uses auxiliary functions [zip] and [cat]. See: →zip_cat← for details.

[trip]  checks  that the namespace supplied as left argument contains a compiled
[graph] array. If not, it calls the compiler to build one and tries again.

    0=⍺.⎕NC'graph':⍺{                   ⍝ source not compiled for this space.
        ⎕←'compiling graph ...'         ⍝ explain slight delay.
        (compile ⍺)trip ⍵               ⍝ try again with compiled graph.
    }⍵

Notice that, as the helpful message 'compiling graph ...' is on a line, separate
from  the recursive call to [trip], the body of the guard is enclosed in braces.
This means that the recursive reference to function trip must either be explicit
as above, or an implicit reference (∇) must be passed as operand to an operator,
as below:

    0=⍺.⎕NC'graph':⍺ ∇{                 ⍝ source not compiled for this space.
        ⎕←'compiling graph ...'         ⍝ explain slight delay.
        (compile ⍺)⍺⍺ ⍵                 ⍝ try again with compiled graph.
    }⍵

Access  to the subway network is via station entrances. Station labels are dist-
inguished in the ⍺.labels vector, having a depth of 1.

    access←⍺.((1=≡¨labels)/labels)      ⍝ access via station entrances.

A  simple-minded  text-matching  function  locates given names within the access
vector.

    legs←{                              ⍝ start and end station indices.
        hits←∨/⍵⍷↑access                ⍝ stations containing supplied string.
        best←1+⊃⍋↑⍴¨hits/access         ⍝ best (tightest) fit.
        best⊃0,hits/⍳⍴hits              ⍝ index of chosen station.
    }¨⍵                                 ⍝ for each leg of the journey.

The  function  will  match 'Islington' with 'Highbury & Islington' and 'Burrona'
with  'Cascina Burrona'.  It  returns the index of the matching station with the
shortest  name, so that it is always possible to add more characters to disting-
uish,  for example: 'Ruislip Manor' from 'Ruislip'. If any of the names can't be
found, [trip] retires with a helpful error message.

    0∊legs:'Can''t find: ',↑{           ⍝ misspelled station name:
        ⍺,' or ',⍵                      ⍝ (one or more stations)
    }/(0=legs)/⍵                        ⍝ give up :-(

Otherwise, the graph is searched for the shortest path for each leg of the trip.

    find←⍺.graph{⍺⍺ path ⍺ ⍵}           ⍝ find one leg of the route.
    route←↑{⍺,1↓⍵}/2 find/legs          ⍝ suggested route via all points.

Notice  the  pairwise  reduction  (2 find/legs). A trip from A to D via B and C,
would  involve  finding trips: A→B, B→C, C→D. The final route avoids duplication
of  stops  on  intermediate legs of the journey: ↑{⍺,1↓⍵}/. (It happens that the
Paris Metro boasts stations containing all of the uppercase letters. For a truly
epic journey, try (paris trip ⎕A). London does nearly as well with: (london trip
¯3↓⎕a)).

Station and stop labels for the trip are extracted from the labels vector.

          labels←⍺.labels[route]        ⍝ labels for all legs of route.

Station  labels  have  depth-1 and stop labels, which contain station, line and
tabbing information, have depth 2.

          disp labels
    ┌→───┬───────────────────┬────────────────────┬─────────────────────┬──────┬──────────────────────┬─────────────────────┬─────┐
    │    │┌→───┬────┬─┬─────┐│┌→───┬─────┬─┬─────┐│┌→───┬──────┬─┬─────┐│      │┌→───┬──────┬─┬──────┐│┌→───┬─────┬─┬──────┐│     │
    │Pear││    │Pear│ │Fruit│││    │Grape│ │Fruit│││    │Tomato│ │Fruit││Tomato││    │Tomato│ │Veggie│││    │Onion│ │Veggie││Onion│
    │    │└───→┴───→┴→┴────→┘│└───→┴────→┴→┴────→┘│└───→┴─────→┴→┴────→┘│      │└───→┴─────→┴→┴─────→┘│└───→┴────→┴→┴─────→┘│     │
    └───→┴──────────────────→┴───────────────────→┴────────────────────→┴─────→┴─────────────────────→┴────────────────────→┴────→┘

The  remainder  of  the code is concerned only with aligning fields in the final
result,  where  alighting stations are exdented and intermediate stops, indented
with columns aligned.

    Pear
        Pear   Fruit
        Grape  Fruit
        Tomato Fruit
    Tomato
        Tomato Veggie
        Onion  Veggie
    Onion

Station and stop labels are distinguished by their depth:

          masks←1 2=⊂≡¨labels           ⍝ masks of stations and stops.
          stats stops←masks/¨⊂labels    ⍝ station and stop labels.

          disp stats
    ┌→───┬──────┬─────┐
    │Pear│Tomato│Onion│
    └───→┴─────→┴────→┘

          disp stops
    ┌→──────────────────┬────────────────────┬─────────────────────┬──────────────────────┬─────────────────────┐
    │┌→───┬────┬─┬─────┐│┌→───┬─────┬─┬─────┐│┌→───┬──────┬─┬─────┐│┌→───┬──────┬─┬──────┐│┌→───┬─────┬─┬──────┐│
    ││    │Pear│ │Fruit│││    │Grape│ │Fruit│││    │Tomato│ │Fruit│││    │Tomato│ │Veggie│││    │Onion│ │Veggie││
    │└───→┴───→┴→┴────→┘│└───→┴────→┴→┴────→┘│└───→┴─────→┴→┴────→┘│└───→┴─────→┴→┴─────→┘│└───→┴────→┴→┴─────→┘│
    └──────────────────→┴───────────────────→┴────────────────────→┴─────────────────────→┴────────────────────→┘

Local [zip] and [cat] functions are defined: See →zip_cat←

          zip←{↓⍉↑⍵}                    ⍝ transpose vector-of-vectors.
          cat←{↑,/⍵}                    ⍝ concatenate   ..      ..

[pad] stretches each item in a vector-of-vectors to the same length.

          pad←{↓↑⍵}                     ⍝ pad vectors with blanks.

Stop labels are aligned by stretching the station names:

          slabs←cat¨zip pad¨zip stops   ⍝ aligned stop labels.

          disp slabs
    ┌→───────────────────┬────────────────────┬────────────────────┬─────────────────┬─────────────────┐
    │    Pear   Fruit    │    Grape  Fruit    │    Tomato Fruit    │    Tomato Veggie│    Onion  Veggie│
    └───────────────────→┴───────────────────→┴───────────────────→┴────────────────→┴────────────────→┘

Finally,  the  station and aligned stop labels are re-merged and mixed to return
a character matrix result.

          ↑(stats,slabs)[⍋⍋2⊃masks]     ⍝ merged stations and stops.

Examples:

      notes trip 'Pear' 'Onion'         ⍝ simple trip.
compiling graph ...
Pear
    Pear   Fruit
    Grape  Fruit
    Tomato Fruit
Tomato
    Tomato Veggie
    Onion  Veggie
Onion

      notes trip'Apple' 'Banana' 'Cabbage'      ⍝ multi-leg trip.
Apple
    Apple   Fruit
    Tomato  Fruit
Tomato
    Tomato  Fruit
    Banana  Fruit
Banana
    Banana  Fruit
    Tomato  Fruit
Tomato
    Tomato  Veggie
    Lettuce Veggie
    Onion   Veggie
    Cabbage Veggie
Cabbage

See also: →compile← →path← →ed← →zip_cat←

Back to: contents