Edge difference (ED) estimates how contracting a node will change a graph’s edge count. It is the number of shortcut edges needed to preserve shortest paths, minus the edges removed with the node. In contraction-hierarchy routing, ED provides a way to rank nodes before preprocessing a road network for faster queries. section 4.3.4 section 4.4.4
To calculate ED for a candidate node:
- Examine paths that enter the node and leave it through another edge. section 4.4.4
- Count a required shortcut when a shortest path between those neighboring nodes passes through the candidate. An alternative shortest path can make a shortcut unnecessary. section 4.3.4 section 4.4.4
- Subtract the candidate’s degree from the required-shortcut count. The result measures the net edge change, not the length of a route. section 4.4.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 implements this calculation by checking incoming–outgoing edge pairs against precomputed shortest paths, then subtracting each node’s degree. section 4.4.4
The trade-off appears during preprocessing: ranking and contracting nodes costs time so that later searches can examine less of the graph. In one 404-node road network, contraction took about 24 seconds; the resulting query explored 164 nodes rather than 282 for ordinary bidirectional Dijkstra’s, while returning the same route. section 4.4.4
