Node contraction makes shortest-path searches faster by removing a node from a working graph while adding any shortcut edges needed to preserve shortest-path distances. In road routing, it is the preprocessing operation behind contraction hierarchies: contract less important intersections first, then search mainly through increasingly important connections. section 4.3.4
Deciding whether a shortcut is needed
Suppose a shortest route from u to w goes through v, with edge costs 2 and 3. Contracting v would lose that cost-5 route, so add a u-to-w shortcut of cost 5. If another route between u and w costs 4, it already serves as a witness path: no shortcut is needed. section 4.3.4
To use contraction in a routing graph:
- Rank nodes by importance and contract them from least to most important. Edge difference—the number of required shortcuts minus the node’s degree—is one ranking measure. section 4.3.4 section 4.4.4
- For paths through each contracted node, test whether removing it changes a shortest path. Add weighted shortcuts where needed and record the removed node so a route can later be unpacked. section 4.3.4 section 4.4.4
- Run a bidirectional shortest-path search on the preprocessed graph, following increasingly important edges. Expand shortcuts afterward to recover the route through the original nodes. section 4.3.4 section 4.4.4
Figure 4.24 Witness path—there is another path from P to w that is shorter, so no shortcut is needed when contracting v.
The witness-path figure shows why contracting a node does not require a shortcut when another shorter route remains. section 4.3.4
Listing 4.10 U of T routing using CH
def edge_differences(G, sp):
ed = {}
degrees = dict(G.degree)
for node in G.nodes:
req_edges = 0
neighbours = list(G.neighbors(node))
if len(neighbours)==0: ed[node] = - degrees[node] #1
for u, v in G.in_edges(node):
for v, w in G.out_edges(node):
if u == w: continue #2
if v in sp[u][w]:
req_edges += 1
ed[node] = req_edges - degrees[node] #3
return dict(sorted(ed.items(), key=lambda x: x, reverse=True))
The Python listing counts shortcuts needed through each node and subtracts its degree to calculate edge difference. section 4.4.4
def unpack(G, u,v):
u = int(u)
v = int(v)
if "midpoint" in G[u][v][0]:
midpoint = G[u][v][0]["midpoint"]
return unpack(G,u,midpoint) + unpack(G,midpoint, v) #1
return [u]
route = []
for u,v in zip(solution.result[:-1], solution.result[1:]): #2
route.extend(unpack(G,u,v))
route += [solution.result[-1]]
print(route)
The recursive unpacking code follows stored midpoints to turn shortcut edges back into a route through original nodes. section 4.4.4
The payoff depends on the graph and the cost of preprocessing. In one road-network example, contraction hierarchies explored 164 nodes rather than the 282 explored by ordinary bidirectional Dijkstra’s, while returning the same route. Contracting that 404-node graph took about 24 seconds; the reported query time excludes this work. Test both preprocessing and query costs before choosing contraction for an application. section 4.4.4
