Past exam question: 2079 Ashwin (Back), Q12(b)
Open in the Padhaiko appUse Warshall's algorithm to find transitive closure for following graph:
[figure: a directed graph on vertices 0, 1, 2, 3. The available scan shows vertices 0 and 1 at the top with an edge from 1 to 0, and two crossing edges running down from 0 and 1 towards the lower vertices; the lower half of the figure is cut off in the scan.]
Figure incomplete: The bottom of this figure is missing from the only scan we have, so the edges into and out of vertices 2 and 3 cannot be read. The method is shown below; the final matrix is left out rather than guessed.
Solution
Method. Write the adjacency matrix of the graph: when there is an edge , otherwise .
Warshall's update. For in turn, compute
In words: for each row that has a in column , OR row into row .
Result. After the last pass, is the transitive closure: entry is exactly when is reachable from by a path of one or more edges. Worked Example 6.1 in Chapter 6 carries out every pass on a complete 4-vertex graph.
The transitive closure is the matrix obtained after four Warshall passes over the adjacency matrix. The exact matrix cannot be given here because the lower half of the graph is missing from the available scan.