Package algs42

Class Digraph

java.lang.Object
algs42.Digraph
public class Digraph extends Object
The Digraph class represents an directed graph of vertices named 0 through V-1. It supports the following operations: add an edge to the graph, iterate over all of the neighbors incident to a vertex. Parallel edges and self-loops are permitted.

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

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    private final Bag<Integer>[]
    adj
     
    private int
    E
     
    private int[]
    indegree
     
    private final int
    V
     

  • Constructor Summary

    Constructors
    Constructor
    Description
    Digraph(int V)
    Create an empty digraph with V vertices.
    Digraph(Digraph G)
    Initializes a new digraph that is a deep copy of the specified digraph.
    Digraph(In in)
    Initializes a digraph from the specified input stream.

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    addEdge(int v, int w)
    Add the directed edge v->w to the digraph.
    Iterable<Integer>
    adj(int v)
    Return the list of vertices pointed to from vertex v as an Iterable.
    int
    E()
    Return the number of edges in the digraph.
    int
    indegree(int v)
    Returns the number of directed edges incident to vertex v.
    static void
    main(String[] args)
    Test client.
    int
    outdegree(int v)
    Returns the number of directed edges incident from vertex v.
    Digraph
    reverse()
    Return the reverse of the digraph.
    void
    toGraphviz(String filename)
    Save a graphviz representation of the graph.
    String
    toString()
    Return a string representation of the digraph.
    int
    V()
    Return the number of vertices in the digraph.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • V

      private final int V

    • E

      private int E

    • adj

      private final Bag<Integer>[] adj

    • indegree

      private int[] indegree

  • Constructor Details

    • Digraph

      public Digraph(int V)
      Create an empty digraph with V vertices.

    • Digraph

      public Digraph(In in)
      Initializes a digraph from the specified input stream. The format is the number of vertices V, followed by the number of edges E, followed by E pairs of vertices, with each entry separated by whitespace.
      Parameters:
      in - the input stream
      Throws:
      IllegalArgumentException - if in is null
      IllegalArgumentException - if the endpoints of any edge are not in prescribed range
      IllegalArgumentException - if the number of vertices or edges is negative
      IllegalArgumentException - if the input stream is in the wrong format

    • Digraph

      public Digraph(Digraph G)
      Initializes a new digraph that is a deep copy of the specified digraph.
      Parameters:
      G - the digraph to copy
      Throws:
      IllegalArgumentException - if G is null

  • Method Details

    • V

      public int V()
      Return the number of vertices in the digraph.

    • E

      public int E()
      Return the number of edges in the digraph.

    • addEdge

      public void addEdge(int v, int w)
      Add the directed edge v->w to the digraph.
      Throws:
      IndexOutOfBoundsException - unless both 0 <= v < V and 0 <= w < V

    • adj

      public Iterable<Integer> adj(int v)
      Return the list of vertices pointed to from vertex v as an Iterable.
      Throws:
      IndexOutOfBoundsException - unless 0 <= v < V

    • outdegree

      public int outdegree(int v)
      Returns the number of directed edges incident from vertex v. This is known as the outdegree of vertex v.
      Parameters:
      v - the vertex
      Returns:
      the outdegree of vertex v
      Throws:
      IllegalArgumentException - unless {@code 0 <= v < V}

    • indegree

      public int indegree(int v)
      Returns the number of directed edges incident to vertex v. This is known as the indegree of vertex v.
      Parameters:
      v - the vertex
      Returns:
      the indegree of vertex v
      Throws:
      IllegalArgumentException - unless 0 <= v < V

    • reverse

      public Digraph reverse()
      Return the reverse of the digraph.

    • toString

      public String toString()
      Return a string representation of the digraph.
      Overrides:
      toString in class Object

    • toGraphviz

      public void toGraphviz(String filename)
      Save a graphviz representation of the graph. See graphviz.org.

    • main

      public static void main(String[] args)
      Test client.