EssentialSubgraphLab: Essential Subgraphs of Random Graphs
About the Lab
You are given a graph or digraph
G = (V,E,W) with positive
weights on edges. The
distance between vertices
x
and
y is defined as cost of the least-cost path between
x and
y, summing weights of edges used in the path.
For any pair x,y, the edge (x,y) may or may or may not be
the shortest path. An edge of G is called essential
if it is uniquely the shortest path between its endpoints: that is if
there is no alternative path of equal or smaller cost.
The Essential Subgraph Problem is, given G, to find
the subgraph S containing only the essential edges of G. This
problem has many similarities with All-Pairs Shortest-Paths.
The algorithm described here works by considering edges of G
in increasing order by weight, and building the Essential Subraph S
on the fly. If (x,y) is essential (based on a search in S),
then it adds the edge to S and otherwise discards it. The
runtime is O(ns log n), where s is the number of edges in
S at the end of the computation. In the standard averagae case
model s = O(n log n).
Resources and Links
The algorithm and these versions are described in Chapter 4: Tuning Algorithms, Tuning Code.
- subgraph0.c Version 0 in the book. Simple implementation of the algorithm.
- subgraph1.c Version 1. Memoization with a distance matrix
- subgraph2.c Version 2. memoization+ no loop abort + yes filter the heap
(selected after 8-way test of all combinations)
- subgraph3.c Version 3: V2 plus bfs with loop abort (outer loop).
- timetest0.in Sample shell script for time tests.
- n100.in Sample input command file.
- See: C. McGeoch, All Pairs Shortest Paths and the Essential
Subgraph to learn more about this algorithm and properties.
Projects
- Try more of the algorithm and code tuning ideas suggested in Chapter 4. How fast can you make
it run?
- The tuning process would be very different if different input graph models were used. Try engineering this
algorithm for road-map graphs.
- Try tuning the heap data structure for a different application: for example to support Dijkstra's
Single-Source Shortest Path algorithm.
- This algorithm is easily adapted to solve the all-pairs shortest paths problem. How would you adapt
these tune-ups to solve that problem on real-world instances?