edu.princeton.cs.algs4

## Class DigraphGenerator

• Object
• edu.princeton.cs.algs4.DigraphGenerator

• ```public class DigraphGenerator
extends Object```
The `DigraphGenerator` class provides static methods for creating various digraphs, including Erdos-Renyi random digraphs, random DAGs, random rooted trees, random rooted DAGs, random tournaments, path digraphs, cycle digraphs, and the complete digraph.

For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:
Robert Sedgewick, Kevin Wayne
• ### Method Summary

All Methods
Modifier and Type Method and Description
`static Digraph` `binaryTree(int V)`
Returns a complete binary tree digraph on `V` vertices.
`static Digraph` `complete(int V)`
Returns the complete digraph on `V` vertices.
`static Digraph` `completeRootedInDAG(int V)`
Returns a complete rooted-in DAG on `V` vertices.
`static Digraph` `completeRootedOutDAG(int V)`
Returns a complete rooted-out DAG on `V` vertices.
`static Digraph` `cycle(int V)`
Returns a cycle digraph on `V` vertices.
`static Digraph` ```dag(int V, int E)```
Returns a random simple DAG containing `V` vertices and `E` edges.
`static Digraph` ```eulerianCycle(int V, int E)```
Returns an Eulerian cycle digraph on `V` vertices.
`static Digraph` ```eulerianPath(int V, int E)```
Returns an Eulerian path digraph on `V` vertices.
`static void` `main(String[] args)`
Unit tests the `DigraphGenerator` library.
`static Digraph` `path(int V)`
Returns a path digraph on `V` vertices.
`static Digraph` ```rootedInDAG(int V, int E)```
Returns a random rooted-in DAG on `V` vertices and `E` edges.
`static Digraph` `rootedInTree(int V)`
Returns a random rooted-in tree on `V` vertices.
`static Digraph` ```rootedOutDAG(int V, int E)```
Returns a random rooted-out DAG on `V` vertices and `E` edges.
`static Digraph` `rootedOutTree(int V)`
Returns a random rooted-out tree on `V` vertices.
`static Digraph` ```simple(int V, double p)```
Returns a random simple digraph on `V` vertices, with an edge between any two vertices with probability `p`.
`static Digraph` ```simple(int V, int E)```
Returns a random simple digraph containing `V` vertices and `E` edges.
`static Digraph` ```strong(int V, int E, int c)```
Returns a random simple digraph on `V` vertices, `E` edges and (at least) `c` strong components.
`static Digraph` `tournament(int V)`
Returns a random tournament digraph on `V` vertices.
• ### Methods inherited from class Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Method Detail

• #### simple

```public static Digraph simple(int V,
int E)```
Returns a random simple digraph containing `V` vertices and `E` edges.
Parameters:
`V` - the number of vertices
`E` - the number of vertices
Returns:
a random simple digraph on `V` vertices, containing a total of `E` edges
Throws:
`IllegalArgumentException` - if no such simple digraph exists
• #### simple

```public static Digraph simple(int V,
double p)```
Returns a random simple digraph on `V` vertices, with an edge between any two vertices with probability `p`. This is sometimes referred to as the Erdos-Renyi random digraph model. This implementations takes time propotional to V^2 (even if `p` is small).
Parameters:
`V` - the number of vertices
`p` - the probability of choosing an edge
Returns:
a random simple digraph on `V` vertices, with an edge between any two vertices with probability `p`
Throws:
`IllegalArgumentException` - if probability is not between 0 and 1
• #### complete

`public static Digraph complete(int V)`
Returns the complete digraph on `V` vertices. In a complete digraph, every pair of distinct vertices is connected by two antiparallel edges. There are `V*(V-1)` edges.
Parameters:
`V` - the number of vertices
Returns:
the complete digraph on `V` vertices
• #### dag

```public static Digraph dag(int V,
int E)```
Returns a random simple DAG containing `V` vertices and `E` edges. Note: it is not uniformly selected at random among all such DAGs.
Parameters:
`V` - the number of vertices
`E` - the number of vertices
Returns:
a random simple DAG on `V` vertices, containing a total of `E` edges
Throws:
`IllegalArgumentException` - if no such simple DAG exists
• #### tournament

`public static Digraph tournament(int V)`
Returns a random tournament digraph on `V` vertices. A tournament digraph is a digraph in which, for every pair of vertices, there is one and only one directed edge connecting them. A tournament is an oriented complete graph.
Parameters:
`V` - the number of vertices
Returns:
a random tournament digraph on `V` vertices
• #### completeRootedInDAG

`public static Digraph completeRootedInDAG(int V)`
Returns a complete rooted-in DAG on `V` vertices. A rooted in-tree is a DAG in which there is a single vertex reachable from every other vertex. A complete rooted in-DAG has V*(V-1)/2 edges.
Parameters:
`V` - the number of vertices
Returns:
a complete rooted-in DAG on `V` vertices
• #### rootedInDAG

```public static Digraph rootedInDAG(int V,
int E)```
Returns a random rooted-in DAG on `V` vertices and `E` edges. A rooted in-tree is a DAG in which there is a single vertex reachable from every other vertex. The DAG returned is not chosen uniformly at random among all such DAGs.
Parameters:
`V` - the number of vertices
`E` - the number of edges
Returns:
a random rooted-in DAG on `V` vertices and `E` edges
• #### completeRootedOutDAG

`public static Digraph completeRootedOutDAG(int V)`
Returns a complete rooted-out DAG on `V` vertices. A rooted out-tree is a DAG in which every vertex is reachable from a single vertex. A complete rooted in-DAG has V*(V-1)/2 edges.
Parameters:
`V` - the number of vertices
Returns:
a complete rooted-out DAG on `V` vertices
• #### rootedOutDAG

```public static Digraph rootedOutDAG(int V,
int E)```
Returns a random rooted-out DAG on `V` vertices and `E` edges. A rooted out-tree is a DAG in which every vertex is reachable from a single vertex. The DAG returned is not chosen uniformly at random among all such DAGs.
Parameters:
`V` - the number of vertices
`E` - the number of edges
Returns:
a random rooted-out DAG on `V` vertices and `E` edges
• #### rootedInTree

`public static Digraph rootedInTree(int V)`
Returns a random rooted-in tree on `V` vertices. A rooted in-tree is an oriented tree in which there is a single vertex reachable from every other vertex. The tree returned is not chosen uniformly at random among all such trees.
Parameters:
`V` - the number of vertices
Returns:
a random rooted-in tree on `V` vertices
• #### rootedOutTree

`public static Digraph rootedOutTree(int V)`
Returns a random rooted-out tree on `V` vertices. A rooted out-tree is an oriented tree in which each vertex is reachable from a single vertex. It is also known as a arborescence or branching. The tree returned is not chosen uniformly at random among all such trees.
Parameters:
`V` - the number of vertices
Returns:
a random rooted-out tree on `V` vertices
• #### path

`public static Digraph path(int V)`
Returns a path digraph on `V` vertices.
Parameters:
`V` - the number of vertices in the path
Returns:
a digraph that is a directed path on `V` vertices
• #### binaryTree

`public static Digraph binaryTree(int V)`
Returns a complete binary tree digraph on `V` vertices.
Parameters:
`V` - the number of vertices in the binary tree
Returns:
a digraph that is a complete binary tree on `V` vertices
• #### cycle

`public static Digraph cycle(int V)`
Returns a cycle digraph on `V` vertices.
Parameters:
`V` - the number of vertices in the cycle
Returns:
a digraph that is a directed cycle on `V` vertices
• #### eulerianCycle

```public static Digraph eulerianCycle(int V,
int E)```
Returns an Eulerian cycle digraph on `V` vertices.
Parameters:
`V` - the number of vertices in the cycle
`E` - the number of edges in the cycle
Returns:
a digraph that is a directed Eulerian cycle on `V` vertices and `E` edges
Throws:
`IllegalArgumentException` - if either `V <= 0` or `E <= 0`
• #### eulerianPath

```public static Digraph eulerianPath(int V,
int E)```
Returns an Eulerian path digraph on `V` vertices.
Parameters:
`V` - the number of vertices in the path
`E` - the number of edges in the path
Returns:
a digraph that is a directed Eulerian path on `V` vertices and `E` edges
Throws:
`IllegalArgumentException` - if either `V <= 0` or `E < 0`
• #### strong

```public static Digraph strong(int V,
int E,
int c)```
Returns a random simple digraph on `V` vertices, `E` edges and (at least) `c` strong components. The vertices are randomly assigned integer labels between `0` and `c-1` (corresponding to strong components). Then, a strong component is creates among the vertices with the same label. Next, random edges (either between two vertices with the same labels or from a vetex with a smaller label to a vertex with a larger label). The number of components will be equal to the number of distinct labels that are assigned to vertices.
Parameters:
`V` - the number of vertices
`E` - the number of edges
`c` - the (maximum) number of strong components
Returns:
a random simple digraph on `V` vertices and `E` edges, with (at most) `c` strong components
Throws:
`IllegalArgumentException` - if `c` is larger than `V`
• #### main

`public static void main(String[] args)`
Unit tests the `DigraphGenerator` library.
Parameters:
`args` - the command-line arguments