Package edu.princeton.cs.algs4

Class DigraphGenerator

Object

edu.princeton.cs.algs4.DigraphGenerator

public class DigraphGenerator
extends Object

The 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.

Author:

Robert Sedgewick, Kevin Wayne

Method Summary

Modifier and Type	Method	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	completeRootedInDAG(int V)	Returns a complete rooted-in DAG on V vertices.
static Digraph	completeRootedOutDAG(int V)	Returns a complete rooted-out DAG 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.

Methods inherited from class java.lang.Object

clone, equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

simple

public static Digraph simple(int V,
                             int E)

Returns a random simple digraph containing V vertices and E edges.

Parameters:

V - the number of vertices

E - the number of vertices

Returns:

a random simple digraph on V vertices, containing a total of E edges

Throws:

IllegalArgumentException - if no such simple digraph exists

simple

public 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. This is sometimes referred to as the Erdos-Renyi random digraph model. This implementations takes time proportional to V^2 (even if p is small).

Parameters:

V - the number of vertices

p - the probability of choosing an edge

Returns:

a random simple digraph on V vertices, with an edge between any two vertices with probability p

Throws:

IllegalArgumentException - if probability is not between 0 and 1

complete

public static Digraph complete(int V)

Returns the complete digraph on V vertices. In a complete digraph, every pair of distinct vertices is connected by two antiparallel edges. There are V*(V-1) 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 containing V vertices and E edges. Note: it is not uniformly selected at random among all such DAGs.

Parameters:

V - the number of vertices

E - the number of vertices

Returns:

a random simple DAG on V vertices, containing a total of E edges

Throws:

IllegalArgumentException - if no such simple DAG exists

tournament

public static Digraph tournament(int V)

Returns a random tournament digraph on V 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 rooted-in DAG on V vertices. A rooted in-tree is a DAG in which there is a single vertex reachable from every other vertex. A complete rooted in-DAG has V*(V-1)/2 edges.

Parameters:

V - the number of vertices

Returns:

a complete rooted-in DAG on V vertices

rootedInDAG

public static Digraph rootedInDAG(int V,
                                  int E)

Returns a random rooted-in DAG on 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.

Parameters:

V - the number of vertices

E - the number of edges

Returns:

a random rooted-in DAG on V vertices and E edges

completeRootedOutDAG

public static Digraph completeRootedOutDAG(int V)

Returns a complete rooted-out DAG on V vertices. A rooted out-tree is a DAG in which every vertex is reachable from a single vertex. A complete rooted in-DAG has V*(V-1)/2 edges.

Parameters:

V - the number of vertices

Returns:

a complete rooted-out DAG on V vertices

rootedOutDAG

public static Digraph rootedOutDAG(int V,
                                   int E)

Returns a random rooted-out DAG on 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.

Parameters:

V - the number of vertices

E - the number of edges

Returns:

a random rooted-out DAG on V vertices and E edges

rootedInTree

public static Digraph rootedInTree(int V)

Returns a random rooted-in tree on 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.

Parameters:

V - the number of vertices

Returns:

a random rooted-in tree on V vertices

rootedOutTree

public static Digraph rootedOutTree(int V)

Returns a random rooted-out tree on 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.

Parameters:

V - the number of vertices

Returns:

a random rooted-out tree on V vertices

path

public static Digraph path(int V)

Returns a path digraph on V 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 on V 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 on V 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 on V vertices.

Parameters:

V - the number of vertices in the cycle

E - the number of edges in the cycle

Returns:

a digraph that is a directed Eulerian cycle on V vertices and E edges

Throws:

IllegalArgumentException - if either V <= 0 or E <= 0

eulerianPath

public static Digraph eulerianPath(int V,
                                   int E)

Returns an Eulerian path digraph on V vertices.

Parameters:

V - the number of vertices in the path

E - the number of edges in the path

Returns:

a digraph that is a directed Eulerian path on V vertices and E edges

Throws:

IllegalArgumentException - if either V <= 0 or E < 0

strong

public 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. 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 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 vertices

E - the number of edges

c - the (maximum) number of strong components

Returns:

a random simple digraph on V vertices and E edges, with (at most) c strong components

Throws:

IllegalArgumentException - if c is larger than V

main

public static void main(String[] args)

Unit tests the DigraphGenerator library.

Parameters:

args - the command-line arguments