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); 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:

- New function
`dodgr_to_igraph`

`weight_streetnet`

is now a method, with implementations for objects of classes`.sf`

and`.sc`

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

- Various modifications that should result in notable speed gains
`dodgr_streetnet`

now accepts polygonal`bbox`

argument, and uses`osmdata::trim_osmdata`

to trim resultant network to within that polygon (issue #50).- Extended examples for
`weight_streetnet`

and dodgr_flows_aggregate`to include a non-OSM example from`

stplanr::routes_fast` (issue #45).

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.