get_detour: Return the nodes that can be reached in a detour time set...

In cppRouting: Algorithms for Routing and Solving the Traffic Assignment Problem

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 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.

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

}

cppRouting documentation built on Dec. 1, 2022, 5:08 p.m.