get_detour {cppRouting} | R Documentation |
Return the nodes that can be reached in a detour time set around the shortest path
Description
Return the nodes that can be reached in a detour time set around the shortest path
Usage
get_detour(Graph, from, to, extra = NULL, keep = NULL, long = FALSE)
Arguments
Graph |
An object generated by makegraph or cpp_simplify function. |
from |
A vector of one or more vertices from which shortest path are calculated (origin). |
to |
A vector of one or more vertices (destination). |
extra |
numeric. Additional cost |
keep |
numeric or character. Vertices of interest that will be returned. |
long |
logical. If |
Details
Each returned nodes n meet the following condition :
SP(o,n) + SP(n,d) < SP(o,d) + t
with SP shortest distance/time, o the origin node, d the destination node and t the extra cost.
Modified bidirectional Dijkstra algorithm is ran for each path.
This algorithm is multithreaded. Please use RcppParallel::setThreadOptions()
to set the number of threads.
Value
list
or a data.frame
of nodes that can be reached
Note
from
and to
must be the same length.
Examples
#Choose number of cores used by cppRouting
RcppParallel::setThreadOptions(numThreads = 1)
if(requireNamespace("igraph",quietly = TRUE)){
#Generate fully connected graph
gf<- igraph::make_full_graph(400)
igraph::V(gf)$names<-1:400
#Convert to data frame and add random weights
df<-igraph::as_long_data_frame(gf)
df$dist<-sample(1:100,nrow(df),replace = TRUE)
#Construct cppRouting graph
graph<-makegraph(df[,c(1,2,5)],directed = FALSE)
#Pick up random origin and destination node
origin<-sample(1:400,1)
destination<-sample(1:400,1)
#Compute distance from origin to all nodes
or_to_all<-get_distance_matrix(graph,from=origin,to=1:400)
#Compute distance from all nodes to destination
all_to_dest<-get_distance_matrix(graph,from=1:400,to=destination,)
#Get all shortest paths from origin to destination, passing by each node of the graph
total_paths<-rowSums(cbind(t(or_to_all),all_to_dest))
#Compute shortest path between origin and destination
distance<-get_distance_pair(graph,from=origin,to=destination)
#Compute detour with an additional cost of 3
det<-get_detour(graph,from=origin,to=destination,extra=3)
#Check result validity
length(unlist(det))
length(total_paths[total_paths < distance + 3])
}