R/contract.R

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

#' Contraction hierarchies algorithm
#' @description Contract a graph by using contraction hierarchies algorithm
#' @param Graph  An object generated by \link{makegraph} or \link{cpp_simplify} function.
#' @param silent Logical. If \code{TRUE}, progress is not displayed.
#' @return A contracted graph.
#' @details Contraction hierarchies is a speed-up technique for finding shortest path in a graph.
#' It consist of two steps : preprocessing phase and query. \code{cpp_contract()} preprocess the input graph to later use special query algorithm implemented in \link{get_distance_pair}, \link{get_distance_matrix}, \link{get_aon} and \link{get_path_pair} functions.
#' To see the benefits of using contraction hierarchies, see the package description : \url{https://github.com/vlarmet/cppRouting/blob/master/README.md}.
#' @seealso \link{cpp_simplify}
#' @examples
#' #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))
#'
#' #Construct cppRouting graph
#' graph<-makegraph(edges,directed=TRUE)
#'
#' #Contract graph
#' contracted_graph<-cpp_contract(graph,silent=TRUE)


cpp_contract<-function(Graph,silent=FALSE){
  if (length(Graph) != 5) stop("Input should be generated by makegraph() or cpp_simplify() function")

  res <- cppcontract(Graph$data$from,Graph$data$to,Graph$data$dist,Graph$nbnode,!silent)



  return(list(data=data.frame(from=res[[1]][[1]],
                              to=res[[1]][[2]],
                              dist=res[[1]][[3]]),
              rank=res[[2]],
              shortcuts=data.frame(shortf=res[[3]][[1]],
                                   shortt=res[[3]][[2]],
                                   shortc=res[[3]][[3]]),
              nbnode=Graph$nbnode,
              dict=Graph$dict,
              original = Graph[c("data", "attrib")]))
}