edu.princeton.cs.algorithms

Class DigraphGenerator

java.lang.Object

edu.princeton.cs.algorithms.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

Constructor Summary

Constructors

Constructor and Description
DigraphGenerator()

Method Summary

Methods

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 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, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

DigraphGenerator

public DigraphGenerator()

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

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 DAG in which for every two vertices, there is one direted edge. A tournament is an oriented complete graph.

Parameters:

V - the number of vertices

Returns:

a random tournament digraph 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

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

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

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.