# In-Memory Tiles

The `inmemory`

module contains efficient in-memory data structures that implement the *Core* interfaces.

```
libraryDependencies ++= Seq(
"com.here.platform.location" %% "location-inmemory" % "0.21.139"
)
```

```
<dependencies>
<dependency>
<groupId>com.here.platform.location</groupId>
<artifactId>location-inmemory_${scala.compat.version}</artifactId>
<version>0.21.139</version>
</dependency>
</dependencies>
```

```
dependencies {
compile group: 'com.here.platform.location', name: 'location-inmemory_2.11', version:'0.21.139'
}
```

## Graphs and TiledGraph

You can partition very large routing graphs by means of a *partitioning scheme*. A partioning scheme specifies which part of the graph goes to which partition. The routing graph is partitioned according to the heretile partitioning scheme, which is based on the geographical location associated with graph primitives and a bounding box for each partition. Specifically, the 2D space of geocoordinates is partitioned into rectangular tiles, and the graph primitives that are inside the boundaries of the same tile go to the same partition.

A TiledGraph implements the Location Library DirectedGraph abstraction for data in Compressed Sparse Row Format.

In particular, TiledGraph represents a partitioned incidence graph.

An incidence graph is a graph that only supports one operation on a vertex: getting its outgoing edges. To implement this efficiently, you can store the outgoing edges with their start vertex in the same partition. Outgoing edges may end at a vertex that is not in the same partition.

TiledGraph transparently handles the transition between partitions. For example for seamless graph traversal, you can create a TiledGraph out of two GraphTiles as follows:

```
import com.here.platform.location.inmemory.geospatial.TileId
import com.here.platform.location.inmemory.graph._
// Create the graph p3(1) <-- p1(0) --> p2(0).
val graph1 = new GraphTile(TileId(1),
firstEdgeIndices = Array(0, 2),
edges = Array(1, 2),
externalVertexTileIds = Array(2, 3),
externalVertexIndices = Array(0, 1))
val graph2 = new GraphTile(TileId(2),
firstEdgeIndices = Array(0, 0),
edges = Array.empty,
externalVertexTileIds = Array.empty,
externalVertexIndices = Array.empty)
// Only partition 1 and 2 are present.
val graphTiles =
Map(graph1.tileId -> graph1, graph2.tileId -> graph2)
val graph = new TiledGraph(graphTiles.get)
val p1v0 = Vertex(TileId(1), VertexIndex(0))
val edges: Iterable[Edge] = graph.outEdgeIterator(p1v0).toIterable
println(s"$p1v0 has ${edges.size} outgoing edges: ...")
val p2v0 = graph.target(edges.head)
println(s"... one to $p2v0")
val p2v0edges = graph.outEdgeIterator(p2v0)
println("which can be expanded")
```

When exploring a TiledGraph that does not contain the complete graph, you may still find a partition that is missing. For example, while exploring the routing graph for a particular area, you may reach a vertex that lies outside of the area. A plain TiledGraph throws an exception in that case.

```
val p3v1 = graph.target(edges.last)
println(s"... and one to $p3v1")
try {
graph.outEdgeIterator(p3v1)
} catch {
case _: NoSuchElementException =>
println("which cannot be expanded")
println("because its partition is not present")
}
```

In case you just want to filter out these vertices, you can construct the TiledGraph **with** TiledGraph.CutBorders

```
val cutGraph = new TiledGraph(graphTiles.get) with TiledGraph.CutBorders
val cutEdges = cutGraph.outEdgeIterator(p3v1)
println(s"... unless we cut the graph's borders")
assert(cutEdges.isEmpty)
println("in which case the missing vertex will have no outgoing edges")
```

## Vertices

To retrieve any information associated with a graph vertex, you can use Vertex as a key into a PropertyMap.

A vertex is uniquely identified by a graph partition (represented by TileId) and its index (represented by VertexIndex) inside that partition.

## TileResolver

In order to access a tiled map, there needs to be a way to calculate the tile IDs of necessary partitions. There is no way to implement this generically because you cannot know in advance the partitioning scheme or tile level of the map data you are trying to use. Consequently, you should rely on a TileResolver that allows calculating tile IDs for various area queries.

```
import com.here.platform.location.inmemory.geospatial.TileResolver
import com.here.platform.location.integration.herecommons.geospatial.{
HereTileLevel,
HereTileResolver
}
// Construct a resolver for the HEREtile scheme on level 14
val outputLevel = HereTileLevel(14)
val resolver: TileResolver = new HereTileResolver(outputLevel)
```

The following snippets show example queries.

By point search:

Scala`import com.here.platform.location.core.geospatial.GeoCoordinate val point = new GeoCoordinate(latitude = 0.0, longitude = 53.0) val pointTile = resolver.fromCoordinate(point) println(s"The $point is inside the level ${outputLevel.value} tile with id ${pointTile.value}")`

By radius search:

Scala`val radiusInMeters = 1000.0 val radiusTiles = resolver.fromCenterAndRadius(point, radiusInMeters) println(s"The following tiles are within $radiusInMeters meters of $point:") radiusTiles.foreach(println)`

By bounding-box search:

Scala`import com.here.platform.location.core.geospatial.BoundingBox val bb = BoundingBox(northLatitude = 52.53047, southLatitude = 52.51708, westLongitude = 13.39632, eastLongitude = 13.42293) val bbTiles = resolver.fromBoundingBox(bb) println(s"The following tiles are intersecting $bb:") bbTiles.foreach(println)`

## The Compressed Sparse Row Graph Format

The Compressed Sparse Row (CSR) Format is an efficient storage format for matrices and graphs. In the Location Library's partitioned variant, each partition consists of four integer arrays:

**firstEdgeIndices**: The index of the first edge for each internal vertex**edges**: The destination vertex index for each edge**partitionIds**: The partition IDs for all external vertices that are referenced from this partition**vertexIndices**: The vertex indices in their respective partitions for all external vertices

Vertex indices 0 through `firstEdgeIndices.length - 2`

refer to internal vertices (vertices in this partition).

The last entry of `firstEdgeIndices`

is always `edges.length`

.

So each entry in `firstEdgeIndices`

is the index of the edge after the last edge of the previous vertex.

As a consequence, the edges starting at a given internal vertex with index `idx`

are determined by the index range from `firstEdgeIndices(idx)`

(inclusive) to `firstEdgeIndices(idx + 1)`

(exclusive).

Vertex indices `firstEdgeIndices.length - 1`

through `firstEdgeIndices.length + partitionIds.length - 2`

refer to external vertices (vertices outside this partition that are referred to from inside this partition). Therefore, the number of external vertices is `partitionIds.length`

.

For vertex `v`

with index `idx`

, the following is valid:

If

`idx < firstEdgeIndices.length - 1`

,`v`

is in the current graph partition.Otherwise,

`v`

belongs to the partition with id`partitionIds(idx - firstEdgeIndices.length + 1)`

and its index in that partition is `vertexIndices(idx - firstEdgeIndices.length + 1)`

.

### Example

The following image shows partition 1 of a given graph:

CSRG format represents this partition as follows:

You can restore the graph partition by looking at its CSRG representation.

Let `v(i)`

be the vertex with index `i`

, so `v(0)`

is the vertex with index 0, and `v(1)`

that with index 1, and so on.

Find out how many internal vertices this partition defines and which external vertices it references.

`firstEdgeIndices.length - 1`

is 3, thus the vertices`v(0)`

,`v(1)`

and`v(2)`

belong to the current partition.The vertex

`v(3)`

corresponds to the external vertex in partition`partitionIds(0)`

at index`vertexIndices(0)`

, which are partition 24 and index 13.Similarly, the vertex

`v(4)`

is the external vertex in partition`partitionIds(1)`

at index`vertexIndices(1)`

, which are partition 42 and index 9.Reconstruct the graph edges. For every internal vertex, decode its outgoing edges.

The outgoing edges of

`v(0)`

have indices in the range [0, 1) (from`firstEdgeIndices(0)`

inclusive to`firstEdgeIndices(1)`

exclusive). So the vertex has a single outgoing edge with index 0, and the edge's target is the vertex`v(edges(0))`

==`v(2)`

.The outgoing edges of

`v(1)`

have indices in the (empty) range [1, 1) (from`firstEdgeIndices(1)`

inclusive to`firstEdgeIndices(2)`

exclusive). Therefore, the vertex has no outgoing edges.Similarly, the outgoing edges of

`v(2)`

have indices in the range [1, 3), which correspond to target vertices`v(edges(1))`

and`v(edges(2))`

-- the vertices`v(4)`

and`v(3)`

.