001package algs42;
002import stdlib.*;
003import algs13.Queue;
004import algs13.Stack;
005import algs44.DirectedEdge;
006import algs44.EdgeWeightedDigraph;
007/* ***********************************************************************
008 *  Compilation:  javac DepthFirstOrder.java
009 *  Execution:    java DepthFirstOrder filename.txt
010 *  Dependencies: Digraph.java Queue.java Stack.java StdOut.java
011 *                EdgeWeightedDigraph.java DirectedEdge.java
012 *  Data files:   http://algs4.cs.princeton.edu/42directed/tinyDAG.txt
013 *                http://algs4.cs.princeton.edu/42directed/tinyDG.txt
014 *
015 *  Compute preorder and postorder for a digraph or edge-weighted digraph.
016 *  Runs in O(E + V) time.
017 *
018 *  % java DepthFirstOrder tinyDAG.txt
019 *     v  pre post
020 *  --------------
021 *     0    0    8
022 *     1    3    2
023 *     2    9   10
024 *     3   10    9
025 *     4    2    0
026 *     5    1    1
027 *     6    4    7
028 *     7   11   11
029 *     8   12   12
030 *     9    5    6
031 *    10    8    5
032 *    11    6    4
033 *    12    7    3
034 *  Preorder:  0 5 4 1 6 9 11 12 10 2 3 7 8
035 *  Postorder: 4 5 1 12 11 10 9 6 0 3 2 7 8
036 *  Reverse postorder: 8 7 2 3 0 6 9 10 11 12 1 5 4
037 *
038 *************************************************************************/
039
040public class DepthFirstOrder {
041        private final boolean[] marked;          // marked[v] = has v been marked in dfs?
042        private final int[] pre;                 // pre[v]    = preorder  number of v
043        private final int[] post;                // post[v]   = postorder number of v
044        private final Queue<Integer> preorder;   // vertices in preorder
045        private final Stack<Integer> revPost;    // vertices in preorder
046        private final Queue<Integer> postorder;  // vertices in postorder
047        private int preCounter;            // counter or preorder numbering
048        private int postCounter;           // counter for postorder numbering
049
050        // depth-first search preorder and postorder in a digraph
051        public DepthFirstOrder(Digraph G) {
052                pre    = new int[G.V()];
053                post   = new int[G.V()];
054                revPost   = new Stack<>();
055                postorder = new Queue<>();
056                preorder  = new Queue<>();
057                marked    = new boolean[G.V()];
058                for (int v = 0; v < G.V(); v++)
059                        if (!marked[v]) dfs(G, v);
060        }
061
062        // depth-first search preorder and postorder in an edge-weighted digraph
063        public DepthFirstOrder(EdgeWeightedDigraph G) {
064                pre    = new int[G.V()];
065                post   = new int[G.V()];
066                revPost   = new Stack<>();
067                postorder = new Queue<>();
068                preorder  = new Queue<>();
069                marked    = new boolean[G.V()];
070                for (int v = 0; v < G.V(); v++)
071                        if (!marked[v]) dfs(G, v);
072        }
073
074        // run DFS in digraph G from vertex v and compute preorder/postorder
075        private void dfs(Digraph G, int v) {
076                marked[v] = true;
077                pre[v] = preCounter++;
078                preorder.enqueue(v);
079                for (int w : G.adj(v)) {
080                        if (!marked[w]) {
081                                dfs(G, w);
082                        }
083                }
084                postorder.enqueue(v);
085                revPost.push(v);
086                post[v] = postCounter++;
087                return;
088        }
089
090        // run DFS in edge-weighted digraph G from vertex v and compute preorder/postorder
091        private void dfs(EdgeWeightedDigraph G, int v) {
092                marked[v] = true;
093                pre[v] = preCounter++;
094                preorder.enqueue(v);
095                for (DirectedEdge e : G.adj(v)) {
096                        int w = e.to();
097                        if (!marked[w]) {
098                                dfs(G, w);
099                        }
100                }
101                postorder.enqueue(v);
102                revPost.push(v);
103                post[v] = postCounter++;
104        }
105
106        public int pre(int v) {
107                return pre[v];
108        }
109
110        public int post(int v) {
111                return post[v];
112        }
113
114        // return vertices in postorder as an Iterable
115        public Iterable<Integer> post() {
116                return postorder;
117        }
118
119        // return vertices in preorder as an Iterable
120        public Iterable<Integer> pre() {
121                return preorder;
122        }
123
124        // return vertices in reverse postorder as an Iterable
125        public Iterable<Integer> reversePost() {
126                return revPost;
127        }
128
129
130        // check that pre() and post() are consistent with pre(v) and post(v)
131        private boolean check(Digraph G) {
132
133                // check that post(v) is consistent with post()
134                int r = 0;
135                for (int v : post()) {
136                        if (post(v) != r) {
137                                StdOut.println("post(v) and post() inconsistent");
138                                return false;
139                        }
140                        r++;
141                }
142
143                // check that pre(v) is consistent with pre()
144                r = 0;
145                for (int v : pre()) {
146                        if (pre(v) != r) {
147                                StdOut.println("pre(v) and pre() inconsistent");
148                                return false;
149                        }
150                        r++;
151                }
152
153                return true;
154        }
155
156        public static void main(String[] args) {
157                args = new String[] { "data/tinyDG.txt" };
158
159                In in = new In(args[0]);
160                Digraph G = DigraphGenerator.fromIn(in);
161
162                DepthFirstOrder dfs = new DepthFirstOrder(G);
163                StdOut.println("   v  pre post");
164                StdOut.println("--------------");
165                for (int v = 0; v < G.V(); v++) {
166                        StdOut.format("%4d %4d %4d\n", v, dfs.pre(v), dfs.post(v));
167                }
168
169                StdOut.print("Preorder:  ");
170                for (int v : dfs.pre()) {
171                        StdOut.print(v + " ");
172                }
173                StdOut.println();
174
175                StdOut.print("Postorder: ");
176                for (int v : dfs.post()) {
177                        StdOut.print(v + " ");
178                }
179                StdOut.println();
180
181                StdOut.print("Reverse postorder: ");
182                for (int v : dfs.reversePost()) {
183                        StdOut.print(v + " ");
184                }
185                StdOut.println();
186
187
188        }
189
190}