Package algs42
Class DigraphGenerator
java.lang.Object
algs42.DigraphGenerator
The
DigraphGenerator
class provides static methods for creating
various digraphs, including ErdosRenyi 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

Nested Class Summary

Constructor Summary

Method Summary
Modifier and TypeMethodDescriptionstatic Digraph
binaryTree
(int V) Returns a complete binary tree digraph onV
vertices.static Digraph
complete
(int V) Returns the complete digraph onV
vertices.static Digraph
static Digraph
cycle
(int V) Returns a cycle digraph onV
vertices.static Digraph
dag
(int V, int E) Returns a random simple DAG containingV
vertices andE
edges.static Digraph
eulerianCycle
(int V, int E) Returns an Eulerian cycle digraph onV
vertices.static Digraph
eulerianPath
(int V, int E) Returns an Eulerian path digraph onV
vertices.static Digraph
static void
static Digraph
path
(int V) Returns a path digraph onV
vertices.private static void
Unit tests theDigraphGenerator
library.static Digraph
random
(int V, int E) Create a random digraph with V vertices and E edges.static Digraph
rootedInDAG
(int V, int E) Returns a random rootedin DAG onV
vertices andE
edges.static Digraph
rootedInTree
(int V) Returns a random rootedin tree onV
vertices.static Digraph
rootedOutDAG
(int V, int E) Returns a random rootedout DAG onV
vertices andE
edges.static Digraph
rootedOutTree
(int V) Returns a random rootedout tree onV
vertices.static Digraph
simple
(int V, double p) Returns a random simple digraph onV
vertices, with an edge between any two vertices with probabilityp
.static Digraph
simple
(int V, int E) Returns a random simple digraph containingV
vertices andE
edges.static Digraph
strong
(int V, int E, int c) Returns a random simple digraph onV
vertices,E
edges and (at most)c
strong components.static Digraph
tournament
(int V) Returns a random tournament digraph onV
vertices.

Constructor Details

DigraphGenerator
public DigraphGenerator()


Method Details

fromIn

copy

random
Create a random digraph with V vertices and E edges. Expected running time is proportional to V + E. 
simple
Returns a random simple digraph containingV
vertices andE
edges. Parameters:
V
 the number of verticesE
 the number of vertices Returns:
 a random simple digraph on
V
vertices, containing a total ofE
edges  Throws:
IllegalArgumentException
 if no such simple digraph exists

simple
Returns a random simple digraph onV
vertices, with an edge between any two vertices with probabilityp
. This is sometimes referred to as the ErdosRenyi random digraph model. This implementations takes time propotional to V^2 (even ifp
is small). Parameters:
V
 the number of verticesp
 the probability of choosing an edge Returns:
 a random simple digraph on
V
vertices, with an edge between any two vertices with probabilityp
 Throws:
IllegalArgumentException
 if probability is not between 0 and 1

complete
Returns the complete digraph onV
vertices. Parameters:
V
 the number of vertices Returns:
 the complete digraph on
V
vertices

dag
Returns a random simple DAG containingV
vertices andE
edges. Note: it is not uniformly selected at random among all such DAGs. Parameters:
V
 the number of verticesE
 the number of vertices Returns:
 a random simple DAG on
V
vertices, containing a total ofE
edges  Throws:
IllegalArgumentException
 if no such simple DAG exists

tournament
Returns a random tournament digraph onV
vertices. A tournament digraph is a DAG in which for every two vertices, there is one directed edge. A tournament is an oriented complete graph. Parameters:
V
 the number of vertices Returns:
 a random tournament digraph on
V
vertices

rootedInDAG
Returns a random rootedin DAG onV
vertices andE
edges. A rooted intree 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 verticesE
 the number of edges Returns:
 a random rootedin DAG on
V
vertices andE
edges

rootedOutDAG
Returns a random rootedout DAG onV
vertices andE
edges. A rooted outtree 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 verticesE
 the number of edges Returns:
 a random rootedout DAG on
V
vertices andE
edges

rootedInTree
Returns a random rootedin tree onV
vertices. A rooted intree 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 rootedin tree on
V
vertices

rootedOutTree
Returns a random rootedout tree onV
vertices. A rooted outtree 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 rootedout tree on
V
vertices

path
Returns a path digraph onV
vertices. Parameters:
V
 the number of vertices in the path Returns:
 a digraph that is a directed path on
V
vertices

binaryTree
Returns a complete binary tree digraph onV
vertices. Parameters:
V
 the number of vertices in the binary tree Returns:
 a digraph that is a complete binary tree on
V
vertices

cycle
Returns a cycle digraph onV
vertices. Parameters:
V
 the number of vertices in the cycle Returns:
 a digraph that is a directed cycle on
V
vertices

eulerianCycle
Returns an Eulerian cycle digraph onV
vertices. Parameters:
V
 the number of vertices in the cycleE
 the number of edges in the cycle Returns:
 a digraph that is a directed Eulerian cycle on
V
vertices andE
edges  Throws:
IllegalArgumentException
 if eitherV <= 0
orE <= 0

eulerianPath
Returns an Eulerian path digraph onV
vertices. Parameters:
V
 the number of vertices in the pathE
 the number of edges in the path Returns:
 a digraph that is a directed Eulerian path on
V
vertices andE
edges  Throws:
IllegalArgumentException
 if eitherV <= 0
orE < 0

strong
Returns a random simple digraph onV
vertices,E
edges and (at most)c
strong components. The vertices are randomly assigned integer labels between0
andc1
(corresponding to strong components). Then, a strong component is created among the vertices with the same label. Next, random edges (either between two vertices with the same labels or from a vertex 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 verticesE
 the number of edgesc
 the (maximum) number of strong components Returns:
 a random simple digraph on
V
vertices andE
edges, with (at most)c
strong components  Throws:
IllegalArgumentException
 ifc
is larger thanV

print
Unit tests theDigraphGenerator
library. 
main
