001// Exercise 4.2.3 (Solution published at http://algs4.cs.princeton.edu/)
002package algs42;
003import stdlib.*;
004import algs13.Stack;
005
006import java.util.NoSuchElementException;
007
008import algs13.Bag;
009
010/**
011 *  The {@code Digraph} class represents an directed graph of vertices
012 *  named 0 through V-1.
013 *  It supports the following operations: add an edge to the graph,
014 *  iterate over all of the neighbors incident to a vertex.
015 *  Parallel edges and self-loops are permitted.
016 *  <p>
017 *  For additional documentation,
018 *  see <a href="http://algs4.cs.princeton.edu/52directed">Section 5.2</a> of
019 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
020 */
021public class Digraph {
022        private final int V;
023        private int E;
024        private final Bag<Integer>[] adj;
025    private int[] indegree;
026
027        /**
028         * Create an empty digraph with V vertices.
029         */
030        @SuppressWarnings("unchecked")
031        public Digraph(int V) {
032                if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be nonnegative");
033                this.V = V;
034                this.E = 0;
035        indegree = new int[V];
036                adj = new Bag[V];
037                for (int v = 0; v < V; v++) {
038                        adj[v] = new Bag<>();
039                }
040        }
041
042    /**  
043     * Initializes a digraph from the specified input stream.
044     * The format is the number of vertices <em>V</em>,
045     * followed by the number of edges <em>E</em>,
046     * followed by <em>E</em> pairs of vertices, with each entry separated by whitespace.
047     *
048     * @param  in the input stream
049     * @throws IllegalArgumentException if {@code in} is {@code null}
050     * @throws IllegalArgumentException if the endpoints of any edge are not in prescribed range
051     * @throws IllegalArgumentException if the number of vertices or edges is negative
052     * @throws IllegalArgumentException if the input stream is in the wrong format
053     */
054    @SuppressWarnings("unchecked")
055        public Digraph(In in) {
056        if (in == null) throw new IllegalArgumentException("argument is null");
057        try {
058            this.V = in.readInt();
059            if (V < 0) throw new IllegalArgumentException("number of vertices in a Digraph must be non-negative");
060            indegree = new int[V];
061            adj = (Bag<Integer>[]) new Bag[V];
062            for (int v = 0; v < V; v++) {
063                adj[v] = new Bag<Integer>();
064            }
065            int E = in.readInt();
066            if (E < 0) throw new IllegalArgumentException("number of edges in a Digraph must be non-negative");
067            for (int i = 0; i < E; i++) {
068                int v = in.readInt();
069                int w = in.readInt();
070                addEdge(v, w); 
071            }
072        }
073        catch (NoSuchElementException e) {
074            throw new IllegalArgumentException("invalid input format in Digraph constructor", e);
075        }
076    }
077
078    /**
079     * Initializes a new digraph that is a deep copy of the specified digraph.
080     *
081     * @param  G the digraph to copy
082     * @throws IllegalArgumentException if {@code G} is {@code null}
083     */
084    @SuppressWarnings("unchecked")
085        public Digraph(Digraph G) {
086        if (G == null) throw new IllegalArgumentException("argument is null");
087
088        this.V = G.V();
089        this.E = G.E();
090        if (V < 0) throw new IllegalArgumentException("Number of vertices in a Digraph must be non-negative");
091
092        // update indegrees
093        indegree = new int[V];
094        for (int v = 0; v < V; v++)
095            this.indegree[v] = G.indegree(v);
096
097        // update adjacency lists
098        adj = (Bag<Integer>[]) new Bag[V];
099        for (int v = 0; v < V; v++) {
100            adj[v] = new Bag<Integer>();
101        }
102
103        for (int v = 0; v < G.V(); v++) {
104            // reverse so that adjacency list is in same order as original
105            Stack<Integer> reverse = new Stack<Integer>();
106            for (int w : G.adj[v]) {
107                reverse.push(w);
108            }
109            for (int w : reverse) {
110                adj[v].add(w);
111            }
112        }
113    }
114        /**
115         * Return the number of vertices in the digraph.
116         */
117        public int V() {
118                return V;
119        }
120
121        /**
122         * Return the number of edges in the digraph.
123         */
124        public int E() {
125                return E;
126        }
127
128        /**
129         * Add the directed edge {@code v->w} to the digraph.
130         * @throws java.lang.IndexOutOfBoundsException unless both {@code 0 <= v < V} and {@code 0 <= w < V}
131         */
132        public void addEdge(int v, int w) {
133                if (v < 0 || v >= V) throw new IndexOutOfBoundsException("vertex " + v + " is not between 0 and " + (V-1));
134                if (w < 0 || w >= V) throw new IndexOutOfBoundsException("vertex " + w + " is not between 0 and " + (V-1));
135                adj[v].add(w);
136        indegree[w]++;
137                E++;
138        }
139
140        /**
141         * Return the list of vertices pointed to from vertex v as an Iterable.
142         * @throws java.lang.IndexOutOfBoundsException unless {@code 0 <= v < V}
143         */
144        public Iterable<Integer> adj(int v) {
145                if (v < 0 || v >= V) throw new IndexOutOfBoundsException();
146                return adj[v];
147        }
148
149    /**
150     * Returns the number of directed edges incident from vertex {@code v}.
151     * This is known as the <em>outdegree</em> of vertex {@code v}.
152     *
153     * @param  v the vertex
154     * @return the outdegree of vertex {@code v}               
155     * @throws IllegalArgumentException unless {@code {@code 0 <= v < V}}
156     */
157    public int outdegree(int v) {
158                if (v < 0 || v >= V) throw new IndexOutOfBoundsException();
159        return adj[v].size();
160    }
161
162    /**
163     * Returns the number of directed edges incident to vertex {@code v}.
164     * This is known as the <em>indegree</em> of vertex {@code v}.
165     *
166     * @param  v the vertex
167     * @return the indegree of vertex {@code v}               
168     * @throws IllegalArgumentException unless {@code 0 <= v < V}
169     */
170    public int indegree(int v) {
171                if (v < 0 || v >= V) throw new IndexOutOfBoundsException();
172        return indegree[v];
173    }
174        /**
175         * Return the reverse of the digraph.
176         */
177        public Digraph reverse() {
178                Digraph R = new Digraph(V);
179                for (int v = 0; v < V; v++) {
180                        for (int w : adj(v)) {
181                                R.addEdge(w, v);
182                        }
183                }
184                return R;
185        }
186
187        /**
188         * Return a string representation of the digraph.
189         */
190        public String toString() {
191                StringBuilder s = new StringBuilder();
192                String NEWLINE = System.getProperty("line.separator");
193                s.append(V + " vertices, " + E + " edges " + NEWLINE);
194                for (int v = 0; v < V; v++) {
195                        s.append(String.format("%d: ", v));
196                        for (int w : adj[v]) {
197                                s.append(String.format("%d ", w));
198                        }
199                        s.append(NEWLINE);
200                }
201                return s.toString();
202        }
203
204        /**
205         * Save a graphviz representation of the graph.
206         * See <a href="http://www.graphviz.org/">graphviz.org</a>.
207         */
208        public void toGraphviz(String filename) {
209                GraphvizBuilder gb = new GraphvizBuilder ();
210                for (int v = 0; v < V; v++) {
211                        gb.addNode (v);
212                        for (int w : adj[v])
213                                gb.addEdge (v, w);
214                }
215                gb.toFile (filename);
216        }
217
218        /**
219         * Test client.
220         */
221        public static void main(String[] args) {
222                //args = new String[] { "data/mediumDG.txt" };
223                args = new String[] { "data/tinyDG.txt" };
224                //args = new String[] { "data/tinyDGeuler1.txt" };
225                //args = new String[] { "data/tinyDGeuler2.txt" };
226                //args = new String[] { "data/tinyDGeuler3.txt" };
227                //args = new String[] { "data/tinyDGeuler4.txt" };
228                //args = new String[] { "data/tinyDGeuler5.txt" };
229                //args = new String[] { "data/tinyDGeuler6.txt" };
230                //args = new String[] { "data/tinyDGex2.txt" };
231                //args = new String [] { "10", "20" };
232
233                Digraph G;
234                if (args.length == 1) {
235                        In in = new In(args[0]);
236                        G = DigraphGenerator.fromIn(in);
237                } else {
238                        int V = Integer.parseInt (args[0]);
239                        int E = Integer.parseInt (args[1]);
240                        G = DigraphGenerator.simple(V, E);
241                }
242                StdOut.println(G);
243                G.toGraphviz ("g.png");
244        }
245
246}