support cppRouting

[mem48]

Its seems that https://github.com/vlarmet/cppRouting is fast and powerful, perhaps this is how we should be doing route networks?

[mpadge]

It is definitely fast and powerful, but comes with an important caveat: It it not a dual-weighted algorithm, so routing can only be done via actual geometrical shortest paths, and can not be weighted for different modes of transport.

[mem48]

Good point @mpadge I'd been using dodgr but running into problems (e.g. UrbanAnalyst/dodgr#126) so was trying out some of the alteratives. cppRouting seems better than the sf/igraph solution but is missing some simple features that make ploting easy. But I think we could easily wrap cppRouting to add most of these features.

For the different modes you could probably store different weights and pass them to cppRouting as required, they seem to just come from a data.frame Not ideal but would work.

[mpadge]

No, you can't unfortunately use a single-weighted Dijkstra at all for dual-weighted problems. Dual-weighted algorithms choose a path based on one weight, but calculate the resultant distance with the other. An algorithm which only receives a single weight can only calculate the distance of the path, so only a direct distance, or some non-physical sum of weighted distances, but can not calculate actual distances along weighted paths. The whole business is generally really tricky, and depends a lot on what kind of end applications are envisioned for a particular application. I've removed any comparisons with other software from dodgr, because there are never any sufficiently neutral grounds for comparison.

The closest you could get to use cppRouting for dual-weighted application would be to use the weighted graph to get paths from cppRouting, and then to aggregate actual distances according to those paths. This reprex reveals some pretty profound inefficiencies of cppRouting (noting that the get_path_pair() function assumes paired lists of OD points, so these have to be explicitly constructed, while dodgr_paths evaluates all pairwise combinations of origin & dest). The paths are what would be required to trace dual-weighted graphs, for which cppRouting would be quite enormously less efficient than dodgr:

library(cppRouting)
library(igraph)
library(dodgr)
h <- readRDS (<highway>/<system>/<of>/<New York City>.Rds)
dodgr_cache_off ()
net <- weight_streetnet (h, wt_profile = "foot")
#> Loading required namespace: geodist
#> Loading required namespace: dplyr
net <- net [net$component == 1, ]
v <- dodgr_vertices (net) [, c ("id", "x", "y")]
net0 <- net [, c (".vx0", ".vx1", "d_weighted")]
graph <- makegraph (net0, directed = TRUE, coords = v)
origin <- sample (graph$dict$ref, 50)
dest <- sample (graph$dict$ref, 100)
origin2 <- rep (origin, each = length (dest)) # to get all pairwise ODs for get_path_pair()
dest2 <- rep (dest, time = length (origin))
microbenchmark::microbenchmark (
    cppdists = d1 <- get_distance_matrix (graph, from=origin, to=dest, allcores = FALSE),
    cpppaths = p1 <- get_path_pair (graph, from=origin2, to=dest2, long = FALSE),
    dodgr_dists = d2 <- dodgr_distances (net, from = origin, to = dest, parallel = FALSE),
    dodgr_paths = p2 <- dodgr_paths (net, from = origin, to = dest),
    times = 1L
)
#> Running bidirectional Dijkstra...
#> Unit: seconds
#>         expr        min         lq       mean     median         uq        max
#>     cppdists   2.144544   2.144544   2.144544   2.144544   2.144544   2.144544
#>     cpppaths 106.944702 106.944702 106.944702 106.944702 106.944702 106.944702
#>  dodgr_dists   5.561910   5.561910   5.561910   5.561910   5.561910   5.561910
#>  dodgr_paths   5.538563   5.538563   5.538563   5.538563   5.538563   5.538563
#>  neval
#>      1
#>      1
#>      1
#>      1

^{Created on 2020-01-14 by the reprex package (v0.3.0)}

[mem48]

I see, thanks for the explanation

[vlarmet]

Hi!
I confirm that cppRouting implement only single weighted graph so far.
I have initially created cppRouting for working on very large graph, that's why you can contract the graph with contraction hierarchies algorithm.
However, you can use cppRouting::get_multi_paths function instead of replicate origins/destination and use get_path_pair
Cheers

[Robinlovelace]

Great, thanks for the info, definitely want to support this. Wider question is: should we split-out the route() function into a minimal package that is just for routing? I can see advantages of that approach.

[Robinlovelace]