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}