001package algs42; 002import stdlib.*; 003/* *********************************************************************** 004 * Compilation: javac WarshallTC.java 005 * Dependencies: AdjMatrixDigraph.java StdOut.java 006 * 007 * Compute transitive closure of a digraph G and support 008 * reachability queries. 009 * 010 * Preprocessing time: O(V^3) time. 011 * Query time: O(1). 012 * Space: O(V^2). 013 * 014 * % java WarshallTC 10 20 015 * 10 20 016 * 0: 9 2 7 5 017 * 1: 6 7 018 * 2: 019 * 3: 9 9 9 7 6 020 * 4: 7 021 * 5: 7 022 * 6: 7 1 023 * 7: 2 024 * 8: 7 6 0 025 * 9: 2 026 * 027 * Transitive closure 028 * ----------------------------------- 029 * 0 1 2 3 4 5 6 7 8 9 030 * 0: x x x x x 031 * 1: x x x x 032 * 2: x 033 * 3: x x x x x x 034 * 4: x x x 035 * 5: x x x 036 * 6: x x x x 037 * 7: x x 038 * 8: x x x x x x x x 039 * 9: x x 040 * 041 *************************************************************************/ 042 043public class XWarshallTC { 044 private final boolean[][] tc; // tc[v][w] = true iff path from v to w 045 046 public XWarshallTC(XAdjMatrixDigraph G) { 047 048 // initialize tc[][] 049 int V = G.V(); 050 tc = new boolean[V][V]; 051 for (int v = 0; v < V; v++) { 052 for (int w : G.adj(v)) { 053 tc[v][w] = true; 054 } 055 tc[v][v] = true; 056 } 057 058 // Warshall's algorithm 059 for (int i = 0; i < V; i++) { 060 for (int v = 0; v < V; v++) { 061 if (!tc[v][i]) continue; // optimization 062 for (int w = 0; w < V; w++) { 063 if (tc[v][i] && tc[i][w]) tc[v][w] = true; 064 } 065 } 066 } 067 068 } 069 070 // is there a directed path from v to w? 071 public boolean hasPath(int v, int w) { 072 return tc[v][w]; 073 } 074 075 076 // test client 077 public static void main(String[] args) { 078 args = new String[] { "10", "20" }; 079 080 int V = Integer.parseInt(args[0]); 081 int E = Integer.parseInt(args[1]); 082 XAdjMatrixDigraph G = new XAdjMatrixDigraph(V, E); 083 StdOut.println(G); 084 XWarshallTC tc = new XWarshallTC(G); 085 086 // print header 087 StdOut.println("Transitive closure"); 088 StdOut.println("-----------------------------------"); 089 StdOut.print(" "); 090 for (int v = 0; v < G.V(); v++) 091 StdOut.format("%3d", v); 092 StdOut.println(); 093 094 // print transitive closure 095 for (int v = 0; v < G.V(); v++) { 096 StdOut.format("%3d: ", v); 097 for (int w = 0; w < G.V(); w++) { 098 if (tc.hasPath(v, w)) StdOut.format(" x"); 099 else StdOut.format(" "); 100 } 101 StdOut.println(); 102 } 103 } 104 105}