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. `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")

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); and`dodgr_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:

- Crucial fix of previous typo that made all
`dodgr_dist`

calculations wrong (Earth's radius is 6371, not 3671!) - thanks to @chrijo `weight_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:

- Added Malcolm Morgan (@mem48; bug-finder extraordinare) as contributor
- Bug fix with
`dodgr_paths`

and simple`data.frame`

s, thanks to James Smith. - Bug fix of former improper handling of one-way edges, thanks to @chrijo.
`match_pts_to_graph`

has additional`connected`

parameter to allow points to be matched only to largest connected component.

Major changes:

- New function
`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:

- New function,
`dodgr_paths`

, for returning explicit shortest path routes. - New function,
`dodgr_flows`

, for aggregting flows across a network from multiple origin and destination points. - New function,
`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.- Distance matrices from
`dodgr_dists`

inherit the names of routing points (`from`

and`to`

parameters).

Initial CRAN release.