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}