Support cppRouting

[latot]

Hi!, I have tested some time ago sfnetworks, which is great! is just some very big networks just does not works very fast to compute things like distance matrix or similars.

cppRouting is actually very fast, I have tested it, it uses Dijkstra Algorithm.

Well, I think the best would be support different libs and algorithms, and be able to choose them on the sfnetwork functions.

Do you think add this lib would be useful here?

https://github.com/vlarmet/cppRouting

Thx!

[Robinlovelace]

Main challenge would be converting to/from input data structures used by cppRouting I think and I guess that would best be done in collaboration with the package author. Thoughts @vlarmet?

[latot]

I have some code with the transformations, but I think have @vlarmet collaboration would be great maybe there is better things to do it.

[latot]

@Robinlovelace I have code, that handle all the transformations using nodes, sfnetworks from/to cppRouting.

I can share it! is like half of this, the other half is connect from the points to the nodes in some way.

[agila5]

Hi @latot! I'm not sure if cppRouting can be included in sfnetworks but I think that, if possible, for the time being, you could share your code here (maybe creating a new discussion) so that other users can test it and benefit from it.

[latot]

Okis! I have tested the differences, at least in speed and time we can have great benefit from it. when I have time, I'll upload it!

[Robinlovelace]

Sounds great @latot happy to take a look when ready.

[latot]

@Robinlovelace @agila5 @vlarmet #254

There is discussion, has a repo with the code how to implement several functions!

[Robinlovelace]

Hi all, I've had a play, in collaboration with @bda1986, and have made some progress. By coincidence, Bernhard has also written some code for sf (but not sfnetworks) object -> cppRouting graph object conversion and has got some nice things working. I have not yet but wanted to report progress. Overall: I think it's well worth adding a function to help create graph objects that can be used for cppRouting, although I have no idea how to get geographic representations from the outputs of cppRouting yet, with the biggest issue being the following:

route_cpp = cppRouting::get_path_pair(graph, from_graph, to_graph)
str(route_cpp)

List of 1
 $ 1244_113: chr(0) 

where's the route? I need to do more work to understand what is going on here...

[Robinlovelace]

P.s. reproducible code in README.qmd, interested to hear if people can reproduce this and thoughts: https://github.com/streetvoronoi/streetvoronoi#routing-with-cpprouting

[latot]

Hi all, I've had a play, in collaboration with @bda1986, and have made some progress. By coincidence, Bernhard has also written some code for sf (but not sfnetworks) object -> cppRouting graph object conversion and has got some nice things working. I have not yet but wanted to report progress. Overall: I think it's well worth adding a function to help create graph objects that can be used for cppRouting, although I have no idea how to get geographic representations from the outputs of cppRouting yet, with the biggest issue being the following:

route_cpp = cppRouting::get_path_pair(graph, from_graph, to_graph)
str(route_cpp)

List of 1
 $ 1244_113: chr(0) 

where's the route? I need to do more work to understand what is going on here...

Hi, that is possible to happens, IIRC if the node 1244 is in a complete different component than 113, two different components are not connected, but this is harder to considerate with directed networks, the best would be detect it and replace with Inf.

I wanted to confirm this, sadly the docs of https://github.com/streetvoronoi/streetvoronoi#routing-with-cpprouting are not complete, the load the data and the initial variables are not described on the doc, so I was not able to follow the example.

[latot]

@Robinlovelace I was able to confirm this, I tested distance and paths, if they are in different components.

• path: will return logical(0)
• distance: will return NA

[Robinlovelace]

Thanks for checking @latot. I cleaned the network by only keeping edges connected to the main component, as per this code:

net_groups = stplanr::rnet_group(net_linestrings)
largest_group = table(net_groups) |> which.max()
net_clean = net_linestrings[net_groups == largest_group, ]

Source: https://github.com/streetvoronoi/streetvoronoi/blob/bfccb3fbd8ee129cc374c1eafd569d2114ca0ee8/README.qmd#L149-L150

How did you diagnose the issue of them being in different components and how should we fix this?

[latot]

Hi, @Robinlovelace I have updated https://github.com/latot/sample_sfnetworks_cppRouting

The shortestpath functions already has that fix, you can see it when is checked with length(), while the distance one does not have it, but I already implemented it latot/sample_sfnetworks_cppRouting@8a9a1fe.

You can se the default values I assigned is "Inf", this is because to follow the logic, the distance between two unconnected lines is Infinite.

While there is a logical issue in represent the shortest path, because there does not exists any linestring that connect both nodes, maybe the best choice would be NA? I don't like NA, because cause a lot of problem (1+NA = NA). For now I'm using an empty linestring, but can be misunderstood when you look the shortest path between the same node, (from node 1 to node 1 is an empty linestring), maybe instead of NA an empty point could do the trick, can be anything except linestring and NA, while is documented.

[latot]

Talking on postgis, thinking in how to represent this cases on the shortest path, the best answer was.

If the shortes path exists, then that linestring

The shortest path from point a to point a, is a linestring with one point, the point a

If the shortest path does not exists, use an empty linestring.

[latot]

@Robinlovelace I have updated the repo https://github.com/latot/sample_sfnetworks_cppRouting/

Now have a real example, some... simplifications? I have splittled how the functions works, and how to read the output of cppRouting, less files, I hope is easier to read.

[Robinlovelace]

Awesome, many thanks! Will aim to take a look soon but may not be until next week..