Source code

001package algs41;
002
003import java.util.Arrays;
004import algs13.Stack;
005import algs24.MinPQ;
006import stdlib.*;
007
008public class GraphGenerator {
009
010        /**
011         * Create a graph from input stream.
012         */
013        public static Graph fromIn (In in) {
014                Graph G = new Graph (in.readInt());
015                int E = in.readInt();
016                for (int i = 0; i < E; i++) {
017                        int v = in.readInt();
018                        int w = in.readInt();
019                        G.addEdge(v, w);
020                }
021                return G;
022        }
023        public static Graph copy (Graph G) {
024                Graph R = new Graph (G.V());
025        for (int v = 0; v < G.V(); v++) {
026            // reverse so that adjacency list is in same order as original
027            Stack<Integer> reverse = new Stack<Integer>();
028            for (int w : G.adj(v)) {
029                reverse.push(w);
030            }
031            for (int w : reverse) {
032                R.addEdge (v, w);
033            }
034        }
035                return R;
036        }
037        public static Graph complete (int V) {
038                return simple (V, V * (V - 1) / 2);
039        }
040        public static Graph simple (int V, int E) {
041                if (V < 0 || E < 0) throw new IllegalArgumentException ();
042                if (E > V * (V - 1) / 2) throw new IllegalArgumentException ("Number of edges must be less than V*(V-1)/2");
043                Graph G = new Graph (V);
044                newEdge: while (E > 0) {
045                        int v = StdRandom.uniform (V);
046                        int w = StdRandom.uniform (V);
047                        if (v == w) continue;
048                        for (int w2 : G.adj (v))
049                                if (w == w2) continue newEdge;
050                        G.addEdge (v, w);
051                        E--;
052                }
053                return G;
054        }
055        public static Graph simpleConnected (int V, int E) {
056                if (V < 0 || E < 0) throw new IllegalArgumentException ();
057                if (E > V * (V - 1) / 2) throw new IllegalArgumentException ("Number of edges must be less than V*(V-1)/2");
058                Graph G = spanningTree (V);
059                newEdge: while (G.E () < E) {
060                        int v = StdRandom.uniform (V);
061                        int w = StdRandom.uniform (V);
062                        if (v == w) continue;
063                        for (int w2 : G.adj (v))
064                                if (w == w2) continue newEdge;
065                        G.addEdge (v, w);
066                        E--;
067                }
068                return G;
069        }
070        public static Graph connected (int V, int E) {
071                if (V < 0 || E < 0) throw new IllegalArgumentException ();
072                Graph G = spanningTree (V);
073                while (G.E () < E) {
074                        int v = StdRandom.uniform (V);
075                        int w = StdRandom.uniform (V);
076                        G.addEdge (v, w);
077                }
078                return G;
079        }
080        public static Graph random (int V, int E) {
081                if (V < 0 || E < 0) throw new IllegalArgumentException ();
082                Graph G = new Graph (V);
083                while (G.E () < E) {
084                        int v = StdRandom.uniform (V);
085                        int w = StdRandom.uniform (V);
086                        G.addEdge (v, w);
087                }
088                return G;
089        }
090        public static Graph spanningTree (int V) {
091                if (V < 1) throw new IllegalArgumentException ();
092                int[] vertices = new int[V];
093                for (int i = 0; i < V; i++)
094                        vertices[i] = i;
095                StdRandom.shuffle (vertices);
096                Graph G = new Graph (V);
097                for (int i = 1; i < V; i++) {
098                        int v = vertices[StdRandom.uniform (i)];
099                        int w = vertices[i];
100                        G.addEdge (v, w);
101                }
102                return G;
103        }
104
105        public static Graph connected(int V, int E, int c) {
106                if (c >= V || c <= 0)
107                        throw new IllegalArgumentException("Number of components must be between 1 and V");
108                if (E <= (V-c))
109                        throw new IllegalArgumentException("Number of edges must be at least (V-c)");
110                if (E > V * (V - 1) / 2)
111                        throw new IllegalArgumentException("Too many edges");
112
113                int[] label = new int[V];
114                for (int v = 0; v < V; v++) {
115                        label[v] = StdRandom.uniform(c);
116                }
117                // The following hack ensures that each color appears at least once
118                {
119                        Arrays.sort (label);
120                        label[0] = 0;
121                        for (int v = 1; v < V; v++) {
122                                if (label[v]-label[v-1] > 1 || V-v == c-label[v-1]-1)
123                                        label[v] = label[v-1]+1;
124                        }
125                        StdRandom.shuffle (label);
126                }
127
128                // make all vertices with label c a connected component
129                Graph G = new Graph(V);
130                for (int i = 0; i < c; i++) {
131                        // how many vertices in component c
132                        int count = 0;
133                        for (int v = 0; v < V; v++) {
134                                if (label[v] == i) count++;
135                        }
136                        int[] vertices = new int[count];
137                        {
138                                int j = 0;
139                                for (int v = 0; v < V; v++)
140                                        if (label[v] == i) vertices[j++] = v;
141                        }
142                        StdRandom.shuffle(vertices);
143
144                        for (int j = 1; j < count; j++) {
145                                int v = vertices[StdRandom.uniform (j)];
146                                int w = vertices[j];
147                                G.addEdge (v, w);
148                        }
149                }
150
151                while (G.E() < E) {
152                        int v = StdRandom.uniform(V);
153                        int w = StdRandom.uniform(V);
154                        if (v != w && label[v] == label[w]) {
155                                G.addEdge(v, w);
156                        }
157                }
158
159                return G;
160        }
161    /**
162     * Returns a random simple bipartite graph on {@code V1} and {@code V2} vertices,
163     * containing each possible edge with probability {@code p}.
164     * @param V1 the number of vertices in one partition
165     * @param V2 the number of vertices in the other partition
166     * @param p the probability that the graph contains an edge with one endpoint in either side
167     * @return a random simple bipartite graph on {@code V1} and {@code V2} vertices,
168     *    containing each possible edge with probability {@code p}
169     * @throws IllegalArgumentException if probability is not between 0 and 1
170     */
171    public static Graph bipartite(int V1, int V2, double p) {
172        if (p < 0.0 || p > 1.0)
173            throw new IllegalArgumentException("Probability must be between 0 and 1");
174        int[] vertices = new int[V1 + V2];
175        for (int i = 0; i < V1 + V2; i++)
176            vertices[i] = i;
177        StdRandom.shuffle(vertices);
178        Graph G = new Graph(V1 + V2);
179        for (int i = 0; i < V1; i++)
180            for (int j = 0; j < V2; j++)
181                if (StdRandom.bernoulli(p))
182                    G.addEdge(vertices[i], vertices[V1+j]);
183        return G;
184    }
185
186    /**
187     * Returns a path graph on {@code V} vertices.
188     * @param V the number of vertices in the path
189     * @return a path graph on {@code V} vertices
190     */
191    public static Graph path(int V) {
192        Graph G = new Graph(V);
193        int[] vertices = new int[V];
194        for (int i = 0; i < V; i++)
195            vertices[i] = i;
196        StdRandom.shuffle(vertices);
197        for (int i = 0; i < V-1; i++) {
198            G.addEdge(vertices[i], vertices[i+1]);
199        }
200        return G;
201    }
202
203    /**
204     * Returns a complete binary tree graph on {@code V} vertices.
205     * @param V the number of vertices in the binary tree
206     * @return a complete binary tree graph on {@code V} vertices
207     */
208    public static Graph binaryTree(int V) {
209        Graph G = new Graph(V);
210        int[] vertices = new int[V];
211        for (int i = 0; i < V; i++)
212            vertices[i] = i;
213        StdRandom.shuffle(vertices);
214        for (int i = 1; i < V; i++) {
215            G.addEdge(vertices[i], vertices[(i-1)/2]);
216        }
217        return G;
218    }
219
220    /**
221     * Returns a cycle graph on {@code V} vertices.
222     * @param V the number of vertices in the cycle
223     * @return a cycle graph on {@code V} vertices
224     */
225    public static Graph cycle(int V) {
226        Graph G = new Graph(V);
227        int[] vertices = new int[V];
228        for (int i = 0; i < V; i++)
229            vertices[i] = i;
230        StdRandom.shuffle(vertices);
231        for (int i = 0; i < V-1; i++) {
232            G.addEdge(vertices[i], vertices[i+1]);
233        }
234        G.addEdge(vertices[V-1], vertices[0]);
235        return G;
236    }
237
238    /**
239     * Returns an Eulerian cycle graph on {@code V} vertices.
240     *
241     * @param  V the number of vertices in the cycle
242     * @param  E the number of edges in the cycle
243     * @return a graph that is an Eulerian cycle on {@code V} vertices
244     *         and {@code E} edges
245     * @throws IllegalArgumentException if either {@code V <= 0} or {@code E <= 0}
246     */
247    public static Graph eulerianCycle(int V, int E) {
248        if (E <= 0)
249            throw new IllegalArgumentException("An Eulerian cycle must have at least one edge");
250        if (V <= 0)
251            throw new IllegalArgumentException("An Eulerian cycle must have at least one vertex");
252        Graph G = new Graph(V);
253        int[] vertices = new int[E];
254        for (int i = 0; i < E; i++)
255            vertices[i] = StdRandom.uniform(V);
256        for (int i = 0; i < E-1; i++) {
257            G.addEdge(vertices[i], vertices[i+1]);
258        }
259        G.addEdge(vertices[E-1], vertices[0]);
260        return G;
261    }
262
263    /**
264     * Returns an Eulerian path graph on {@code V} vertices.
265     *
266     * @param  V the number of vertices in the path
267     * @param  E the number of edges in the path
268     * @return a graph that is an Eulerian path on {@code V} vertices
269     *         and {@code E} edges
270     * @throws IllegalArgumentException if either {@code V <= 0} or {@code E < 0}
271     */
272    public static Graph eulerianPath(int V, int E) {
273        if (E < 0)
274            throw new IllegalArgumentException("negative number of edges");
275        if (V <= 0)
276            throw new IllegalArgumentException("An Eulerian path must have at least one vertex");
277        Graph G = new Graph(V);
278        int[] vertices = new int[E+1];
279        for (int i = 0; i < E+1; i++)
280            vertices[i] = StdRandom.uniform(V);
281        for (int i = 0; i < E; i++) {
282            G.addEdge(vertices[i], vertices[i+1]);
283        }
284        return G;
285    }
286
287    /**
288     * Returns a wheel graph on {@code V} vertices.
289     * @param V the number of vertices in the wheel
290     * @return a wheel graph on {@code V} vertices: a single vertex connected to
291     *     every vertex in a cycle on {@code V-1} vertices
292     */
293    public static Graph wheel(int V) {
294        if (V <= 1) throw new IllegalArgumentException("Number of vertices must be at least 2");
295        Graph G = new Graph(V);
296        int[] vertices = new int[V];
297        for (int i = 0; i < V; i++)
298            vertices[i] = i;
299        StdRandom.shuffle(vertices);
300
301        // simple cycle on V-1 vertices
302        for (int i = 1; i < V-1; i++) {
303            G.addEdge(vertices[i], vertices[i+1]);
304        }
305        G.addEdge(vertices[V-1], vertices[1]);
306
307        // connect vertices[0] to every vertex on cycle
308        for (int i = 1; i < V; i++) {
309            G.addEdge(vertices[0], vertices[i]);
310        }
311
312        return G;
313    }
314
315    /**
316     * Returns a star graph on {@code V} vertices.
317     * @param V the number of vertices in the star
318     * @return a star graph on {@code V} vertices: a single vertex connected to
319     *     every other vertex
320     */
321    public static Graph star(int V) {
322        if (V <= 0) throw new IllegalArgumentException("Number of vertices must be at least 1");
323        Graph G = new Graph(V);
324        int[] vertices = new int[V];
325        for (int i = 0; i < V; i++)
326            vertices[i] = i;
327        StdRandom.shuffle(vertices);
328
329        // connect vertices[0] to every other vertex
330        for (int i = 1; i < V; i++) {
331            G.addEdge(vertices[0], vertices[i]);
332        }
333
334        return G;
335    }
336
337    /**
338     * Returns a uniformly random {@code k}-regular graph on {@code V} vertices
339     * (not necessarily simple). The graph is simple with probability only about e^(-k^2/4),
340     * which is tiny when k = 14.
341     *
342     * @param V the number of vertices in the graph
343     * @param k degree of each vertex
344     * @return a uniformly random {@code k}-regular graph on {@code V} vertices.
345     */
346    public static Graph regular(int V, int k) {
347        if (V*k % 2 != 0) throw new IllegalArgumentException("Number of vertices * k must be even");
348        Graph G = new Graph(V);
349
350        // create k copies of each vertex
351        int[] vertices = new int[V*k];
352        for (int v = 0; v < V; v++) {
353            for (int j = 0; j < k; j++) {
354                vertices[v + V*j] = v;
355            }
356        }
357
358        // pick a random perfect matching
359        StdRandom.shuffle(vertices);
360        for (int i = 0; i < V*k/2; i++) {
361            G.addEdge(vertices[2*i], vertices[2*i + 1]);
362        }
363        return G;
364    }
365
366    // http://www.proofwiki.org/wiki/Labeled_Tree_from_Prüfer_Sequence
367    // http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.36.6484&rep=rep1&type=pdf
368    /**
369     * Returns a uniformly random tree on {@code V} vertices.
370     * This algorithm uses a Prufer sequence and takes time proportional to <em>V log V</em>.
371     * @param V the number of vertices in the tree
372     * @return a uniformly random tree on {@code V} vertices
373     */
374    public static Graph tree(int V) {
375        Graph G = new Graph(V);
376
377        // special case
378        if (V == 1) return G;
379
380        // Cayley's theorem: there are V^(V-2) labeled trees on V vertices
381        // Prufer sequence: sequence of V-2 values between 0 and V-1
382        // Prufer's proof of Cayley's theorem: Prufer sequences are in 1-1
383        // with labeled trees on V vertices
384        int[] prufer = new int[V-2];
385        for (int i = 0; i < V-2; i++)
386            prufer[i] = StdRandom.uniform(V);
387
388        // degree of vertex v = 1 + number of times it appers in Prufer sequence
389        int[] degree = new int[V];
390        for (int v = 0; v < V; v++)
391            degree[v] = 1;
392        for (int i = 0; i < V-2; i++)
393            degree[prufer[i]]++;
394
395        // pq contains all vertices of degree 1
396        MinPQ<Integer> pq = new MinPQ<Integer>();
397        for (int v = 0; v < V; v++)
398            if (degree[v] == 1) pq.insert(v);
399
400        // repeatedly delMin() degree 1 vertex that has the minimum index
401        for (int i = 0; i < V-2; i++) {
402            int v = pq.delMin();
403            G.addEdge(v, prufer[i]);
404            degree[v]--;
405            degree[prufer[i]]--;
406            if (degree[prufer[i]] == 1) pq.insert(prufer[i]);
407        }
408        G.addEdge(pq.delMin(), pq.delMin());
409        return G;
410    }
411
412        public static void print (Graph G, String filename) {
413                if (G == null) return;
414                System.out.println (filename);
415                System.out.println (G);
416                System.out.println ();
417                G.toGraphviz (filename + ".png");
418        }
419        
420        public static void main (String[] args) {
421                //StdRandom.setSeed (10);
422                args = new String[] { "6", "10", "3" };
423
424                int V = Integer.parseInt (args[0]);
425                int E = Integer.parseInt (args[1]);
426                int c = Integer.parseInt (args[2]);
427
428                for (int i= 5; i>0; i--) {
429                        print (GraphGenerator.random (V, E), "random-" + V + "-" + E);
430                        print (GraphGenerator.random (V, E), "random-" + V + "-" + E);
431                        print (GraphGenerator.simple (V, E), "simple-" + V + "-" + E);
432                        print (GraphGenerator.complete (V), "complete-" + V);
433                        print (GraphGenerator.spanningTree (V), "spanningTree-" + V);
434                        print (GraphGenerator.simpleConnected (V, E), "simpleConnected-" + V + "-" + E);
435                        print (GraphGenerator.connected (V, E), "connected-" + V + "-" + E);
436                        print (GraphGenerator.path (V), "path-" + V);
437                        print (GraphGenerator.binaryTree (V), "binaryTree-" + V);
438                        print (GraphGenerator.cycle (V), "cycle-" + V);
439                        if (E <= (V - c)) E = (V - c) + 1;
440                        print (GraphGenerator.connected (V, E, c), "connected-" + V + "-" + E + "-" + c);
441                        print (GraphGenerator.eulerianCycle (V, E), "eulerian-" + V + "-" + E);
442                }
443        }
444}