liveBook · Manning

Node importance

As explained in Optimization Algorithms: AI techniques for design, planning, and control problems

A dynamic priority estimate indicating how attractive it is to contract a graph node next.

Node importance is a priority estimate for choosing which node to contract next in a contraction hierarchy (CH). The resulting order shapes preprocessing: contracting a node can require shortcuts that preserve shortest-path distances. section 4.3.4

For a road network, consider:

  • Road type: residential roads, national roads, and highways suggest different importance levels. section 4.3.4
  • Maximum speed, toll rates, and number of turns as additional heuristics. section 4.3.4

A contraction needs no shortcut when another path between the affected nodes costs no more than the route through the contracted node. Choosing an order therefore matters to the augmented graph built before fast queries. section 4.3.4

Figure 4.27 Edge difference in case of a hub node. The numbers in brackets denote the cost of the added shortcuts.

The hub-node figure shows the shortcuts and their costs for one contraction choice. section 4.3.4

How Optimization Algorithms: AI techniques for design, planning, and control problems covers it

How deep it goes
Explains ranking heuristics and how contraction affects shortcuts without specifying a numerical importance formula.
Examples
Uses road types and a hub-node contraction figure to illustrate ranking considerations.
What it assumes
Assumes weighted directed graphs and shortest-path costs while explaining contraction and shortcuts.
What you can do after
Operate/configure it by selecting road-network heuristics for a contraction order and checking the shortcuts that result.
How it connects
Links contraction hierarchies, shortest paths, shortcuts, witness paths, and road-network routing.
Cover of Optimization Algorithms: AI techniques for design, planning, and control problems
liveBookmanning.com
Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

This explainer was generated by Manning's knowledge graph from the text of Optimization Algorithms: AI techniques for design, planning, and control problems. The section links point to the parts of the book it draws on.