EdgeStore (r5 4.6.1-SNAPSHOT API)

java.lang.Object
- com.conveyal.r5.streets.EdgeStore

All Implemented Interfaces:

Serializable
```
public class EdgeStore
extends Object
implements Serializable
```
This stores all the characteristics of the edges in the street graph layer of the transport network. The naive way to do this is making one object per edge, and storing all those edges in one big list or in outgoing and incoming edge lists in each vertex. However, representing the street graph as an object graph has some disadvantages, including devoting a large amount of space to pointers, making serialization more complex, and possible memory locality effects on speed. Originally we considered using a library that would simulate compound value types (C structs). A column store with parallel arrays is better than a struct simulation because: 1. it is less fancy, 2. it is auto-resizing (not fixed size), 3. I've tried both and they're the same speed. Edges come in pairs that have the same origin and destination vertices and the same geometries, but reversed. Therefore many of the arrays are only half as big as the number of edges. All even numbered edges are forward, all odd numbered edges are reversed. Typically, somewhat more than half of street segment edges have intermediate points (ie. their geometry contains points other than the two endpoints endpoints). Therefore it's more efficient to add a complete dense column for references to intermediate point arrays, instead of using a sparse HashMap to store values only for those edges that have intermediate points. For geometry storage I tried several methods. Full Netherlands load in 4GB of heap: Build time is around 8 minutes. 2.5-3GB was actually in use. List of int arrays: 246MB serialized, 5.2 sec write, 6.3 sec read. List of int arrays, full lists (not only intermediates): 261MB, 6.1 sec write, 6.2 sec read. Indexes into single contiguous int array: 259MB, 5 sec write, 7.5 sec read. We are using the first option as it is both readable and efficient.

See Also:

Serialized Form

Nested Class Summary

Nested Classes
Modifier and Type	Class and Description
`static class`	`EdgeStore.DefaultTravelTimeCalculator`
`class`	`EdgeStore.Edge` Inner class that serves as a cursor: points to a single edge in this store, and can be moved to other indexes.
`static class`	`EdgeStore.EdgeFlag` Edge flags are various boolean values (requiring a single bit of information) that can be attached to each edge in the street graph.
`static interface`	`EdgeStore.PointConsumer` A functional interface that consumes the points in a street geometry one by one.
`static interface`	`EdgeStore.SegmentConsumer` A functional interface that consumes segments in a street geometry one by one.

Field Summary

Fields
Modifier and Type	Field and Description
`int`	`firstModifiableEdge` When applying scenarios, we don't duplicate the entire set of edges and vertices.
`gnu.trove.list.TIntList`	`flags` Boolean flags for every edge.
`gnu.trove.list.TIntList`	`fromVertices` The index of the origin vertex of each edge pair in the forward direction.
`List<int[]>`	`geometries` Geometries.
`gnu.trove.list.TByteList`	`inAngles` The compass angle at the start of the edge geometry (binary radians clockwise from North).
`StreetLayer`	`layer` The street layer of a transport network that the edges in this edgestore make up.
`gnu.trove.list.TIntList`	`lengths_mm` Length of the edge along its geometry (millimeters).
`gnu.trove.list.TLongList`	`osmids` OSM ids of edges.
`gnu.trove.list.TByteList`	`outAngles` The compass angle at the end of the edge geometry (binary radians clockwise from North).
`static EnumSet<EdgeStore.EdgeFlag>`	`PERMISSION_FLAGS` As a convenience, the set of all edge flags that control which modes can traverse the edge
`gnu.trove.list.TShortList`	`speeds` One speed for each edge.
`static double`	`STAIR_RELUCTANCE_FACTOR`
`gnu.trove.set.TIntSet`	`temporarilyDeletedEdges` When applying a scenario, we can't touch the baseline graph which is shared between all threads.
`gnu.trove.list.TIntList`	`toVertices` The index of the destination vertex of each edge pair in the forward direction.
`TIntIntMultimap`	`turnRestrictions` Turn restrictions for turning _out of_ each edge
`TIntIntMultimap`	`turnRestrictionsReverse` Turn restrictions for turning _into_ each edge
`VertexStore`	`vertexStore`
`static double`	`WALK_RELUCTANCE_FACTOR`

Constructor Summary

Constructors
Constructor and Description

EdgeStore(VertexStore vertexStore, StreetLayer layer, int initialSize)

Constructors
Constructor and Description
`EdgeStore(VertexStore vertexStore, StreetLayer layer, int initialSize)`

Method Summary

All Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`EdgeStore.Edge`	`addStreetPair(int beginVertexIndex, int endVertexIndex, int edgeLengthMillimeters, long osmID)` This creates the bare topological edge pair with a length.
`void`	`dump()`
`EdgeStore`	`extendOnlyCopy(StreetLayer copiedStreetLayer)` Returns a semi-deep copy of this EdgeStore for use when applying Scenarios.
`void`	`forEachTemporarilyAddedEdge(IntConsumer consumer)` If this EdgeStore has has a Scenario applied, it may contain edges that are not in the baseline network.
`void`	`forEachTemporarilyAddedOrDeletedEdge(IntConsumer consumer)` Call the supplied int consumer function with every temporarily added edge in this EdgeStore, then on every temporarily deleted edge.
`EdgeStore.Edge`	`getCursor()`
`EdgeStore.Edge`	`getCursor(int pos)`
`boolean`	`isExtendOnlyCopy()` This method will tell you whether a scenario has been applied to this EdgeStore, i.e.
`int`	`nEdgePairs()`
`int`	`nEdges()`

Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Field Detail
  - STAIR_RELUCTANCE_FACTOR
```
public static final double STAIR_RELUCTANCE_FACTOR
```
    See Also:
    
    Constant Field Values
  - WALK_RELUCTANCE_FACTOR
```
public static final double WALK_RELUCTANCE_FACTOR
```
    See Also:
    
    Constant Field Values
  - vertexStore
```
public VertexStore vertexStore
```
  - flags
```
public gnu.trove.list.TIntList flags
```
    Boolean flags for every edge. Separate entries for forward and backward edges.
  - speeds
```
public gnu.trove.list.TShortList speeds
```
    One speed for each edge. Separate entries for forward and backward edges. rounded (m/s * 100) (2 decimal places) Saved speed is mostly the same as speed saved as m/s * 1000 it differs in second decimal place and is 0.024% smaller This way of saving speeds is 3.5% smaller then previous (saving 7 decimal places)
  - fromVertices
```
public gnu.trove.list.TIntList fromVertices
```
    The index of the origin vertex of each edge pair in the forward direction. One entry for each edge pair.
  - toVertices
```
public gnu.trove.list.TIntList toVertices
```
    The index of the destination vertex of each edge pair in the forward direction. One entry for each edge pair.
  - lengths_mm
```
public gnu.trove.list.TIntList lengths_mm
```
    Length of the edge along its geometry (millimeters). One entry for each edge pair.
  - osmids
```
public gnu.trove.list.TLongList osmids
```
    OSM ids of edges. One entry for each edge pair
  - geometries
```
public List<int[]> geometries
```
    Geometries. One entry for each edge pair. These are packed lists of lat, lon, lat, lon... as fixed-point integers, and don't include the endpoints (i.e. don't include the intersection vertices, only intermediate points).
  - inAngles
```
public gnu.trove.list.TByteList inAngles
```
    The compass angle at the start of the edge geometry (binary radians clockwise from North). Internal representation is -180 to +179 integer degrees mapped to -128 to +127 (brads) One entry for each edge pair.
  - outAngles
```
public gnu.trove.list.TByteList outAngles
```
    The compass angle at the end of the edge geometry (binary radians clockwise from North). Internal representation is -180 to +179 integer degrees mapped to -128 to +127 (brads) One entry for each edge pair.
  - firstModifiableEdge
```
public int firstModifiableEdge
```
    When applying scenarios, we don't duplicate the entire set of edges and vertices. We extend them, treating the baseline graph as immutable. We have to be careful not to change or delete any elements of that baseline graph which is shared between all threads. All edges at or above the index firstModifiableEdge can be modified, all lower indexes should be treated as immutable. All edges from firstModifiableEdge up to nEdges() are temporary and are in a separate spatial index. This field also serves as an indication that a scenario is being applied and this EdgeStore is a protective copy, whenever firstModifiableEdge > 0.
  - temporarilyDeletedEdges
```
public gnu.trove.set.TIntSet temporarilyDeletedEdges
```
    When applying a scenario, we can't touch the baseline graph which is shared between all threads. Whenever we must delete one of these immutable edges (e.g. when splitting a road to connect a new stop) we instead record its index in temporarilyDeletedEdges, meaning it should be ignored as if it did not exist in this thread. TODO: ignore these edges when routing, not only during spatial index queries.
  - turnRestrictions
```
public TIntIntMultimap turnRestrictions
```
    Turn restrictions for turning _out of_ each edge
  - turnRestrictionsReverse
```
public TIntIntMultimap turnRestrictionsReverse
```
    Turn restrictions for turning _into_ each edge
  - layer
```
public StreetLayer layer
```
    The street layer of a transport network that the edges in this edgestore make up.
  - PERMISSION_FLAGS
```
public static final transient EnumSet<EdgeStore.EdgeFlag> PERMISSION_FLAGS
```
    As a convenience, the set of all edge flags that control which modes can traverse the edge
- Constructor Detail
  - EdgeStore
```
public EdgeStore(VertexStore vertexStore,
                 StreetLayer layer,
                 int initialSize)
```
- Method Detail
  - isExtendOnlyCopy
```
public boolean isExtendOnlyCopy()
```
    This method will tell you whether a scenario has been applied to this EdgeStore, i.e. whether its lists have been extended. There's one case where this method will fail: using Scenarios to create street networks from a blank slate, where there are no edges before the scenario is applied.
    
    Returns:
    
    true if this EdgeStore has already been extended, and can therefore be modified without affecting the baseline graph shared between all threads.
  - addStreetPair
```
public EdgeStore.Edge addStreetPair(int beginVertexIndex,
                                    int endVertexIndex,
                                    int edgeLengthMillimeters,
                                    long osmID)
```
    This creates the bare topological edge pair with a length. Flags, detailed geometry, etc. must be set subsequently using an edge cursor. This avoids having a tangle of different edge creator functions for different circumstances.
    
    Returns:
    
    a cursor pointing to the forward edge in the pair, which always has an even index.
  - getCursor
```
public EdgeStore.Edge getCursor()
```
    Returns:
    
    an Edge object that can be moved around in the EdgeStore to get a view of any edge in the graph. This object is not pointing at any edge upon creation, so you'll need to call seek() on it to select an edge.
  - getCursor
```
public EdgeStore.Edge getCursor(int pos)
```
    Returns:
    
    an Edge object that can be moved around in the EdgeStore to get a view of any edge in the graph.
  - dump
```
public void dump()
```
  - nEdges
```
public int nEdges()
```
    Returns:
    
    the total number of individual directed edges in the graph, including temporary ones from Scenarios. Forward and backward edges in pairs are counted separately.
  - nEdgePairs
```
public int nEdgePairs()
```
    Returns:
    
    the number of forward+backward edge pairs in the graph, including temporary ones from applied Scenarios. This should always be always nEdges/2.
  - extendOnlyCopy
```
public EdgeStore extendOnlyCopy(StreetLayer copiedStreetLayer)
```
    Returns a semi-deep copy of this EdgeStore for use when applying Scenarios. Mutable objects and collections will be cloned, but their contents will not. The lists containing the edge characteristics will be copied in such a way that all threads applying Scenarios will share the same baseline data, and only extend those lists. We don't use clone() and make sure every field copy is explicit below, avoiding any unintentional shallow-copying of collections or referenced data structures.
    
    Parameters:
    
    copiedStreetLayer - the copy of the street layer that this edgeStore will reference.
  - forEachTemporarilyAddedEdge
```
public void forEachTemporarilyAddedEdge(IntConsumer consumer)
```
    If this EdgeStore has has a Scenario applied, it may contain edges that are not in the baseline network. The edges added temporarily by a Scenario should always be the numbers from firstModifiableEdge to nEdges. Call the supplied int consumer function with every temporary edge in this EdgeStore.
  - forEachTemporarilyAddedOrDeletedEdge
```
public void forEachTemporarilyAddedOrDeletedEdge(IntConsumer consumer)
```
    Call the supplied int consumer function with every temporarily added edge in this EdgeStore, then on every temporarily deleted edge.

Class EdgeStore

Nested Class Summary

Field Summary

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Field Detail

STAIR_RELUCTANCE_FACTOR

WALK_RELUCTANCE_FACTOR

vertexStore

flags

speeds

fromVertices

toVertices

lengths_mm

osmids

geometries

inAngles

outAngles

firstModifiableEdge

temporarilyDeletedEdges

turnRestrictions

turnRestrictionsReverse

layer

PERMISSION_FLAGS

Constructor Detail

EdgeStore

Method Detail

isExtendOnlyCopy

addStreetPair

getCursor

getCursor

dump

nEdges

nEdgePairs

extendOnlyCopy

forEachTemporarilyAddedEdge

forEachTemporarilyAddedOrDeletedEdge