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).

Note that most dodgr algorithms implement parallel computation with the RcppParallel library, and by default use the maximal number of available cores or threads. If you do not wish dodgrto use all available threads, please reduce the number manually by first specifying a value via

RcppParallel::setThreadOptions (numThreads = 1L) # or desired number

What’s so special?

Four aspects. First, while other packages exist for calculating distances on directed graphs, notably igraph, 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 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, access restrictions, and the effects of elevation on both cyclists and pedestrians. See the dedicated vignette on street networks and time-based routing for more detail.

Installation

You can install latest stable version of dodgr from CRAN with:

install.packages ("dodgr") # current CRAN version

Alternatively, current development versions can be installed using any of the following options:

# install.packages("remotes")
remotes::install_git ("https://git.sr.ht/~mpadge/dodgr")
remotes::install_git ("https://codeberg.org/UrbanAnalyst/dodgr")
remotes::install_bitbucket ("UrbanAnalyst/dodgr")
remotes::install_gitlab ("UrbanAnalyst/dodgr")
remotes::install_github ("UrbanAnalyst/dodgr")

Then load with

library (dodgr)
packageVersion ("dodgr")
#> [1] '0.2.21'

Important Note

While dodgr works with any arbitrary networks, it also includes numerous functions explicitly intended to be applied to geodesic coordinates, which are identified whenever input data have columns labelled “longitude” and “latitude”, or similar. Coordinates for such data must be in the EPSG:4326 (WGS84) coordinate system. dodgr treats coordinates as numbers only, and it is up to the user to ensure appropriate transformation to WGS84 coordinates prior to submitting data to dodgr functions.

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 (a primarily pedestrian village in the middle of a large World Heritage zone). These data are in Simple Features (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:

class (hampi)
#> [1] "sf"         "data.frame"
dim (hampi)
#> [1] 236  15
graph <- weight_streetnet (hampi, wt_profile = "foot")
class (graph)
#> [1] "data.frame"      "dodgr_streetnet"
dim (graph)
#> [1] 6813   15

The sf-format network contained 236 LINESTRING objects, with the weight_streetnet() function decomposing these into 6,813 distinct edges, indicating that the sf representation had around 29 edges or segments in each LINESTRING object. The dodgr network then looks like this:

head (graph)

geom_num	edge_id	from_id	from_lon	from_lat	to_id	to_lon	to_lat	d	d_weighted	highway	way_id	component	time	time_weighted
1	1	339318500	76.47491	15.34167	339318502	76.47612	15.34173	130.000241	130.000241	path	28565950	1	93.600174	93.600174
1	2	339318502	76.47612	15.34173	339318500	76.47491	15.34167	130.000241	130.000241	path	28565950	1	93.600174	93.600174
1	3	339318502	76.47612	15.34173	2398958028	76.47621	15.34174	8.890622	8.890622	path	28565950	1	6.401248	6.401248
1	4	2398958028	76.47621	15.34174	339318502	76.47612	15.34173	8.890622	8.890622	path	28565950	1	6.401248	6.401248
1	5	2398958028	76.47621	15.34174	1427116077	76.47628	15.34179	9.307736	9.307736	path	28565950	1	6.701570	6.701570
1	6	1427116077	76.47628	15.34179	2398958028	76.47621	15.34174	9.307736	9.307736	path	28565950	1	6.701570	6.701570

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:

head (graph [graph$highway == "path", ])

geom_num	edge_id	from_id	from_lon	from_lat	to_id	to_lon	to_lat	d	d_weighted	highway	way_id	component	time	time_weighted
1	1	339318500	76.47491	15.34167	339318502	76.47612	15.34173	130.000241	130.000241	path	28565950	1	93.600174	93.600174
1	2	339318502	76.47612	15.34173	339318500	76.47491	15.34167	130.000241	130.000241	path	28565950	1	93.600174	93.600174
1	3	339318502	76.47612	15.34173	2398958028	76.47621	15.34174	8.890622	8.890622	path	28565950	1	6.401248	6.401248
1	4	2398958028	76.47621	15.34174	339318502	76.47612	15.34173	8.890622	8.890622	path	28565950	1	6.401248	6.401248
1	5	2398958028	76.47621	15.34174	1427116077	76.47628	15.34179	9.307736	9.307736	path	28565950	1	6.701570	6.701570
1	6	1427116077	76.47628	15.34179	2398958028	76.47621	15.34174	9.307736	9.307736	path	28565950	1	6.701570	6.701570

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() or, for street networks, times, dodgr_times(), 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.

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:

v <- dodgr_vertices (graph)
head (v)

	id	x	y	component	n
1	339318500	76.47491	15.34167	1	0
2	339318502	76.47612	15.34173	1	1
4	2398958028	76.47621	15.34174	1	2
6	1427116077	76.47628	15.34179	1	3
8	7799710916	76.47634	15.34184	1	4
10	339318503	76.47641	15.34190	1	5

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:

from <- sample (v$id, size = 20)
to <- sample (v$id, size = 50)
d <- dodgr_dists (graph = graph, from = from, to = to)
dim (d)
#> [1] 20 50

Alternatively, the points may be specified as matrices of geographic coordinates:

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:

graph <- graph [graph$component == 1, ]
nrow (graph)

or by explicitly using the match_points_to_verts() function with the option connected = TRUE:

from <- match_points_to_verts (v, cbind (from_x, from_y), connected = TRUE)
to <- match_points_to_verts (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:

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”:

flows <- array (runif (length (from) * length (to)), dim = c (length (from), length (to)))
length (from)
#> [1] 20
length (to)
#> [1] 50
dim (flows)
#> [1] 20 50
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:

head (f)

geom_num	edge_id	from_id	from_lon	from_lat	to_id	to_lon	to_lat	d	d_weighted	highway	way_id	component	time	time_weighted	flow
1	1	339318500	76.47491	15.34167	339318502	76.47612	15.34173	130.000241	130.000241	path	28565950	1	93.600174	93.600174	0.5815996
1	2	339318502	76.47612	15.34173	339318500	76.47491	15.34167	130.000241	130.000241	path	28565950	1	93.600174	93.600174	2.3630118
1	3	339318502	76.47612	15.34173	2398958028	76.47621	15.34174	8.890622	8.890622	path	28565950	1	6.401248	6.401248	0.5815996
1	4	2398958028	76.47621	15.34174	339318502	76.47612	15.34173	8.890622	8.890622	path	28565950	1	6.401248	6.401248	2.3630118
1	5	2398958028	76.47621	15.34174	1427116077	76.47628	15.34179	9.307736	9.307736	path	28565950	1	6.701570	6.701570	0.5815996
1	6	1427116077	76.47628	15.34179	2398958028	76.47621	15.34174	9.307736	9.307736	path	28565950	1	6.701570	6.701570	2.3630118

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:

f <- dodgr_flows_disperse (graph = graph, from = from, dens = runif (length (from)))

Further detail

For more detail, see the main package vignette, and the second vignette on street networks and time-based routing

Contributors

All contributions to this project are gratefully acknowledged using the allcontributors package following the allcontributors specification. Contributions of any kind are welcome!

Code

mpadge	karpfen	Robinlovelace	agila5	JimShady	DavisVaughan
layik	olivroy

Issue Authors

chrjangit	rafapereirabr	chrijo	dataandcrowd	mem48	fzenoni
mdsumner	nacnudus	mkvasnicka	orlando-sabogal	tbuckl	douglascm
darinchristensen	romainFr	dcooley	Hussein-Mahfouz	sigmafelix	polettif
edzer	FlxPo	LeshunXu	deanmarchiori	demcortillas	Urban-JonathanCohen
sriramab	xiaofanliang	grobins	jucardwell	diegoteca	xtimbeau
pasipasi123	jamiedtor	chinhqho	szhorvat	nataliamush	juanfonsecaLS1
luukvdmeer	jonas260492

Issue Contributors

virgesmith

richardellison

coatless

znmeb

yihui

MartinLHazelton