Distances on Directed Graphs

Distances on dual-weighted directed graphs using priority-queue shortest paths (Padgham (2019) ). 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.


BuildStatus AppVeyor BuildStatus codecov Project Status:Active CRAN_Status_Badge CRANDownloads CII BestPractices

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.

Installation

You can install dodgr from github with:

# install.packages("devtools")
devtools::install_github("ATFutures/dodgr")

Note on macOS

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.

Usage

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 <- 1000
pts <- 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 secs
range (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.

Other Functions

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.

The dodgr graph structure

A 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:

  1. dodgr_to_sfc to convert spatial dodgr graphs into Simple Features format used by the sf package.
  2. dodgr_to_igraph to convert (not necessarily spatial) dodgr graphs into igraph format (not yet implemented); and
  3. dodgr_to_tidygraph to convert (not necessarily spatial) dodgr graphs into tidygraph format (not yet implemented).

Further detail

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.

News

v0.1.1.099

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_aggregateto include a non-OSM example fromstplanr::routes_fast` (issue #45).

v0.1.1

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.frames, 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.

v0.1.0

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.

v0.0.3

Tidy C++ code that flagged errors on CRAN solaris machine. Nothing else.

v0.0.2

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

v0.0.1

Initial CRAN release.

Reference manual

It appears you don't have a PDF plugin for this browser. You can click here to download the reference manual.

install.packages("dodgr")

0.2.1 by Mark Padgham, 7 days ago


https://github.com/ATFutures/dodgr


Report a bug at https://github.com/ATFutures/dodgr/issues


Browse source code at https://github.com/cran/dodgr


Authors: Mark Padgham [aut, cre] , Andreas Petutschnig [aut] , Robin Lovelace [ctb] , Andrew Smith [ctb] , Malcolm Morgan [ctb] , Shane Saunders [cph] (Original author of included code for priority heaps)


Documentation:   PDF Manual  


Task views: Handling and Analyzing Spatio-Temporal Data


GPL-3 license


Imports callr, digest, igraph, magrittr, methods, osmdata, rbenchmark, Rcpp, RcppParallel

Suggests dplyr, geodist, ggplot2, igraphdata, jsonlite, knitr, purrr, RColorBrewer, rmarkdown, roxygen2, scales, sf, testthat, tidygraph

Linking to Rcpp, RcppParallel

System requirements: C++11, GNU make


Imported by bikedata.

Suggested by stplanr.


See at CRAN