Distances on dual-weighted directed graphs using priority-queue
shortest paths (Padgham (2019)
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:
On macOS, if you need "gfortran", you could install "gcc" from brew or similar package manager, but on brew "gfortran" is included in "gcc". After installing
gcc you may still have R complaining about
library not found for -lgfortran. Others have written about this issue in detail, we recommend this quick answer on SO and adding a line
FLIBS=-L/usr/local/lib/gcc/8/ (given that you installed gcc8) to your
~/.R/Makevars file for R to be aware of your
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
weight_streetnetis now a method, with implementations for objects of classes
weight_railwayto weight a network for railway routing.
dodgr_distsimplements Dijkstra paths with std::set sorting through new option
dodgr_dists(..., heap = "set")(It's slower than others, but good for sake of completeness).
dodgr_streetnetnow accepts polygonal
bboxargument, and uses
osmdata::trim_osmdatato trim resultant network to within that polygon (issue #50).
to include a non-OSM example fromstplanr::routes_fast` (issue #45).
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.