Digraph (Algorithms 4/e)

Object
- edu.princeton.cs.algs4.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 instancce 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 and Description
`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.
`Digraph(int V)` Initializes an empty digraph with V vertices.

Method Summary

All Methods Static Methods Instance Methods Concrete Methods
Modifier and Type	Method and Description
`void`	`addEdge(int v, int w)` Adds the directed edge v→w to this digraph.
`Iterable<Integer>`	`adj(int v)` Returns the vertices adjacent from vertex `v` in this digraph.
`int`	`E()` Returns the number of edges in this digraph.
`int`	`indegree(int v)` Returns the number of directed edges incident to vertex `v`.
`static void`	`main(String[] args)` Unit tests the `Digraph` data type.
`int`	`outdegree(int v)` Returns the number of directed edges incident from vertex `v`.
`Digraph`	`reverse()` Returns the reverse of the digraph.
`String`	`toString()` Returns a string representation of the graph.
`int`	`V()` Returns the number of vertices in this digraph.

Methods inherited from class Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

- 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

Class Digraph

Constructor Summary

Method Summary

Methods inherited from class Object

Constructor Detail

Digraph

Digraph

Digraph

Method Detail

V

E

addEdge

adj

outdegree

indegree

reverse

toString

main