cpp_contract: Contraction hierarchies algorithm

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

Contraction hierarchies algorithm

Description

Contract a graph by using contraction hierarchies algorithm

Usage

cpp_contract(Graph, silent = FALSE)

Arguments

Graph	An object generated by makegraph or cpp_simplify function.
silent	Logical. If TRUE, progress is not displayed.

Details

Contraction hierarchies is a speed-up technique for finding shortest path in a graph. It consist of two steps : preprocessing phase and query. cpp_contract() preprocess the input graph to later use special query algorithm implemented in get_distance_pair, get_distance_matrix, get_aon and get_path_pair functions. To see the benefits of using contraction hierarchies, see the package description : https://github.com/vlarmet/cppRouting/blob/master/README.md.

Value

A contracted graph.

See Also

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)

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