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

      • toDot

        public String toDot()
        Returns a string representation of this digraph in DOT format, suitable for visualization with Graphviz. To visualize the digraph, install Graphviz (e.g., "brew install graphviz"). Then use one of the graph visualization tools - dot (hierarchical or layer drawing) - neato (spring model) - fdp (force-directed placement) - sfdp (scalable force-directed placement) - twopi (radial layout) For example, the following commands will create graph drawings in SVG and PDF formats - dot input.dot -Tsvg -o output.svg - dot input.dot -Tpdf -o output.pdf To change the digraph attributes (e.g., vertex and edge shapes, arrows, colors) in the DOT format, see https://graphviz.org/doc/info/lang.html
        Returns:
        a string representation of this digraph in DOT format

      • main

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