GraphStructure
This page is out of date. The edge based graph is no longer being used in the master branch of OTP. Rather, and edge-based search is executed on a directed, vertex-based graph of the kind shown in Figure 1. Turn restrictions are handled by annotating edges to explicitly allow or disallow turns onto other edges. These restrictions are applied during the search.
Street and transport networks are represented in OTP using directed graphs. The purpose of this page is to explain how vertices (aka nodes) and edges are arranged to allow finding optimal paths through a complex transportation system.
Figure 1 shows a small part of an OTP graph for New York, containing both street and public transit information. Here we are using a simplified representation of the street network, where nodes represent intersections and edges represent road segments between intersections. This model has been superseded (see below) but we present it here because the newer model is derived from it. Edges in OTP are directed, so a street segment is usually composed of two edges, one in each direction. Certain modes of travel might be allowed in one direction, but not in the other (e.g. one-way streets, bike lanes).
Each transit stop has at least one node that represents being in or at the stop. There could be multiple nodes for a single stop if it has several platforms. These nodes are linked with low-weight edges to the street network. In fig. 1 the two stations are shown linked to intersections, but if station entrances were too far away from an existing node, the street edge would be split to position the entrances more realistically.
The Board, Alight, Dwell, and Hop edges represent transit trips. Many trips can be grouped together into time-dependent PatternBoard, PatternAlight, PatternDwell, and PatternHop edges if they have the same sequence of stops. These edges' weight functions vary according to the time at which they are traversed. For example, a PatternBoard edge will search for the next departure time for its associated trip pattern and vary its weight accordingly. In fig. 1, two different trip patterns are used to represent two different subway services which happen to pass through the same stops here, but will branch out elsewhere in the city.
In order to allow more complicated behavior, especially turn restrictions, the simple street representation used in fig. 1 has been replaced with the "edge-based" representation shown in fig. 2. The original street network can be seen in grey, with the new edges superimposed. Every edge in the original graph has been replaced with a node, and every pair of edges that share a node in the original graph is represented with an edge. Here, the nodes represent being on a certain street segment, and traversing an edge represents turning onto another nearby street segment. Note that turning restrictions can now be applied to individual turns, and even individual modes of travel. Also note, as shown in fig. 3, that a path can pass through an intersection more than once, and a shortest path can loop back on itself. This is not possible in the simpler street graph. For more information, see: Winter and Grünbacher. Modeling Costs of Turns in Route Planning. Institute for Geoinformation, Technical University Vienna.
In figures 2 and 3, the new nodes are drawn in the center of their corresponding edges for clarity. In OTP, these nodes (StreetVertex objects) represent being at the beginning of a street segment, and a turn edge carries you to the beginning of an adjacent street segment, as shown in figure 4. This simplifies conversion from the original graph and facilitates reuse of street geometry information by edges representing the same segment.