Contraction hierarchies

Contraction hierarchies (CH) speed up shortest-path queries by doing work before anyone asks for a route. On a large road network, even bidirectional Dijkstra’s algorithm may explore too many vertices for an interactive navigation app. CH ranks vertices by importance, contracts the less important ones first, and adds shortcuts so shortest paths remain available. Queries then search the augmented graph with a modified bidirectional Dijkstra’s algorithm. section 4.3.4 section 4.5

Think of preprocessing and querying as separate jobs:

• Choose an importance order. Edge difference is one option: estimate the shortcuts a vertex needs, then subtract the edges removed by contracting it. Contract from least important to most important. section 4.4.4 section 4.5
• For a path through a vertex being contracted, add a shortcut between its neighbors when removing that vertex would change their shortest path. Do not add an unnecessary shortcut if a shorter alternative, called a witness path, already exists. section 4.3.4
• Run the hierarchy-aware bidirectional search. A shortcut represents part of the route, so unpack its stored midpoint to recover the original sequence of vertices. 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 diagram shows why contracting a vertex does not require a shortcut when an alternative path is shorter. section 4.3.4

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 calculates edge difference from a vertex’s neighbors, required shortcuts, and degree before ranking vertices. section 4.4.4

The trade-off is preprocessing time. In a 404-vertex road network, contraction took about 24 seconds; a subsequent CH query explored 164 vertices instead of the 282 explored by ordinary bidirectional Dijkstra’s—more than 40% fewer—while returning the same optimal route. Query timing alone hides that setup cost. CH is therefore attractive when fast routing queries justify preprocessing, but not automatically the best choice for every graph or application. 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 Python function follows each shortcut’s midpoint until it can assemble the route from original edges. section 4.4.4