DigraphGenerator Class

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.

Inheritance Hierarchy

SystemObject
Algs4NetDigraphGenerator

Namespace: Algs4Net
Assembly: Algs4Net (in Algs4Net.dll) Version: 1.0.0.0 (1.0.0.0)

Syntax

Copy

public class DigraphGenerator

The DigraphGenerator type exposes the following members.

Methods

	Name	Description
	BinaryTree	Returns a complete binary tree digraph on V vertices.
	Complete	Returns the complete digraph on V vertices.
	Cycle	Returns a cycle digraph on V vertices.
	Dag	Returns a random simple DAG containing V vertices and E edges. Note: it is not uniformly selected at random among all such DAGs.
	EulerianCycle	Returns an Eulerian cycle digraph on V vertices.
	EulerianPath	Returns an Eulerian path digraph on V vertices.
	MainTest	Demo test the DigraphGenerator library.
	Path	Returns a path digraph on V vertices.
	RootedInDAG	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.
	RootedInTree	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.
	RootedOutDAG	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.
	RootedOutTree	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.
	Simple(Int32, Double)	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).
	Simple(Int32, Int32)	Returns a random simple digraph containing V vertices and E edges.
	Strong	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.
	Tournament	Returns a random tournament digraph on 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.

Top

Remarks

For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

This class is a C# port from the original Java class DigraphGenerator implementation by the respective authors.

Reference

Algs4Net Namespace