get_path_pair: Compute shortest path between origin and destination nodes.

Description

Compute shortest path between origin and destination nodes.

Usage

get_path_pair(
  Graph,
  from,
  to,
  algorithm = "bi",
  constant = 1,
  keep = NULL,
  long = FALSE
)

Value

list or a data.frame containing shortest path nodes between from and to.

Arguments

Graph: An object generated by makegraph, cpp_simplify or cpp_contract function.
from: A vector of one or more vertices from which shortest paths are calculated (origin).
to: A vector of one or more vertices (destination).
algorithm: character. Dijkstra for uni-directional Dijkstra, bi for bi-directional Dijkstra, A* for A star unidirectional search or NBA for New bi-directional A star .Default to bi
constant: numeric. Constant to maintain the heuristic function admissible in A* and NBA algorithms.
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. Default to 1, when cost is expressed in the same unit than coordinates. See details

Details

If graph is not contracted, the user has the choice between :

unidirectional Dijkstra (Dijkstra)
A star (A*) : projected coordinates should be provided
bidirectional Dijkstra (bi)
New bi-directional A star (NBA) : projected coordinates should be provided

If the input graph has been contracted by cpp_contract function, the algorithm is a modified bidirectional search.

In A* and NBA algorithms, euclidean distance is used as heuristic function.

All algorithms are multithreaded. Please use RcppParallel::setThreadOptions() to set the number of threads.

To understand the importance of constant parameter, see the package description : https://github.com/vlarmet/cppRouting/blob/master/README.md

Examples

Run this code

#Choose number of cores used by cppRouting
RcppParallel::setThreadOptions(numThreads = 1)

#Data describing edges of the graph
edges<-data.frame(from_vertex=c(0,0,1,1,2,2,3,4,4),
                  to_vertex=c(1,3,2,4,4,5,1,3,5),
                  cost=c(9,2,11,3,5,12,4,1,6))

#Get all nodes
nodes<-unique(c(edges$from_vertex,edges$to_vertex))

#Construct directed and undirected graph
directed_graph<-makegraph(edges,directed=TRUE)
non_directed<-makegraph(edges,directed=FALSE)

#Sampling origin and destination nodes
origin<-sample(nodes,10,replace=TRUE)
destination<-sample(nodes,10,replace=TRUE)

#Get distance between origin and destination in the two graphs
dir_paths<-get_path_pair(Graph=directed_graph, from=origin, to=destination)
non_dir_paths<-get_path_pair(Graph=non_directed, from=origin, to=destination)
print(dir_paths)
print(non_dir_paths)