Metro Routes

A metro map as a graph: stations are nodes, and neighbouring stations on a line are connected. With it, the program finds the route with the fewest stops, and where to change lines along it.

A builtin graph

Network<Id, Data, Edge> is a graph collection that comes with the language. Here the ids are station names, and each station's data is the Set of lines that stop there. The edges carry nothing, so Edge is left out - it defaults to Undefined. buildMetro adds each station once, records its lines, and connects neighbours both ways with connectBoth. windows(2) goes through a line's stations in overlapping pairs: Harbor and Market, then Market and Central, and so on.

The graph answers the questions itself. path finds the route with the fewest edges, or undefined when there's none. components splits the graph into the parts that are connected, which shows that the tram is separate from the metro.

Finding changes

A rider changes lines at a station when no single line serves the station before it, the station itself and the one after. changes looks at the route three stations at a time with windows(3), and uses set operations: the lines common to the first two stations, intersection, having nothing in common with the third, isDisjointFrom. linesAt is a lambda stored in a local variable, to avoid repeating the lookup.

Concepts shown

  • The builtin Network: nodes, edges, path and components.
  • Set operations: intersection and isDisjointFrom.
  • Sliding windows over an array with windows.
  • Lambdas stored in variables.