Overbranching Hunting

The intent of this page is to illustrate how to use the OTP visualizer to investigate scenarios that give rise to an inefficient amount of branching during the execution of the route planning algorithm.

First, generate a graph of about medium size. Portland Oregon including Trimet's GTFS is about the right size.

Next, start up the visualizer using a debugger. Eclipse's debugger works great.

The basic layout of the visualizer is a little messy. You should see three tabs at the top, a pane on the right, several panes on the left, and a map in the middle.

Zoom in with your mouse scrollwheel, then left click a part of the map. All nearby nodes will show up in the "Vertices" pane on the left.

Click on one with a node name starting with "osm:node:", and then click the "set source" button at the top left of the visualizer. Click on another part of the map, and select a different node from the "Vertices" pane, and then click "set sink". Finally, click the button labeled "path search".

After a short animation, you should see something similar to this.

There's a lot going on here, so let's simplify the map a little. Click on the tab at the top labeled "Prefs". Unselect the checkboxes labeled "show transit", "show highlighted", and "show multistate vertices".

Click on the Main tab to go back to the map. Then maybe zoom in a little. It should look like this.

This is still pretty cluttered, but it's worth explaining what's going on. This is a visual depiction of the shortest path tree, where the width of each branch shows the total sum of the weight of all states up-branch. Because a vertex can have multiple states, several branches can overlap on a single point on the map. Each branch is colored according to the "height" of the tree branch. The algorithm is sort of complicated but the idea is to give a quick visual indication of where different fanning SPT regions overlie the same area, and it didn't really work out super great.