| cpp_contract | R Documentation |
Contract a graph by using contraction hierarchies algorithm.
cpp_contract(Graph, silent = FALSE, customizable = FALSE, order = NULL)
Graph |
An object generated by makegraph or cpp_simplify function. |
silent |
Logical. If |
customizable |
Logical. If |
order |
Optional node order, only used when |
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.
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.
cpp_simplify
#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)
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.