forked from UrbanAnalyst/dodgr
-
Notifications
You must be signed in to change notification settings - Fork 1
/
README.Rmd
253 lines (219 loc) · 10.8 KB
/
README.Rmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
---
title: "dodgr, Distances on Directed Graphs in R"
output:
rmarkdown::html_vignette:
self_contained: no
md_document:
variant: markdown_github
---
<!-- README.md is generated from README.Rmd. Please edit that file -->
```{r opts, echo = FALSE}
knitr::opts_chunk$set(
collapse = TRUE,
warning = TRUE,
message = TRUE,
width = 120,
comment = "#>",
fig.retina = 2,
fig.path = "README-"
)
```
[](https://travis-ci.org/ATFutures/dodgr)
[](https://ci.appveyor.com/project/ATFutures/dodgr)
[](https://codecov.io/gh/ATFutures/dodgr)
[](http://www.repostatus.org/#active)
[](https://cran.r-project.org/package=dodgr)
[](https://cran.r-project.org/package=dodgr)
[](https://bestpractices.coreinfrastructure.org/projects/1396)
# dodgr: Distances on Directed Graphs in R
`dodgr` is an R package for efficient calculation of many-to-many pairwise
distances on dual-weighted directed graphs, for aggregation of flows throughout
networks, and for highly realistic routing through street networks (time-based
routing considering incline, turn-angles, surface quality, everything).
## What's so special?
Four aspects. First, while other packages exist for calculating distances on
directed graphs, notably [`igraph`](https://igraph.org/r), even that otherwise
fabulous package does not (readily) permit analysis of *dual-weighted* graphs.
Dual-weighted graphs have two sets of weights for each edge, so routing can be
evaluated with one set of weights, while distances can be calculated with the
other. A canonical example is a street network, where *weighted distances* are
assigned depending on mode of transport (for example, weighted distances for
pedestrians on multi-lane vehicular roads are longer than equivalent distances
along isolated walking paths), yet the desired output remains direct,
unweighted distances. Accurate calculation of distances on street networks
requires a dual-weighted representation. In **R**, `dodgr` is currently the
only package that offers this functionality (without excessive data wrangling).
Second, while [`igraph`](https://igraph.org/r) and almost all other routing
packages are primarily designed for one-to-one routing, `dodgr` is specifically
designed for many-to-many routing, and will generally outperform equivalent
packages in large routing tasks.
Third, `dodgr` goes beyond the functionality of comparable packages through
including routines to aggregate flows throughout a network, through specifying
origins, destinations, and flow densities between each pair of points.
Alternatively, flows can be aggregated according to a network dispersal model
from a set of origin points and associated densities, and a user-specified
dispersal model.
Fourth and finally, `dodgr` implements highly realistic and fully-customisable
profiles for routing through street networks with various modes of transport,
and using either distance- or time-based routing. Routing can include such
factors as waiting times at traffic lights, delays for turning across oncoming
traffic, and the effects of elevation on both cyclists and pedestrians.
## Installation
You can install `dodgr` with:
```{r gh-installation, eval = FALSE}
install.packages("dodgr") # current CRAN version
# install.packages("remotes")
remotes::install_github("ATFutures/dodgr") # Development version
```
Then load with
```{r library}
library (dodgr)
packageVersion ("dodgr")
```
## Usage: Sample Data and `dodgr` networks
To illustrate functionality, the package includes an example data set
containing the Open Street Map network for [Hampi,
India](https://www.openstreetmap.org/#map=15/15.3368/76.4601) (a primarily
pedestrian village in the middle of a large World Heritage zone). These data
are in [Simple Features (`sf`)](https://cran.r-project.org/package=sf) format,
as a collection of `LINESTRING` objects. `dodgr` represents networks as
a simple rectangular graph, with each row representing an edge segment between
two points or vertices. `sf`-format objects can be converted to equivalent
`dodgr` representations with the `weight_streetnet()` function:
```{r hampi}
class (hampi)
dim (hampi)
graph <- weight_streetnet (hampi, wt_profile = "foot")
class (graph)
dim (graph)
```
The `sf`-format network contained `r nrow (hampi)` `LINESTRING` objects, with
the `weight_streetnet()` function decomposing these into `r format (nrow (graph),
big.mark = ",")` distinct edges, indicating that the `sf` representation had
around `r round (nrow (graph) / nrow (hampi))` edges or segments in each
`LINESTRING` object. The `dodgr` network then looks like this:
```{r hampi-net-fakey, eval = FALSE}
head (graph)
```
```{r hampi-net, echo = FALSE}
knitr::kable (head (graph))
```
The `geom_num` column maps directly onto the sequence of `LINESTRING` objects
within the `sf`-formatted data. The `highway` column is taken directly from
Open Street Map, and denotes the kind of "highway" represented by each edge. The
`component` column is an integer value describing which of the connected
components of the network each edge belongs to (with `1` always being the
largest component; `2` the second largest; and so on).
Note that the `d_weighted` values are often greater than the geometric
distances, `d`. In the example shown, `service` highways are not ideal for
pedestrians, and so weighted distances are slightly greater than actual
distances. Compare this with:
```{r hampi-net-faken2, eval = FALSE}
head (graph [graph$highway == "path", ])
```
```{r hampi-net2, echo = FALSE}
knitr::kable (head (graph [graph$highway == "path", ]))
```
A `"path"` offers ideal walking conditions, and so weighted distances are equal
to actual distances.
## Usage: Distances and Times
The many-to-many nature of `dodgr` means that the function to calculate
distances,
[`dodgr_distances()`](https://atfutures.github.io/dodgr/reference/dodgr_distances.html)
or, for street networks, times,
[`dodgr_times()`](https://atfutures.github.io/dodgr/reference/dodgr_times.html),
accepts two vectors or matrices of routing
points as inputs (describing origins and destinations), and returns
a corresponding matrix of pairwise distances. If an input graph has columns for
both distances and weighted distances, and/or times and weighted times, the
weighted versions are used to determine the effectively shortest or fastest
routes through a network, while actual distances or times are summed along the
routes to calculate final values. It is of course also possible to calculate
distances along fastest routes, times along shortest routes, or any combination
thereof, as detailed in the package vignette on [street networks and time-based
routing](https://atfutures.github.io/dodgr/articles/times.html).
Routing points can, for example, be randomly selected from the vertices of a
graph. The vertices can in turn be extracted with the `dodgr_vertices()`
function:
```{r verts-fakey, eval = FALSE}
v <- dodgr_vertices (graph)
head (v)
```
```{r verts, echo = FALSE}
v <- dodgr_vertices (graph)
knitr::kable (head (v))
```
For OSM data extracted with the `osmdata` package (or, equivalently, via the
`dodgr::dodgr_streetnet()` function), each object (vertices, ways, and
high-level relations between these objects) is assigned a unique identifying
number. These are retained both in `osmdata` and `dodgr`, as the `way_id` column
in the above `graph`, and as the `id` column in the vertices. Random vertices
may be generated in this case through selecting `id` values:
```{r random-verts}
from <- sample (v$id, size = 20)
to <- sample (v$id, size = 50)
d <- dodgr_dists (graph = graph, from = from, to = to)
dim (d)
```
Alternatively, the points may be specified as matrices of geographic
coordinates:
```{r}
from_x <- min (graph$from_lon) + runif (20) * diff (range (graph$from_lon))
from_y <- min (graph$from_lat) + runif (20) * diff (range (graph$from_lat))
to_x <- min (graph$from_lon) + runif (50) * diff (range (graph$from_lon))
to_y <- min (graph$from_lat) + runif (50) * diff (range (graph$from_lat))
d <- dodgr_dists (graph = graph, from = cbind (from_x, from_y), to = cbind (to_x, to_y))
```
In this case, the random points will be mapped on to the nearest points on the
street network. This may, of course, map some points onto minor, disconnected
components of the graph. This can be controlled either by reducing the graph to
it's largest connected component only:
```{r large-comp, eval = FALSE}
graph <- graph [graph$component == 1, ]
nrow (graph)
```
or by explicitly using the `match_points_to_graph()` function with the option
`connected = TRUE`:
```{r}
from <- match_points_to_graph (v, cbind (from_x, from_y), connected = TRUE)
to <- match_points_to_graph (v, cbind (to_x, to_y), connected = TRUE)
```
This function returns an index into the result of `dodgr_vertices`, and so
points to use for routing must then be extracted as follows:
```{r}
from <- v$id [from] # or from <- v [from, c ("x", "y")]
to <- v$id [to]
d <- dodgr_dists (graph = graph, from = from, to = to)
```
## Usage: Flow Aggregation
Flow aggregation refers to the procedure of routing along multiple ways
according to specified densities of flow between defined origin and destination
points, and aggregating flows along each edge of the network. The procedure is
functionally similar to the above procedure for distances, with the addition of
a matrix specifying pairwise flow densities between the input set of origin
(`from`) and destination (`to`) points. The following example illustrates use
with a random "flow matrix":
```{r flows}
flows <- array (runif (length (from) * length (to)), dim = c (length (from), length (to)))
length (from); length (to); dim (flows)
f <- dodgr_flows_aggregate (graph = graph, from = from, to = to, flows = flows)
```
The result is simply the input `graph` with an additional column quantifying
the aggregate flows along each edge:
```{r flows-out-fakey, eval = FALSE}
head (f)
```
```{r flows-out, echo = FALSE}
knitr::kable (head (f))
```
An additional flow aggregation function can be applied in cases where only
densities at origin points are known, and movement throughout a graph is
dispersive:
```{r, eval = FALSE}
f <- dodgr_flows_disperse (graph = graph, from = from, dens = runif (length (from)))
```
## Further detail
For more detail, see the [main package
vignette](https://atfutures.github.io/dodgr/articles/dodgr.html), and the second
vignette on [street networks and time-based
routing](https://atfutures.github.io/dodgr/articles/times.html)