Package edu.princeton.cs.algs4
Class DigraphGenerator
 Object

 edu.princeton.cs.algs4.DigraphGenerator

public class DigraphGenerator extends Object
TheDigraphGenerator
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


Method Summary
All Methods Static Methods Concrete Methods Modifier and Type Method Description static 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
completeRootedInDAG(int V)
Returns a complete rootedin DAG onV
vertices.static Digraph
completeRootedOutDAG(int V)
Returns a complete rootedout DAG onV
vertices.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 void
main(String[] args)
Unit tests theDigraphGenerator
library.static Digraph
path(int V)
Returns a path digraph onV
vertices.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 least)c
strong components.static Digraph
tournament(int V)
Returns a random tournament digraph onV
vertices.



Method Detail

simple
public static Digraph simple(int V, int E)
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
public static Digraph simple(int V, double p)
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 proportional 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
public static Digraph complete(int V)
Returns the complete digraph onV
vertices. In a complete digraph, every pair of distinct vertices is connected by two antiparallel edges. There areV*(V1)
edges. Parameters:
V
 the number of vertices Returns:
 the complete digraph on
V
vertices

dag
public static Digraph dag(int V, int E)
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
public static Digraph tournament(int V)
Returns a random tournament digraph onV
vertices. A tournament digraph is a digraph in which, for every pair of vertices, there is one and only one directed edge connecting them. A tournament is an oriented complete graph. Parameters:
V
 the number of vertices Returns:
 a random tournament digraph on
V
vertices

completeRootedInDAG
public static Digraph completeRootedInDAG(int V)
Returns a complete rootedin DAG onV
vertices. A rooted intree is a DAG in which there is a single vertex reachable from every other vertex. A complete rooted inDAG has V*(V1)/2 edges. Parameters:
V
 the number of vertices Returns:
 a complete rootedin DAG on
V
vertices

rootedInDAG
public static Digraph rootedInDAG(int V, int E)
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

completeRootedOutDAG
public static Digraph completeRootedOutDAG(int V)
Returns a complete rootedout DAG onV
vertices. A rooted outtree is a DAG in which every vertex is reachable from a single vertex. A complete rooted inDAG has V*(V1)/2 edges. Parameters:
V
 the number of vertices Returns:
 a complete rootedout DAG on
V
vertices

rootedOutDAG
public static Digraph rootedOutDAG(int V, int E)
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
public static Digraph rootedInTree(int V)
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
public static Digraph rootedOutTree(int V)
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
public static Digraph path(int V)
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
public static Digraph binaryTree(int V)
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
public static Digraph cycle(int V)
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
public static Digraph eulerianCycle(int V, int E)
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
public static Digraph eulerianPath(int V, int E)
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
public static Digraph strong(int V, int E, int c)
Returns a random simple digraph onV
vertices,E
edges and (at least)c
strong components. The vertices are randomly assigned integer labels between0
andc1
(corresponding to strong components). Then, a strong component is creates 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

main
public static void main(String[] args)
Unit tests theDigraphGenerator
library. Parameters:
args
 the commandline arguments

