001package algs42;
002import algs35.SET;
003import algs13.Stack;
004import  stdlib.*;
005
006/*************************************************************************
007 *  Compilation:  javac DigraphGenerator.java
008 *  Execution:    java DigraphGenerator V E
009 *  Dependencies: Digraph.java
010 *
011 *  A digraph generator.
012 *
013 *************************************************************************/
014
015/**
016 *  The {@code DigraphGenerator} class provides static methods for creating
017 *  various digraphs, including Erdos-Renyi random digraphs, random DAGs,
018 *  random rooted trees, random rooted DAGs, random tournaments, path digraphs,
019 *  cycle digraphs, and the complete digraph.
020 *  <p>
021 *  For additional documentation, see <a href="http://algs4.cs.princeton.edu/42digraph">Section 4.2</a> of
022 *  <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
023 *
024 *  @author Robert Sedgewick
025 *  @author Kevin Wayne
026 */
027public class DigraphGenerator {
028        private static class Edge implements Comparable<Edge> {
029                private int v;
030                private int w;
031                private Edge(int v, int w) {
032                        this.v = v;
033                        this.w = w;
034                }
035                public int compareTo(Edge that) {
036                        if (this.v < that.v) return -1;
037                        if (this.v > that.v) return +1;
038                        if (this.w < that.w) return -1;
039                        if (this.w > that.w) return +1;
040                        return 0;
041                }
042        }
043
044        public static Digraph fromIn(In in) {
045                Digraph G = new Digraph (in.readInt());
046                int E = in.readInt();
047                if (E < 0) throw new IllegalArgumentException("Number of edges in a Digraph must be nonnegative");
048                for (int i = 0; i < E; i++) {
049                        int v = in.readInt();
050                        int w = in.readInt();
051                        G.addEdge(v, w);
052                }
053                return G;
054        }
055        public static Digraph copy (Digraph G) {
056                Digraph R = new Digraph (G.V());
057        for (int v = 0; v < G.V(); v++) {
058            // reverse so that adjacency list is in same order as original
059            Stack<Integer> reverse = new Stack<Integer>();
060            for (int w : G.adj(v)) {
061                reverse.push(w);
062            }
063            for (int w : reverse) {
064                R.addEdge (v, w);
065            }
066        }
067                return R;
068        }
069        /**
070         * Create a random digraph with V vertices and E edges.
071         * Expected running time is proportional to V + E.
072         */
073        public static Digraph random(int V, int E) {
074                if (E < 0) throw new Error("Number of edges must be nonnegative");
075                Digraph G = new Digraph(V);
076
077                for (int i = 0; i < E; i++) {
078                        int v = (int) (Math.random() * V);
079                        int w = (int) (Math.random() * V);
080                        G.addEdge(v, w);
081                }
082                return G;
083        }
084        /**
085         * Returns a random simple digraph containing {@code V} vertices and {@code E} edges.
086         * @param V the number of vertices
087         * @param E the number of vertices
088         * @return a random simple digraph on {@code V} vertices, containing a total
089         *     of {@code E} edges
090         * @throws IllegalArgumentException if no such simple digraph exists
091         */
092        public static Digraph simple(int V, int E) {
093                if (E > (long) V*(V-1)) throw new IllegalArgumentException("Too many edges");
094                if (E < 0)              throw new IllegalArgumentException("Too few edges");
095                Digraph G = new Digraph(V);
096                SET<Edge> set = new SET<>();
097                while (G.E() < E) {
098                        int v = StdRandom.uniform(V);
099                        int w = StdRandom.uniform(V);
100                        Edge e = new Edge(v, w);
101                        if ((v != w) && !set.contains(e)) {
102                                set.add(e);
103                                G.addEdge(v, w);
104                        }
105                }
106                return G;
107        }
108
109        /**
110         * Returns a random simple digraph on {@code V} vertices, with an
111         * edge between any two vertices with probability {@code p}. This is sometimes
112         * referred to as the Erdos-Renyi random digraph model.
113         * This implementations takes time propotional to V^2 (even if {@code p} is small).
114         * @param V the number of vertices
115         * @param p the probability of choosing an edge
116         * @return a random simple digraph on {@code V} vertices, with an edge between
117         *     any two vertices with probability {@code p}
118         * @throws IllegalArgumentException if probability is not between 0 and 1
119         */
120        public static Digraph simple(int V, double p) {
121                if (p < 0.0 || p > 1.0)
122                        throw new IllegalArgumentException("Probability must be between 0 and 1");
123                Digraph G = new Digraph(V);
124                for (int v = 0; v < V; v++)
125                        for (int w = 0; w < V; w++)
126                                if (v != w)
127                                        if (StdRandom.bernoulli(p))
128                                                G.addEdge(v, w);
129                return G;
130        }
131
132        /**
133         * Returns the complete digraph on {@code V} vertices.
134         * @param V the number of vertices
135         * @return the complete digraph on {@code V} vertices
136         */
137        public static Digraph complete(int V) {
138                return simple(V, V*(V-1));
139        }
140
141        /**
142         * Returns a random simple DAG containing {@code V} vertices and {@code E} edges.
143         * Note: it is not uniformly selected at random among all such DAGs.
144         * @param V the number of vertices
145         * @param E the number of vertices
146         * @return a random simple DAG on {@code V} vertices, containing a total
147         *     of {@code E} edges
148         * @throws IllegalArgumentException if no such simple DAG exists
149         */
150        public static Digraph dag(int V, int E) {
151                if (E > (long) V*(V-1) / 2) throw new IllegalArgumentException("Too many edges");
152                if (E < 0)                  throw new IllegalArgumentException("Too few edges");
153                Digraph G = new Digraph(V);
154                SET<Edge> set = new SET<>();
155                int[] vertices = new int[V];
156                for (int i = 0; i < V; i++) vertices[i] = i;
157                StdRandom.shuffle(vertices);
158                while (G.E() < E) {
159                        int v = StdRandom.uniform(V);
160                        int w = StdRandom.uniform(V);
161                        Edge e = new Edge(v, w);
162                        if ((v < w) && !set.contains(e)) {
163                                set.add(e);
164                                G.addEdge(vertices[v], vertices[w]);
165                        }
166                }
167                return G;
168        }
169
170        /**
171         * Returns a random tournament digraph on {@code V} vertices. A tournament digraph
172         * is a DAG in which for every two vertices, there is one directed edge.
173         * A tournament is an oriented complete graph.
174         * @param V the number of vertices
175         * @return a random tournament digraph on {@code V} vertices
176         */
177        public static Digraph tournament(int V) {
178                return dag(V, V*(V-1)/2);
179        }
180
181        /**
182         * Returns a random rooted-in DAG on {@code V} vertices and {@code E} edges.
183         * A rooted in-tree is a DAG in which there is a single vertex
184         * reachable from every other vertex.
185         * The DAG returned is not chosen uniformly at random among all such DAGs.
186         * @param V the number of vertices
187         * @param E the number of edges
188         * @return a random rooted-in DAG on {@code V} vertices and {@code E} edges
189         */
190        public static Digraph rootedInDAG(int V, int E) {
191                if (E > (long) V*(V-1) / 2) throw new IllegalArgumentException("Too many edges");
192                if (E < V-1)                throw new IllegalArgumentException("Too few edges");
193                Digraph G = new Digraph(V);
194                SET<Edge> set = new SET<>();
195
196                // fix a topological order
197                int[] vertices = new int[V];
198                for (int i = 0; i < V; i++) vertices[i] = i;
199                StdRandom.shuffle(vertices);
200
201                // one edge pointing from each vertex, other than the root = vertices[V-1]
202                for (int v = 0; v < V-1; v++) {
203                        int w = StdRandom.uniform(v+1, V);
204                        Edge e = new Edge(v, w);
205                        set.add(e);
206                        G.addEdge(vertices[v], vertices[w]);
207                }
208
209                while (G.E() < E) {
210                        int v = StdRandom.uniform(V);
211                        int w = StdRandom.uniform(V);
212                        Edge e = new Edge(v, w);
213                        if ((v < w) && !set.contains(e)) {
214                                set.add(e);
215                                G.addEdge(vertices[v], vertices[w]);
216                        }
217                }
218                return G;
219        }
220
221        /**
222         * Returns a random rooted-out DAG on {@code V} vertices and {@code E} edges.
223         * A rooted out-tree is a DAG in which every vertex is reachable from a
224         * single vertex.
225         * The DAG returned is not chosen uniformly at random among all such DAGs.
226         * @param V the number of vertices
227         * @param E the number of edges
228         * @return a random rooted-out DAG on {@code V} vertices and {@code E} edges
229         */
230        public static Digraph rootedOutDAG(int V, int E) {
231                if (E > (long) V*(V-1) / 2) throw new IllegalArgumentException("Too many edges");
232                if (E < V-1)                throw new IllegalArgumentException("Too few edges");
233                Digraph G = new Digraph(V);
234                SET<Edge> set = new SET<>();
235
236                // fix a topological order
237                int[] vertices = new int[V];
238                for (int i = 0; i < V; i++) vertices[i] = i;
239                StdRandom.shuffle(vertices);
240
241                // one edge pointing from each vertex, other than the root = vertices[V-1]
242                for (int v = 0; v < V-1; v++) {
243                        int w = StdRandom.uniform(v+1, V);
244                        Edge e = new Edge(w, v);
245                        set.add(e);
246                        G.addEdge(vertices[w], vertices[v]);
247                }
248
249                while (G.E() < E) {
250                        int v = StdRandom.uniform(V);
251                        int w = StdRandom.uniform(V);
252                        Edge e = new Edge(w, v);
253                        if ((v < w) && !set.contains(e)) {
254                                set.add(e);
255                                G.addEdge(vertices[w], vertices[v]);
256                        }
257                }
258                return G;
259        }
260
261        /**
262         * Returns a random rooted-in tree on {@code V} vertices.
263         * A rooted in-tree is an oriented tree in which there is a single vertex
264         * reachable from every other vertex.
265         * The tree returned is not chosen uniformly at random among all such trees.
266         * @param V the number of vertices
267         * @return a random rooted-in tree on {@code V} vertices
268         */
269        public static Digraph rootedInTree(int V) {
270                return rootedInDAG(V, V-1);
271        }
272
273        /**
274         * Returns a random rooted-out tree on {@code V} vertices. A rooted out-tree
275         * is an oriented tree in which each vertex is reachable from a single vertex.
276         * It is also known as a <em>arborescence</em> or <em>branching</em>.
277         * The tree returned is not chosen uniformly at random among all such trees.
278         * @param V the number of vertices
279         * @return a random rooted-out tree on {@code V} vertices
280         */
281        public static Digraph rootedOutTree(int V) {
282                return rootedOutDAG(V, V-1);
283        }
284
285        /**
286         * Returns a path digraph on {@code V} vertices.
287         * @param V the number of vertices in the path
288         * @return a digraph that is a directed path on {@code V} vertices
289         */
290        public static Digraph path(int V) {
291                Digraph G = new Digraph(V);
292                int[] vertices = new int[V];
293                for (int i = 0; i < V; i++) vertices[i] = i;
294                StdRandom.shuffle(vertices);
295                for (int i = 0; i < V-1; i++) {
296                        G.addEdge(vertices[i], vertices[i+1]);
297                }
298                return G;
299        }
300
301        /**
302         * Returns a complete binary tree digraph on {@code V} vertices.
303         * @param V the number of vertices in the binary tree
304         * @return a digraph that is a complete binary tree on {@code V} vertices
305         */
306        public static Digraph binaryTree(int V) {
307                Digraph G = new Digraph(V);
308                int[] vertices = new int[V];
309                for (int i = 0; i < V; i++) vertices[i] = i;
310                StdRandom.shuffle(vertices);
311                for (int i = 1; i < V; i++) {
312                        G.addEdge(vertices[i], vertices[(i-1)/2]);
313                }
314                return G;
315        }
316
317        /**
318         * Returns a cycle digraph on {@code V} vertices.
319         * @param V the number of vertices in the cycle
320         * @return a digraph that is a directed cycle on {@code V} vertices
321         */
322        public static Digraph cycle(int V) {
323                Digraph G = new Digraph(V);
324                int[] vertices = new int[V];
325                for (int i = 0; i < V; i++) vertices[i] = i;
326                StdRandom.shuffle(vertices);
327                for (int i = 0; i < V-1; i++) {
328                        G.addEdge(vertices[i], vertices[i+1]);
329                }
330                G.addEdge(vertices[V-1], vertices[0]);
331                return G;
332        }
333        
334    /**
335     * Returns an Eulerian cycle digraph on {@code V} vertices.
336     *
337     * @param  V the number of vertices in the cycle
338     * @param  E the number of edges in the cycle
339     * @return a digraph that is a directed Eulerian cycle on {@code V} vertices
340     *         and {@code E} edges
341     * @throws IllegalArgumentException if either {@code V <= 0} or {@code E <= 0}
342     */
343    public static Digraph eulerianCycle(int V, int E) {
344        if (E <= 0)
345            throw new IllegalArgumentException("An Eulerian cycle must have at least one edge");
346        if (V <= 0)
347            throw new IllegalArgumentException("An Eulerian cycle must have at least one vertex");
348        Digraph G = new Digraph(V);
349        int[] vertices = new int[E];
350        for (int i = 0; i < E; i++)
351            vertices[i] = StdRandom.uniform(V);
352        for (int i = 0; i < E-1; i++) {
353            G.addEdge(vertices[i], vertices[i+1]);
354        }
355        G.addEdge(vertices[E-1], vertices[0]);
356        return G;
357    }
358
359    /**
360     * Returns an Eulerian path digraph on {@code V} vertices.
361     *
362     * @param  V the number of vertices in the path
363     * @param  E the number of edges in the path
364     * @return a digraph that is a directed Eulerian path on {@code V} vertices
365     *         and {@code E} edges
366     * @throws IllegalArgumentException if either {@code V <= 0} or {@code E < 0}
367     */
368    public static Digraph eulerianPath(int V, int E) {
369        if (E < 0)
370            throw new IllegalArgumentException("negative number of edges");
371        if (V <= 0)
372            throw new IllegalArgumentException("An Eulerian path must have at least one vertex");
373        Digraph G = new Digraph(V);
374        int[] vertices = new int[E+1];
375        for (int i = 0; i < E+1; i++)
376            vertices[i] = StdRandom.uniform(V);
377        for (int i = 0; i < E; i++) {
378            G.addEdge(vertices[i], vertices[i+1]);
379        }
380        return G;
381    }
382
383
384        /**
385         * Returns a random simple digraph on {@code V} vertices, {@code E}
386         * edges and (at most) {@code c} strong components. The vertices are randomly
387         * assigned integer labels between  {@code 0} and {@code c-1} (corresponding to
388         * strong components). Then, a strong component is created among the vertices
389         * with the same label. Next, random edges (either between two vertices with
390         * the same labels or from a vertex with a smaller label to a vertex with a
391         * larger label). The number of components will be equal to the number of
392         * distinct labels that are assigned to vertices.
393         *
394         * @param V the number of vertices
395         * @param E the number of edges
396         * @param c the (maximum) number of strong components
397         * @return a random simple digraph on {@code V} vertices and
398               {@code E} edges, with (at most) {@code c} strong components
399         * @throws IllegalArgumentException if {@code c} is larger than {@code V}
400         */
401        public static Digraph strong(int V, int E, int c) {
402                if (c >= V || c <= 0)
403                        throw new IllegalArgumentException("Number of components must be between 1 and V");
404                if (E <= 2*(V-c))
405                        throw new IllegalArgumentException("Number of edges must be at least 2(V-c)");
406                if (E > (long) V*(V-1) / 2)
407                        throw new IllegalArgumentException("Too many edges");
408
409                // the digraph
410                Digraph G = new Digraph(V);
411
412                // edges added to G (to avoid duplicate edges)
413                SET<Edge> set = new SET<>();
414
415                int[] label = new int[V];
416                for (int v = 0; v < V; v++)
417                        label[v] = StdRandom.uniform(c);
418
419                // make all vertices with label c a strong component by
420                // combining a rooted in-tree and a rooted out-tree
421                for (int i = 0; i < c; i++) {
422                        // how many vertices in component c
423                        int count = 0;
424                        for (int v = 0; v < G.V(); v++) {
425                                if (label[v] == i) count++;
426                        }
427
428                        // if (count == 0) System.err.println("less than desired number of strong components");
429
430                        int[] vertices = new int[count];
431                        int j = 0;
432                        for (int v = 0; v < V; v++) {
433                                if (label[v] == i) vertices[j++] = v;
434                        }
435                        StdRandom.shuffle(vertices);
436
437                        // rooted-in tree with root = vertices[count-1]
438                        for (int v = 0; v < count-1; v++) {
439                                int w = StdRandom.uniform(v+1, count);
440                                Edge e = new Edge(w, v);
441                                set.add(e);
442                                G.addEdge(vertices[w], vertices[v]);
443                        }
444
445                        // rooted-out tree with root = vertices[count-1]
446                        for (int v = 0; v < count-1; v++) {
447                                int w = StdRandom.uniform(v+1, count);
448                                Edge e = new Edge(v, w);
449                                set.add(e);
450                                G.addEdge(vertices[v], vertices[w]);
451                        }
452                }
453
454                while (G.E() < E) {
455                        int v = StdRandom.uniform(V);
456                        int w = StdRandom.uniform(V);
457                        Edge e = new Edge(v, w);
458                        if (!set.contains(e) && v != w && label[v] <= label[w]) {
459                                set.add(e);
460                                G.addEdge(v, w);
461                        }
462                }
463
464                return G;
465        }
466
467        /**
468         * Unit tests the {@code DigraphGenerator} library.
469         */
470        private static void print (Digraph G, String filename) {
471                System.out.println(filename);
472                System.out.println(G);
473                System.out.println();
474                G.toGraphviz (filename + ".png");
475        }
476        public static void main(String[] args) {
477                args = new String [] { "6", "10", "0.25", "3" };
478
479                int V = Integer.parseInt(args[0]);
480                int E = Integer.parseInt(args[1]);
481                double p = Double.parseDouble (args[2]);
482                int c = Integer.parseInt(args[3]);
483
484                for (int i=5; i>0; i--) {
485                        print(DigraphGenerator.random(V,E), "random-" + V + "-" + E);
486                        print(DigraphGenerator.simple(V,E), "simpleA-" + V + "-" + E);
487                        print(DigraphGenerator.simple(V,p), "simpleB-" + V + "-" + p);
488                        print(DigraphGenerator.complete(V), "complete-" + V);
489                        print(DigraphGenerator.dag(V,E), "dag-" + V + "-" + E);
490                        print(DigraphGenerator.tournament(V), "tournament-" + V);
491                        print(DigraphGenerator.rootedInDAG(V,E), "rootedInDAG-" + V + "-" + E);
492                        print(DigraphGenerator.rootedOutDAG(V,E), "rootedOutDAG-" + V + "-" + E);
493                        print(DigraphGenerator.rootedInTree(V), "rootedInTree-" + V);
494                        print(DigraphGenerator.rootedOutTree(V), "rootedOutTree-" + V);
495                        print(DigraphGenerator.path(V), "path-" + V);
496                        print(DigraphGenerator.binaryTree(V), "rootedInTreeBinary-" + V);
497                        print(DigraphGenerator.cycle(V), "cycle-" + V);
498                        if (E <= 2*(V-c)) E = 2*(V-c)+1;
499                        print(DigraphGenerator.strong(V,E,c), "strong-" + V + "-" + E + "-" + c);
500                }
501        }
502}