Package algs42

Class DigraphGenerator

java.lang.Object
algs42.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

  • Nested Class Summary

    Nested Classes
    Modifier and Type
    Class
    Description
    private static class 
    DigraphGenerator.Edge
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    DigraphGenerator()
     

  • 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
    copy(Digraph G)
     
    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 Digraph
    fromIn(In in)
     
    static void
    main(String[] args)
     
    static Digraph
    path(int V)
    Returns a path digraph on V vertices.
    private static void
    print(Digraph G, String filename)
    Unit tests the DigraphGenerator library.
    static Digraph
    random(int V, int E)
    Create a random digraph with V vertices and E edges.
    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 most) 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 Details

  • Method Details

    • fromIn

      public static Digraph fromIn(In in)

    • copy

      public static Digraph copy(Digraph G)

    • random

      public static Digraph random(int V, int E)
      Create a random digraph with V vertices and E edges. Expected running time is proportional to V + E.

    • 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 directed 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

    • 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 most) c strong components. The vertices are randomly assigned integer labels between 0 and c-1 (corresponding to strong components). Then, a strong component is created 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

    • print

      private static void print(Digraph G, String filename)
      Unit tests the DigraphGenerator library.

    • main

      public static void main(String[] args)