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.
But wait, there’s more …
dodgr can also aggregate flows throughout a network through specifying origins, destinations, and flow densities. Or even apply a network dispersal model from a set of origin points only.
You can install
Then load with
The primary functions are,
The first function,
dodgr_dists(), 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  + runif (npts) * diff (xlim), y = ylim  + runif (npts) * diff (ylim)) system.time ( d <- dodgr_dists (from = pts) ) #> user system elapsed #> 107.530 0.602 19.418 range (d, na.rm = TRUE) #>  0.00000 21.68109
This 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 20 seconds.
The second function,
dodgr_flows_aggregate(), aggregates the densities specified in the matrix
flows between all pairs of
to points, and returns a modified version of the input network with an additional column containing aggregated flows (see below). The equivalent function,
dodgr_flows_disperse(), does an equivalent thing for network dispersal models from known points of origin.
A graph or network in
dodgr is represented as a flat table (
data.table, whatever) of minimally four columns:
distance. The first two can be of arbitrary form (
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: