Repository files navigation

dodgr is an R package for efficient calculation of many-to-manypairwise distances on dual-weighted directed graphs, for aggregation offlows throughout networks, and for highly realistic routing throughstreet networks (time-based routing considering incline, turn-angles,surface quality, everything).

Note that mostdodgr algorithms implement parallel computation withtheRcppParallel library,and by default use the maximal number of available cores or threads. Ifyou do not wishdodgrto use all available threads, please reduce thenumber manually by first specifying a value via

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

Four aspects. First, while other packages exist for calculatingdistances on directed graphs, notablyigraph,even that otherwise fabulous package does not (readily) permit analysisofdual-weighted graphs. Dual-weighted graphs have two sets of weightsfor each edge, so routing can be evaluated with one set of weights,while distances can be calculated with the other. A canonical example isa street network, whereweighted distances are assigned depending onmode of transport (for example, weighted distances for pedestrians onmulti-lane vehicular roads are longer than equivalent distances alongisolated walking paths), yet the desired output remains direct,unweighted distances. Accurate calculation of distances on streetnetworks requires a dual-weighted representation. InR,dodgr iscurrently the only package that offers this functionality (withoutexcessive data wrangling).

Second, whileigraph and almost all otherrouting packages are primarily designed for one-to-one routing,dodgris specifically designed for many-to-many routing, and will generallyoutperform equivalent packages in large routing tasks.

Third,dodgr goes beyond the functionality of comparable packagesthrough including routines to aggregate flows throughout a network,through specifying origins, destinations, and flow densities betweeneach pair of points. Alternatively, flows can be aggregated according toa network dispersal model from a set of origin points and associateddensities, and a user-specified dispersal model.

Fourth and finally,dodgr implements highly realistic andfully-customisable profiles for routing through street networks withvarious modes of transport, and using either distance- or time-basedrouting. Routing can include such factors as waiting times at trafficlights, delays for turning across oncoming traffic, access restrictions,and the effects of elevation on both cyclists and pedestrians. See thededicated vignette onstreet networks and time-basedrouting formore detail.

You can install latest stable version ofdodgr from CRAN with:

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

Alternatively, current development versions can be installed using anyof 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.4.2'

Whiledodgr works with any arbitrary networks, it also includesnumerous functions explicitly intended to be applied to geodesiccoordinates, which are identified whenever input data have columnslabelled “longitude” and “latitude”, or similar. Coordinates for suchdata must be in the EPSG:4326 (WGS84) coordinate system.dodgr treatscoordinates as numbers only, and it is up to the user to ensureappropriate transformation to WGS84 coordinates prior to submitting datatododgr functions.

To illustrate functionality, the package includes an example data setcontaining the Open Street Map network forHampi,India (aprimarily pedestrian village in the middle of a large World Heritagezone). These data are inSimple Features(sf) format, as a collectionofLINESTRING objects.dodgr represents networks as a simplerectangular graph, with each row representing an edge segment betweentwo points or vertices.sf-format objects can be converted toequivalentdodgr representations with theweight_streetnet()function:

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

Thesf-format network contained 236LINESTRING objects, with theweight_streetnet() function decomposing these into 6,813 distinctedges, indicating that thesf representation had around 29 edges orsegments in eachLINESTRING object. Thedodgr network then lookslike this:

head (graph)

Thegeom_num column maps directly onto the sequence ofLINESTRINGobjects within thesf-formatted data. Thehighway column is takendirectly from Open Street Map, and denotes the kind of “highway”represented by each edge. Thecomponent column is an integer valuedescribing which of the connected components of the network each edgebelongs to (with1 always being the largest component;2 the secondlargest; and so on).

Note that thed_weighted values are often greater than the geometricdistances,d. In the example shown,service highways are not idealfor pedestrians, and so weighted distances are slightly greater thanactual distances. Compare this with:

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

A"path" offers ideal walking conditions, and so weighted distancesare equal to actual distances.

The many-to-many nature ofdodgr means that the function to calculatedistances,dodgr_distances()or, for street networks, times,dodgr_times(),accepts two vectors or matrices of routing points as inputs (describingorigins and destinations), and returns a corresponding matrix ofpairwise distances. If an input graph has columns for both distances andweighted distances, and/or times and weighted times, the weightedversions are used to determine the effectively shortest or fastestroutes through a network, while actual distances or times are summedalong the routes to calculate final values. It is of course alsopossible to calculate distances along fastest routes, times alongshortest routes, or any combination thereof, as detailed in the packagevignette onstreet networks and time-basedrouting.

Routing points can, for example, be randomly selected from the verticesof a graph. The vertices can in turn be extracted with thedodgr_vertices() function:

v<- dodgr_vertices (graph)head (v)

For OSM data extracted with theosmdata package (or, equivalently, viathedodgr::dodgr_streetnet() function), each object (vertices, ways,and high-level relations between these objects) is assigned a uniqueidentifying number. These are retained both inosmdata anddodgr, astheway_id column in the abovegraph, and as theid column in thevertices. Random vertices may be generated in this case throughselectingid 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 geographiccoordinates:

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 pointson the street network. This may, of course, map some points onto minor,disconnected components of the graph. This can be controlled either byreducing the graph to it’s largest connected component only:

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

or by explicitly using thematch_points_to_verts() function with theoptionconnected = 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 ofdodgr_vertices, andso 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)

Flow aggregation refers to the procedure of routing along multiple waysaccording to specified densities of flow between defined origin anddestination points, and aggregating flows along each edge of thenetwork. The procedure is functionally similar to the above procedurefor distances, with the addition of a matrix specifying pairwise flowdensities between the input set of origin (from) and destination(to) points. The following example illustrates use with a random “flowmatrix”:

flows<-array (runif (length (from)* length (to)),dim= c (length (from), length (to)))length (from)#> [1] 20length (to)#> [1] 50dim (flows)#> [1] 20 50f<- dodgr_flows_aggregate (graph=graph,from=from,to=to,flows=flows)

The result is simply the inputgraph with an additional columnquantifying the aggregate flows along each edge:

head (f)

An additional flow aggregation function can be applied in cases whereonly densities at origin points are known, and movement throughout agraph is dispersive:

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

For more detail, see themain packagevignette, andthe second vignette onstreet networks and time-basedrouting

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

mpadge	karpfen	leoniedu	Robinlovelace	agila5	JimShady
DavisVaughan	layik	olivroy	virgesmith

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	meptrsn	RegularnaMatrica

richardellison

coatless

znmeb

yihui

MartinLHazelton