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. 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:
# install.packages("devtools")devtools::install_github("ATFutures/dodgr")
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 gcc
path.
The primary function,
d <- dodgr_dists (graph = graph, from = pts, to = pts)
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 <- 1000pts <- 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 secsrange (d, na.rm = TRUE)#> [1] 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
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.
Major changes:
dodgr_to_igraph
weight_streetnet
is now a method, with implementations for objects of
classes .sf
and .sc
.weight_railway
to weight a network for railway routing.dodgr_dists
implements Dijkstra paths with std::set sorting through new
option dodgr_dists(..., heap = "set")
(It's slower than others, but good for
sake of completeness).Minor changes:
dodgr_streetnet
now accepts polygonal bbox
argument, and uses
osmdata::trim_osmdata
to trim resultant network to within that polygon
(issue #50).weight_streetnet
and dodgr_flows_aggregateto include a non-OSM example from
stplanr::routes_fast` (issue #45).Major changes:
dodgr_dist
calculations wrong
(Earth's radius is 6371, not 3671!) - thanks to @chrijoweight_streetnet
function now accepts data.frame
objects defining
wt_profile
, enabling modification and direct re-submission of
dodgr::weighting_profiles
weighting_profiles$value
modified to 0-1 scores rather than previous
percentage values.weight_streetnet
flags any highway types not present in nominated or
submitted weighting profile.dodgr_paths
now has additional pairwise
parameter to enable paths only
between matched pairs of from
and to
points (so returning n
paths rather
than n^2
), thanks to @mem48.dodgr_to_sf
deprecated to dodgr_to_sfc
(#43)Minor changes:
dodgr_paths
and simple data.frame
s, thanks to James Smith.match_pts_to_graph
has additional connected
parameter to allow points to
be matched only to largest connected component.Major changes:
dodgr_flowmap
plots maps of flows. Currently only writes .png
files, because large networks can not be effectively plotted on graphic
devices.dodgr_flows
has option to routes flows from a set of source origins to all
points in a network, attenuated by distance from those origins.dodgr_to_sf
converts a spatially-explicit dodgr
graph into Simple Features
(sf
) format.Minor changes:
match_pts_to_graph
now accepts Simple Features (sf) collections of
sfc_POINT
objects to be matched.Tidy C++ code that flagged errors on CRAN solaris machine. Nothing else.
Major changes:
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.Minor changes:
weight_streetnet
now accepts arbitrary sf
-formatted networks via
specification of custom weighting profiles, along with highway type and ID
columns in data.frame.dodgr_dists
inherit the names of routing points
(from
and to
parameters).Initial CRAN release.