building a graph
We can download the street network from openstreetmap and the information are pretty detailed

graph_detail
detail of a graph

We see a lot of different street types, depending on the mean of transportation we need to run some operation on the graph and reduce the number of edges keeping the correct distances.

download the graph (berlin: 162k edges, 147k nodes) (643k segments, 526k nodes)
select the routable street classes (32k, 30k)
simplify the graph (24k, 23k)
take the largest connected subgraph (17k, 11k)
project the graph
weight the graph
depending on the mean of transportation we select only particular street classes

graph by transportation
different kind of graphs depending on the mean of transportation

We build a graph from the geo dataframe

graph by type
detail of a graph

We label the nodes with geohash and depending on the digit used we have different number of nodes and connectivity

9
10k
22k
10
24k
29k
13
35k
32k

With low digit we complete distort the geometry, with high number of digits we lose connectivity

graph_digit
disconnected graph

We realize that some parts are disconnected and therefore we take the largest connected graph

graph_detail
disconnected graph

We weight taking in consideration speed, street class, and length. We apply a factor for each street type

motorway
3
primary
2
secondary
2
tertiary
1.5
residential
0.5

We can than weight a graph with this simple formula:

$$ \frac{speed * type}{length} $$

and obtain a weighted graph

graph_weight
different weighting per street

calculating distance matrix
We selected the closest node per each spot

graph_nearest
closest node per spot (in red)

The first iterations show not logical routes which is mainly due to the direct nature of the graph

graph_directed
shortest path between two spots in a directed graph

A good directed graph is a lot of work and we by now use a undirected graph for reasonable routes

graph_nearest
shortest path between two spots in a directed graph

graph_markov
changes in the Markov graph moving to weights

We compare different graphs

aymmetry_matrix
asymmetry matrix

aymmetry_distribution
asymmetry distribution