Distances on dual-weighted directed graphs using priority-queue shortest paths. Weighted directed graphs have weights from A to B which may differ from those from B to A. Dual-weighted directed graphs have two sets of such weights. A canonical example is a street network to be used for routing in which routes are calculated by weighting distances according to the type of way and mode of transport, yet lengths of routes must be calculated from direct distances.
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.
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,
d <- dodgr_dists (graph = graph, from = pts, to = pts)
produces a square matrix of distances between all points listed in
and routed along the dual-weighted directed network given in
even simpler usage allows calculation of pair-wise distances between a
set of geographical coordinates (here, for a sizey chunk of New York
xlim <- c (-74.12931, -73.99214)ylim <- c (40.70347, 40.75354)npts <- 1000pts <- 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 secsrange (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
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
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).
For more detail, see the main package
with a second vignette detailing benchmark
showing that under many circumstances,
dodgr performs considerably
faster than equivalent routines from the
dodgr_distcalculations wrong (Earth's radius is 6371, not 3671!) - thanks to @chrijo
weight_streetnetfunction now accepts
wt_profile, enabling modification and direct re-submission of
weighting_profiles$valuemodified to 0-1 scores rather than previous percentage values.
weight_streetnetflags any highway types not present in nominated or submitted weighting profile.
dodgr_pathsnow has additional
pairwiseparameter to enable paths only between matched pairs of
topoints (so returning
npaths rather than
n^2), thanks to @mem48.
data.frames, thanks to James Smith.
connectedparameter to allow points to be matched only to largest connected component.
dodgr_flowmapplots maps of flows. Currently only writes .png files, because large networks can not be effectively plotted on graphic devices.
dodgr_flowshas option to routes flows from a set of source origins to all points in a network, attenuated by distance from those origins.
dodgr_to_sfconverts a spatially-explicit
dodgrgraph into Simple Features (
match_pts_to_graphnow accepts Simple Features (sf) collections of
sfc_POINTobjects to be matched.
Tidy C++ code that flagged errors on CRAN solaris machine. Nothing else.
dodgr_paths, for returning explicit shortest path routes.
dodgr_flows, for aggregting flows across a network from multiple origin and destination points.
merge_directed_flows, to reduce aggregated directional flows to non-directional equivalent values useful for visualisation.
weight_streetnetnow accepts arbitrary
sf-formatted networks via specification of custom weighting profiles, along with highway type and ID columns in data.frame.
dodgr_distsinherit the names of routing points (
Initial CRAN release.