Rivermede Transit simulator

What it does

The city of Rivermede has 12 stops joined by 6 train routes and 12 bus routes, each with a ride time in minutes. The Airport and East Bridge have trains only.

From a menu you can list the routes, plan one journey from any stop to any other at a time of day, or run a day of passengers: 24 built-in ones travelling at 07:00, 13:00, 18:00 and 22:00, or up to 30 of your own. For each journey it shows the fastest way and, when it is different, the way with the fewest rides, plus the work each search did.

How it works

Stops are the vertices of a graph and routes are weighted, two-way edges, stored as an adjacency list. Breadth-first search finds the journey with the fewest rides. Depth-first search with backtracking tries every journey and keeps the fastest.

To compare them fairly, both count work the same way: one step is one stop visited or one route looked at. Each search is also timed in microseconds, though only the step counts are the same on every machine.

What the numbers showed

BFS costs the same every time: 12 stops plus 36 route checks, 48 steps, which is V + E. DFS costs about ten times more, 465.2 steps per search on average, because it tries 26.8 journeys per passenger.

The extra work buys accuracy. Over the demo day the fastest ways average 16.3 minutes and the fewest-rides ways 16.5 minutes; the fewest-rides way is slower for 4 of the 24 passengers. From Greenwood to Tech Park at 07:00, for example, the fastest way takes 24 minutes in 3 rides and the fewest-rides way 25 minutes in 2.

Testing

make test builds the program, feeds scripted answers to the menu and checks the lines that never change: the route lists, the example journeys and the step totals of the demo day. Timings are not checked, because they depend on the machine.