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  + runif (npts) * diff (xlim), y = ylim  + 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) #>  0.00000 16.64285
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 10 seconds.
The other main functions of
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.
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:
dodgr_to_sfcto convert spatial
dodgrgraphs into Simple Features format used by the
dodgr_to_igraphto convert (not necessarily spatial)
igraphformat (not yet implemented); and
dodgr_to_tidygraphto convert (not necessarily spatial)
tidygraphformat (not yet implemented).