convert a shape file to dodgr network?

[sriramab]

I am looking for options/functions within dodgr to convert a shapefile to dodgr network. I see something rcpp_sf_as_network but I am not sure which function can be used to convert sf to network. I would like to then connect origin to destination via waypoints. I would like to try #210 but I am also wondering if there is any new function that accepts waypoints between origin and destination. I am doing something similar to #210 where a city has 1000 origin-destination pair movements via waypoints and after plotting these, I would like to get volume on each link.

[mpadge]

Hi @sriramab, the "dodgr" package works fine with sf input, so you'd just need to use that package to first convert your shapefile to sf format and use that as input here.

The waypoints question is more interesting, and one I hadn't previously considered. Distances via waypoints would be sufficiently straightfoward, by just making two requests, from origins to waypoints, and from waypoints to destinations. But you mention you want to get "volume on each link", by which I presume you mean flow volumes? In that case, the dodgr_flows_... functions don't really lend themselves so easily to waypoint calculations. Could you please explain a bit more about what you're trying to do? Thanks

[sriramab]

Hi @mpadge , I am trying to do something complex. But to draw analogy, let us assume I have public-transport service. For each trip I know its starting point and end point and waypoints between this start and end point. I also have a shapefile which is the road network these trips would traverse through. So you could consider bus stops or drop-off pickup points as way-points along the way. When these trips come on a mass scale, that is , 1000's of trips, as you would expect each road segment (link) to have an added flow volume (1+1+....+1 = n). So in the end, i would like to know how many trips (flow volume) occured on each road segment of the road network. Definition of a road segment or a link is a stretch of road between two intersections/ junctions.

[mpadge]

If they really are public transport trips, and - the important bit - if you can get GTFS data for the services, then you can use the gtfsrouter package for that. Or even the (currently experimental) m4ra package. I use that to combine millions of pairwise trips combining public transport, driving, walking, cycling, whatever, and it all works very well. If bus trips are regulated according to a timetable, then this package is overkill. You just need the bus routes in whatever format, and a program to scan the timetable and add trips along each segment of the route.

[sriramab]

Thank you for the references. I do not want to use routing services and would like to use a static local shapefile as the network/ graph . I do not have a gtfs for my area of interest. I want path calculations , flow volumes on my network with origin, destination and via waypoints. What do you suggest?

[mpadge]

But the question is where your flow volumes are supposed to represent volumes of timetabled public transport services? If so, you don't even need dodgr. What are your actual origin and destination pairs? Obviously they're spatial coordinates, but what do they represent for your analysis?

[sriramab]

They are regular transport hubs where a service would start and may end at any other hub (may or may not be the starting hub). It is not timetable based but on-demand service.

[mpadge]

Hi again @sriramab. I'm happy to keep iterating here until we find a workable solution for you. Based on your latest comment - and again, all with the caveat that I may be failing to understand what you're really trying to do :smirk: - I suspect what I'd try to do would be to use dodgr to extract all possible segments between all pairs of stops. Do that just one time to get a collection of segments. Then convert the stops into a separate abstract graph where each edge is a consecutive pair of stops, and the graph is constructed so that each route has to traverse the specified sequence. Then feed in whatever data you have to generate the aggregate flows along all edges in that graph. With that, you can then map those flows back on to the actual edge segments extracted in the first step. Would that work?

[sriramab]

hi, thank you for your time. I have made a small sample. I have hundreds of tables like below.

I want to plot and count. Steps for plot:- for each vehicle, each trip, there is a sequence of waypoints (points-lat/long). you may consider first and last point in this sequence to be source and destination. I would like to generate a path along this sequence, but along the graph created by my shapefile (sf). I do not want to use any routing services because I may even draw my own simple xy cartesian locations to do some proof of concepts.

Steps to count:- once I have plotted all these sequences, I want to count numbers of passes on each segment of my graph.

When I look at your suggestion, I think you are suggesting that I do all "individual consequetive pairs" along the sequence and then somehow count the passes on each link. Is that right? I think I have an idea to do this with dodgr and I did somethign similar two years ago and we captured some bugs along the way.

If there is no direct function or no plans to develop a single function which generates a path along the sequence of points (waypoints), I would try your suggestion. Only challenge in your suggestion (or may be coz of my lack of understanding) that remains is I will not be able to identify each sequence back to a table or link a path to my table of trips.

[mpadge]

So i had a try implementing the kind of approach I suggested, but the resultant graphs end up even bigger than original graphs, and the whole approach is very inefficient. That leaves us back with the first question, of how to constrain routing to go through specified way points ... This is, unfortunately, not generally solvable in any efficient way, because it is effectively the travelling saleperson problem. You're going to have to build some kind of modified graph, based on your transport connections, which follow a strict sequence.

I would probably try something like getting all sequential pairs of stops from your transport plan/shapefile/whatever. Some example code to do that could take the demo graph from this package ("hampi"), and pretend that the end vertices of way "way_id" were the waypoints you were interested in. Reduction to sequential pairs would in that case be quite simple:

library (dodgr)
net <- weight_streetnet(hampi)

# Get end vertices of ways (doesn't matter whether from "from_id" or "to_id"):
end_verts <- dplyr::group_by (net, way_id, from_id) |>
    dplyr::summarise (freq = dplyr::n(), .groups = "drop_last") |>
    dplyr::filter (freq == 1L)
# The split into consecurive (from, to) pairs for each "way_id":
end_verts <- dplyr::group_by (end_verts, way_id) |>
    dplyr::summarise (from = dplyr::first (from_id), to = dplyr::last (from_id))

graph_reduced <- dplyr::group_by (net, way_id) |>
    dplyr::summarise (from = dplyr::first (from_id), to = dplyr::last (to_id), d = sum (d))

You can then perform routing or flow aggregation calculations on that reduced graph, and presume that routing would very likely always pass through your desired sequences (although without an absolute guarantee, but likely near enough for most purposes).

---

In more general cases, it wouldn't be so easy to contract sequences of edges between stops like that code does, and you'd have to do something like the following:

1. First calculate paths between all of your pairs:

paths <- dodgr_paths (net, from = end_verts$from, to = end_verts$to, pairwise = FALSE, vertices = TRUE)

2. Reduce those only to paths between sequential vertex pairs, which in this case are paths than have a length of two:

end_verts_vec <- unique (c (end_verts$from, end_verts$to))
lens <- unlist (lapply (paths, function (i) {
    lapply (i, function (j) {
        length (which (j %in% end_verts_vec))
    })
}))
lens <- lens [which (lens == 2)]

3. Extract edges for those paths only, starting by getting (from, to) IDs from names

from_id <- gsub ("\\..*$", "", names (lens))
to_id <- gsub ("^.*\\-", "", names (lens))
from_to <- cbind (from_id, to_id)
from_to <- from_to [which (!duplicated (from_to)), ]

4. Recalculate paths only along those sequential pairs, return them as indices in graph edges, and convert those path indices to reduced graph edges:

paths <- dodgr_paths (net, from = from_to [, 1], to = from_to [, 2], pairwise = TRUE, vertices = FALSE)

paths_reduced <- lapply (paths, function (i) {
    index <- i [[1]] # pairwise paths are always list of 1 element
    if (is.null (index)) return (NULL)
    res <- net [c (index [1], tail (index, 1)), ]
    res$d <- sum (net$d [index])
    res$d_weighted <- sum (net$d_weighted [index])
    res$time <- sum (net$time [index])
    res$time_weighted <- sum (net$time_weighted [index])
    return (res)
})
graph_reduced <- do.call (rbind, paths_reduced)
# These can still contain duplicated edges which should be removed:
ft <- as.matrix (graph_reduced [, c ("from_id", "to_id")])
graph_reduced <- graph_reduced [which (!duplicated (ft)), ]
rownames (graph_reduced) <- NULL

Something like that should also reduce your graph to one which does a good job of "forcing" routing to pass through sequences of points. It's not the most efficient code, but should easily scale to 1000 or so points. Routing may still pass through alternative routes where these might be shorter than specified transport routes, but unless the transport system is notably circuitous, this should be unlikely. It shouldn't be too hard to apply an additional dodgr_paths() call to all actual transport start and end points and confirm that these do indeed pass through expected sequences, and/or find out how to explicitly modify the graph to avoid any which do not behave as expected.