Package edu.princeton.cs.algs4

Class Digraph

  • public class Digraph
extends Object
    The Digraph class represents a directed graph of vertices named 0 through V - 1. It supports the following two primary operations: add an edge to the digraph, iterate over all of the vertices adjacent from a given vertex. It also provides methods for returning the indegree or outdegree of a vertex, the number of vertices V in the digraph, the number of edges E in the digraph, and the reverse digraph. Parallel edges and self-loops are permitted.

    This implementation uses an adjacency-lists representation, which is a vertex-indexed array of Bag objects. It uses Θ(E + V) space, where E is the number of edges and V is the number of vertices. The reverse() method takes Θ(E + V) time and space; all other instance methods take Θ(1) time. (Though, iterating over the vertices returned by adj(int) takes time proportional to the outdegree of the vertex.) Constructing an empty digraph with V vertices takes Θ(V) time; constructing a digraph with E edges and V vertices takes Θ(E + V) time.

    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 Description
      Digraph​(int V)
      Initializes 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.

    • Constructor Detail

      • Digraph

        public Digraph​(int V)
        Initializes an empty digraph with V vertices.
        Parameters:
        V - the number of vertices
        Throws:
        IllegalArgumentException - if V < 0

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

      • V

        public int V()
        Returns the number of vertices in this digraph.
        Returns:
        the number of vertices in this digraph

      • E

        public int E()
        Returns the number of edges in this digraph.
        Returns:
        the number of edges in this digraph

      • addEdge

        public void addEdge​(int v,
                    int w)
        Adds the directed edge v→w to this digraph.
        Parameters:
        v - the tail vertex
        w - the head vertex
        Throws:
        IllegalArgumentException - unless both 0 <= v < V and 0 <= w < V

      • adj

        public Iterable<Integer> adj​(int v)
        Returns the vertices adjacent from vertex v in this digraph.
        Parameters:
        v - the vertex
        Returns:
        the vertices adjacent from vertex v in this digraph, as an iterable
        Throws:
        IllegalArgumentException - 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 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()
        Returns the reverse of the digraph.
        Returns:
        the reverse of the digraph

      • toString

        public String toString()
        Returns a string representation of the graph.
        Overrides:
        toString in class Object
        Returns:
        the number of vertices V, followed by the number of edges E, followed by the V adjacency lists

      • main

        public static void main​(String[] args)
        Unit tests the Digraph data type.
        Parameters:
        args - the command-line arguments