cppRouting (version 3.1)

get_detour: 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)

Value

list or a data.frame of nodes that can be reached

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 TRUE, a long data.frame is returned instead of a list.

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.

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

}