edu.princeton.cs.algs4

## Class GraphGenerator

• Object
• edu.princeton.cs.algs4.GraphGenerator

• ```public class GraphGenerator
extends Object```
The `GraphGenerator` class provides static methods for creating various graphs, including Erdos-Renyi random graphs, random bipartite graphs, random k-regular graphs, and random rooted trees.

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

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

Methods
Modifier and Type Method and Description
`static Graph` `binaryTree(int V)`
Returns a complete binary tree graph on `V` vertices.
`static Graph` ```bipartite(int V1, int V2, double p)```
Returns a random simple bipartite graph on `V1` and `V2` vertices, containing each possible edge with probability `p`.
`static Graph` ```bipartite(int V1, int V2, int E)```
Returns a random simple bipartite graph on `V1` and `V2` vertices with `E` edges.
`static Graph` `complete(int V)`
Returns the complete graph on `V` vertices.
`static Graph` ```completeBipartite(int V1, int V2)```
Returns a complete bipartite graph on `V1` and `V2` vertices.
`static Graph` `cycle(int V)`
Returns a cycle graph on `V` vertices.
`static Graph` ```eulerianCycle(int V, int E)```
Returns an Eulerian cycle graph on `V` vertices.
`static Graph` ```eulerianPath(int V, int E)```
Returns an Eulerian path graph on `V` vertices.
`static void` `main(String[] args)`
Unit tests the `GraphGenerator` library.
`static Graph` `path(int V)`
Returns a path graph on `V` vertices.
`static Graph` ```regular(int V, int k)```
Returns a uniformly random `k`-regular graph on `V` vertices (not necessarily simple).
`static Graph` ```simple(int V, double p)```
Returns a random simple graph on `V` vertices, with an edge between any two vertices with probability `p`.
`static Graph` ```simple(int V, int E)```
Returns a random simple graph containing `V` vertices and `E` edges.
`static Graph` `star(int V)`
Returns a star graph on `V` vertices.
`static Graph` `tree(int V)`
Returns a uniformly random tree on `V` vertices.
`static Graph` `wheel(int V)`
Returns a wheel graph on `V` vertices.
• ### Methods inherited from class Object

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

• #### simple

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

```public static Graph simple(int V,
double p)```
Returns a random simple graph on `V` vertices, with an edge between any two vertices with probability `p`. This is sometimes referred to as the Erdos-Renyi random graph model.
Parameters:
`V` - the number of vertices
`p` - the probability of choosing an edge
Returns:
a random simple graph 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 Graph complete(int V)`
Returns the complete graph on `V` vertices.
Parameters:
`V` - the number of vertices
Returns:
the complete graph on `V` vertices
• #### completeBipartite

```public static Graph completeBipartite(int V1,
int V2)```
Returns a complete bipartite graph on `V1` and `V2` vertices.
Parameters:
`V1` - the number of vertices in one partition
`V2` - the number of vertices in the other partition
Returns:
a complete bipartite graph on `V1` and `V2` vertices
Throws:
`IllegalArgumentException` - if probability is not between 0 and 1
• #### bipartite

```public static Graph bipartite(int V1,
int V2,
int E)```
Returns a random simple bipartite graph on `V1` and `V2` vertices with `E` edges.
Parameters:
`V1` - the number of vertices in one partition
`V2` - the number of vertices in the other partition
`E` - the number of edges
Returns:
a random simple bipartite graph on `V1` and `V2` vertices, containing a total of `E` edges
Throws:
`IllegalArgumentException` - if no such simple bipartite graph exists
• #### bipartite

```public static Graph bipartite(int V1,
int V2,
double p)```
Returns a random simple bipartite graph on `V1` and `V2` vertices, containing each possible edge with probability `p`.
Parameters:
`V1` - the number of vertices in one partition
`V2` - the number of vertices in the other partition
`p` - the probability that the graph contains an edge with one endpoint in either side
Returns:
a random simple bipartite graph on `V1` and `V2` vertices, containing each possible edge with probability `p`
Throws:
`IllegalArgumentException` - if probability is not between 0 and 1
• #### path

`public static Graph path(int V)`
Returns a path graph on `V` vertices.
Parameters:
`V` - the number of vertices in the path
Returns:
a path graph on `V` vertices
• #### binaryTree

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

`public static Graph cycle(int V)`
Returns a cycle graph on `V` vertices.
Parameters:
`V` - the number of vertices in the cycle
Returns:
a cycle graph on `V` vertices
• #### eulerianCycle

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

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

`public static Graph wheel(int V)`
Returns a wheel graph on `V` vertices.
Parameters:
`V` - the number of vertices in the wheel
Returns:
a wheel graph on `V` vertices: a single vertex connected to every vertex in a cycle on `V-1` vertices
• #### star

`public static Graph star(int V)`
Returns a star graph on `V` vertices.
Parameters:
`V` - the number of vertices in the star
Returns:
a star graph on `V` vertices: a single vertex connected to every other vertex
• #### regular

```public static Graph regular(int V,
int k)```
Returns a uniformly random `k`-regular graph on `V` vertices (not necessarily simple). The graph is simple with probability only about e^(-k^2/4), which is tiny when k = 14.
Parameters:
`V` - the number of vertices in the graph
`k` - degree of each vertex
Returns:
a uniformly random `k`-regular graph on `V` vertices.
• #### tree

`public static Graph tree(int V)`
Returns a uniformly random tree on `V` vertices. This algorithm uses a Prufer sequence and takes time proportional to V log V.
Parameters:
`V` - the number of vertices in the tree
Returns:
a uniformly random tree on `V` vertices
• #### main

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