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

All Methods Static Methods Concrete Methods
Modifier and Type	Method	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 java.lang.Object
clone, equals, 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

Class GraphGenerator

Method Summary

Methods inherited from class java.lang.Object

Method Detail

simple

simple

complete

completeBipartite

bipartite

bipartite

path

binaryTree

cycle

eulerianCycle

eulerianPath

wheel

star

regular

tree

main