edu.princeton.cs.algs4

## Class Digraph

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

```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`

`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