GraphGenerator

java.lang.Object
- GraphGenerator

```
public class GraphGenerator
extends java.lang.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.

Constructor Summary

Constructors
Constructor and Description

GraphGenerator()

Constructors
Constructor and Description
`GraphGenerator()`

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 void`	`main(java.lang.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, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

- Constructor Detail
  - GraphGenerator
```
public GraphGenerator()
```
- 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:
    
    java.lang.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:
    
    java.lang.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:
    
    java.lang.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:
    
    java.lang.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:
    
    java.lang.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
  - 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
    
    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(java.lang.String[] args)
```
    Unit tests the GraphGenerator library.

Class GraphGenerator

Constructor Summary

Method Summary

Methods inherited from class java.lang.Object

Constructor Detail

GraphGenerator

Method Detail

simple

simple

complete

completeBipartite

bipartite

bipartite

path

binaryTree

cycle

wheel

star

regular

tree

main