# 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

digit node link
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

highway factor
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 