001package algs42;
002import stdlib.*;
003/* ***********************************************************************
004 *  Compilation:  javac TransitiveClosure.java
005 *  Execution:    java TransitiveClosure filename.txt
006 *  Dependencies: Digraph.java DepthFirstDirectedPaths.java In.java StdOut.java
007 *  Data files:   http://algs4.cs.princeton.edu/42directed/tinyDG.txt
008 *
009 *  Compute transitive closure of a digraph and support
010 *  reachability queries.
011 *
012 *  Preprocessing time: O(V(E + V)) time.
013 *  Query time: O(1).
014 *  Space: O(V^2).
015 *
016 *  % java TransitiveClosure tinyDG.txt
017 *         0  1  2  3  4  5  6  7  8  9 10 11 12
018 *  --------------------------------------------
019 *    0:   T  T  T  T  T  T
020 *    1:      T
021 *    2:   T  T  T  T  T  T
022 *    3:   T  T  T  T  T  T
023 *    4:   T  T  T  T  T  T
024 *    5:   T  T  T  T  T  T
025 *    6:   T  T  T  T  T  T  T        T  T  T  T
026 *    7:   T  T  T  T  T  T  T  T  T  T  T  T  T
027 *    8:   T  T  T  T  T  T  T  T  T  T  T  T  T
028 *    9:   T  T  T  T  T  T           T  T  T  T
029 *   10:   T  T  T  T  T  T           T  T  T  T
030 *   11:   T  T  T  T  T  T           T  T  T  T
031 *   12:   T  T  T  T  T  T           T  T  T  T
032 *
033 *************************************************************************/
034
035public class TransitiveClosure {
036        private final DirectedDFS[] tc;  // tc[v] = reachable from v
037
038        public TransitiveClosure(Digraph G) {
039                tc = new DirectedDFS[G.V()];
040                for (int v = 0; v < G.V(); v++)
041                        tc[v] = new DirectedDFS(G, v);
042        }
043
044        public boolean reachable(int v, int w) {
045                return tc[v].marked(w);
046        }
047
048        // test client
049        public static void main(String[] args) {
050                args = new String[] { "data/tinyDG.txt" };
051
052                In in = new In(args[0]);
053                Digraph G = DigraphGenerator.fromIn(in);
054
055                TransitiveClosure tc = new TransitiveClosure(G);
056
057                // print header
058                StdOut.print("     ");
059                for (int v = 0; v < G.V(); v++)
060                        StdOut.format("%3d", v);
061                StdOut.println();
062                StdOut.println("--------------------------------------------");
063
064                // print transitive closure
065                for (int v = 0; v < G.V(); v++) {
066                        StdOut.format("%3d: ", v);
067                        for (int w = 0; w < G.V(); w++) {
068                                if (tc.reachable(v, w)) StdOut.format("  T");
069                                else                    StdOut.format("   ");
070                        }
071                        StdOut.println();
072                }
073        }
074
075}