R package for calculating pairwise distances on dual-weighted directed graphs using Priority Queue Shortest Paths. Dual-weighted directed graphs are directed graphs with two sets of weights so that weight1(A->B) != weight1(B->A)—the directed property—and weight2(A->B) != weight1(A->B)—the dual property. dodgr calculates shortest paths according to one weight, while distances along paths are calculating using the other weight. A canonical example of a dual-weighted directed graph is a street network to be used for routing. Routes are usually calculated by weighting different kinds of streets or ways according to a particular mode of transport, while the desired output is a direct, unweighted distance.
You can install dodgr from github with:
The primary function,
produces a square matrix of distances between all points listed in pts and routed along the dual-weighted directed network given in graph. An even simpler usage allows calculation of pair-wise distances between a set of geographical coordinates (here, for a sizey chunk of New York City):
xlim <- c (-74.12931, -73.99214)
ylim <- c (40.70347, 40.75354)
npts <- 1000
pts <- data.frame (x = xlim [1] + runif (npts) * diff (xlim),
y = ylim [1] + runif (npts) * diff (ylim))
st <- Sys.time ()
d <- dodgr_dists (from = pts)
Sys.time () - st
#> Time difference of 9.473597 secs
range (d, na.rm = TRUE)
#> [1] 0.00000 16.64285This will automatically download the street network (using osmdata), and even then calculating distances between 1,000 points – that’s 1,000,000 pairwise distances! – can be done in around 10 seconds.
The other main functions of dodgr are dodgr_paths, to return the actual paths between pairs of vertices, and dodgr_flows to aggregate flows as routed throughout a network according to sets of start and end points (origins and destinations), and associated densities or numbers travelling between each of these.
dodgr graph structureA graph or network in dodgr is represented as a flat table (data.frame, tibble, data.table, whatever) of minimally four columns: from, to, weight, and distance. The first two can be of arbitrary form (numeric or character); weight is used to evaluate the shortest paths, and the desired distances are evaluated by summing the values of distance along those paths. For a street network example, weight will generally be the actual distance multiplied by a priority weighting for a given mode of transport and type of way, while distance will be the pysical distance.
dodgr includes the conversion functions:
dodgr_to_sfc to convert spatial dodgr graphs into Simple Features format used by the sf package.dodgr_to_igraph to convert (not necessarily spatial) dodgr graphs into igraph format (not yet implemented); anddodgr_to_tidygraph to convert (not necessarily spatial) dodgr graphs into tidygraph format (not yet implemented).For more detail, see the main package vignette, along with a second vignette detailing benchmark timings, showing that under many circumstances, dodgr performs considerably faster than equivalent routines from the igraph package.