public class DigraphGenerator extends Object
DigraphGenerator
class provides static methods for creating
various digraphs, including Erdos-Renyi 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.
Modifier and Type | Method and Description |
---|---|
static Digraph |
binaryTree(int V)
Returns a complete binary tree digraph on
V vertices. |
static Digraph |
complete(int V)
Returns the complete digraph on
V vertices. |
static Digraph |
cycle(int V)
Returns a cycle digraph on
V vertices. |
static Digraph |
dag(int V,
int E)
Returns a random simple DAG containing
V vertices and E edges. |
static Digraph |
eulerianCycle(int V,
int E)
Returns an Eulerian cycle digraph on
V vertices. |
static Digraph |
eulerianPath(int V,
int E)
Returns an Eulerian path digraph on
V vertices. |
static void |
main(String[] args)
Unit tests the
DigraphGenerator library. |
static Digraph |
path(int V)
Returns a path digraph on
V vertices. |
static Digraph |
rootedInDAG(int V,
int E)
Returns a random rooted-in DAG on
V vertices and E edges. |
static Digraph |
rootedInTree(int V)
Returns a random rooted-in tree on
V vertices. |
static Digraph |
rootedOutDAG(int V,
int E)
Returns a random rooted-out DAG on
V vertices and E edges. |
static Digraph |
rootedOutTree(int V)
Returns a random rooted-out tree on
V vertices. |
static Digraph |
simple(int V,
double p)
Returns a random simple digraph on
V vertices, with an
edge between any two vertices with probability p . |
static Digraph |
simple(int V,
int E)
Returns a random simple digraph containing
V vertices and E edges. |
static Digraph |
strong(int V,
int E,
int c)
Returns a random simple digraph on
V vertices, E
edges and (at least) c strong components. |
static Digraph |
tournament(int V)
Returns a random tournament digraph on
V vertices. |
public static Digraph simple(int V, int E)
V
vertices and E
edges.V
- the number of verticesE
- the number of verticesV
vertices, containing a total
of E
edgesIllegalArgumentException
- if no such simple digraph existspublic static Digraph simple(int V, double p)
V
vertices, with an
edge between any two vertices with probability p
. This is sometimes
referred to as the Erdos-Renyi random digraph model.
This implementations takes time propotional to V^2 (even if p
is small).V
- the number of verticesp
- the probability of choosing an edgeV
vertices, with an edge between
any two vertices with probability p
IllegalArgumentException
- if probability is not between 0 and 1public static Digraph complete(int V)
V
vertices.V
- the number of verticesV
verticespublic static Digraph dag(int V, int E)
V
vertices and E
edges.
Note: it is not uniformly selected at random among all such DAGs.V
- the number of verticesE
- the number of verticesV
vertices, containing a total
of E
edgesIllegalArgumentException
- if no such simple DAG existspublic static Digraph tournament(int V)
V
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.V
- the number of verticesV
verticespublic static Digraph rootedInDAG(int V, int E)
V
vertices and E
edges.
A rooted in-tree 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.V
- the number of verticesE
- the number of edgesV
vertices and E
edgespublic static Digraph rootedOutDAG(int V, int E)
V
vertices and E
edges.
A rooted out-tree 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.V
- the number of verticesE
- the number of edgesV
vertices and E
edgespublic static Digraph rootedInTree(int V)
V
vertices.
A rooted in-tree 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.V
- the number of verticesV
verticespublic static Digraph rootedOutTree(int V)
V
vertices. A rooted out-tree
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.V
- the number of verticesV
verticespublic static Digraph path(int V)
V
vertices.V
- the number of vertices in the pathV
verticespublic static Digraph binaryTree(int V)
V
vertices.V
- the number of vertices in the binary treeV
verticespublic static Digraph cycle(int V)
V
vertices.V
- the number of vertices in the cycleV
verticespublic static Digraph eulerianCycle(int V, int E)
V
vertices.V
- the number of vertices in the cycleE
- the number of edges in the cycleV
vertices
and E
edgesIllegalArgumentException
- if either V <= 0
or E <= 0
public static Digraph eulerianPath(int V, int E)
V
vertices.V
- the number of vertices in the pathE
- the number of edges in the pathV
vertices
and E
edgesIllegalArgumentException
- if either V <= 0
or E < 0
public static Digraph strong(int V, int E, int c)
V
vertices, E
edges and (at least) c
strong components. The vertices are randomly
assigned integer labels between 0
and c-1
(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 vetex 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.V
- the number of verticesE
- the number of edgesc
- the (maximum) number of strong componentsV
vertices and
E
edges, with (at most) c
strong componentsIllegalArgumentException
- if c
is larger than V
public static void main(String[] args)
DigraphGenerator
library.args
- the command-line arguments