cpp_contract: Contraction hierarchies algorithm

View source: R/contract.R

cpp_contractR Documentation

Contraction hierarchies algorithm

Description

Contract a graph by using contraction hierarchies algorithm.

Usage

cpp_contract(Graph, silent = FALSE, customizable = FALSE, order = NULL)

Arguments

Graph

An object generated by makegraph or cpp_simplify function.

silent

Logical. If TRUE, progress is not displayed.

customizable

Logical. If TRUE, build a customizable contraction hierarchy (CCH) instead of a classical one: only the graph topology is contracted, so shortcut costs can be recomputed cheaply with cpp_customize whenever edge weights change. See Details.

order

Optional node order, only used when customizable = TRUE. Values must be node references from Graph$dict$ref. If omitted, cppRouting computes a simple local order. Large road networks usually benefit from a stronger nested-dissection order prepared outside this function.

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.

When customizable = TRUE, contraction is split into two phases instead:

  • Preparation (this function): builds shortcuts from the road topology. This step is reusable as long as the set of edges does not change.

  • Customization (cpp_customize): updates shortcut costs from the current edge weights. This step is repeated when congestion changes travel times.

For traffic assignment, prepare once and call assign_traffic(..., aon_method = "cch", cch = cch). The CCH assignment path uses the elimination-tree query, which is the fast query variant for repeated origins or repeated destinations.

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, or (when customizable = TRUE) a CCH topology object. Run cpp_customize before distance queries on a CCH topology object, or pass it to assign_traffic through the cch argument to avoid rebuilding the topology at each model run.

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)

#Build a customizable contraction hierarchy instead
cch <- cpp_contract(graph, customizable = TRUE)
metric <- cpp_customize(cch)
get_distance_pair(metric, from = 0, to = 3)

cppRouting documentation built on Nov. 12, 2026, 5:11 p.m.