Package algs41
Class GraphGenerator
java.lang.Object
algs41.GraphGenerator
-
Constructor Summary
-
Method Summary
Modifier and TypeMethodDescriptionstatic Graph
binaryTree
(int V) Returns a complete binary tree graph onV
vertices.static Graph
bipartite
(int V1, int V2, double p) Returns a random simple bipartite graph onV1
andV2
vertices, containing each possible edge with probabilityp
.static Graph
complete
(int V) static Graph
connected
(int V, int E) static Graph
connected
(int V, int E, int c) static Graph
static Graph
cycle
(int V) Returns a cycle graph onV
vertices.static Graph
eulerianCycle
(int V, int E) Returns an Eulerian cycle graph onV
vertices.static Graph
eulerianPath
(int V, int E) Returns an Eulerian path graph onV
vertices.static Graph
Create a graph from input stream.static void
static Graph
path
(int V) Returns a path graph onV
vertices.static void
static Graph
random
(int V, int E) static Graph
regular
(int V, int k) Returns a uniformly randomk
-regular graph onV
vertices (not necessarily simple).static Graph
simple
(int V, int E) static Graph
simpleConnected
(int V, int E) static Graph
spanningTree
(int V) static Graph
star
(int V) Returns a star graph onV
vertices.static Graph
tree
(int V) Returns a uniformly random tree onV
vertices.static Graph
wheel
(int V) Returns a wheel graph onV
vertices.
-
Constructor Details
-
GraphGenerator
public GraphGenerator()
-
-
Method Details
-
fromIn
Create a graph from input stream. -
copy
-
complete
-
simple
-
simpleConnected
-
connected
-
random
-
spanningTree
-
connected
-
bipartite
Returns a random simple bipartite graph onV1
andV2
vertices, containing each possible edge with probabilityp
.- Parameters:
V1
- the number of vertices in one partitionV2
- the number of vertices in the other partitionp
- the probability that the graph contains an edge with one endpoint in either side- Returns:
- a random simple bipartite graph on
V1
andV2
vertices, containing each possible edge with probabilityp
- Throws:
IllegalArgumentException
- if probability is not between 0 and 1
-
path
Returns a path graph onV
vertices.- Parameters:
V
- the number of vertices in the path- Returns:
- a path graph on
V
vertices
-
binaryTree
Returns a complete binary tree graph onV
vertices.- Parameters:
V
- the number of vertices in the binary tree- Returns:
- a complete binary tree graph on
V
vertices
-
cycle
Returns a cycle graph onV
vertices.- Parameters:
V
- the number of vertices in the cycle- Returns:
- a cycle graph on
V
vertices
-
eulerianCycle
Returns an Eulerian cycle graph onV
vertices.- Parameters:
V
- the number of vertices in the cycleE
- the number of edges in the cycle- Returns:
- a graph that is an Eulerian cycle on
V
vertices andE
edges - Throws:
IllegalArgumentException
- if eitherV <= 0
orE <= 0
-
eulerianPath
Returns an Eulerian path graph onV
vertices.- Parameters:
V
- the number of vertices in the pathE
- the number of edges in the path- Returns:
- a graph that is an Eulerian path on
V
vertices andE
edges - Throws:
IllegalArgumentException
- if eitherV <= 0
orE < 0
-
wheel
Returns a wheel graph onV
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 onV-1
vertices
-
star
Returns a star graph onV
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
Returns a uniformly randomk
-regular graph onV
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 graphk
- degree of each vertex- Returns:
- a uniformly random
k
-regular graph onV
vertices.
-
tree
Returns a uniformly random tree onV
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
-
print
-
main
-