Package edu.princeton.cs.algs4
Class Digraph
 Object

 edu.princeton.cs.algs4.Digraph

public class Digraph extends Object
TheDigraph
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 selfloops are permitted.This implementation uses an adjacencylists representation, which is a vertexindexed array of
Bag
objects. It uses Θ(E + V) space, where E is the number of edges and V is the number of vertices. Thereverse()
method takes Θ(E + V) time and space; all other instance methods take Θ(1) time. (Though, iterating over the vertices returned byadj(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


Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method 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 vertexv
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 vertexv
.static void
main(String[] args)
Unit tests theDigraph
data type.int
outdegree(int v)
Returns the number of directed edges incident from vertexv
.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.



Constructor Detail

Digraph
public Digraph(int V)
Initializes an empty digraph with V vertices. Parameters:
V
 the number of vertices Throws:
IllegalArgumentException
 ifV < 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
 ifin
isnull
IllegalArgumentException
 if the endpoints of any edge are not in prescribed rangeIllegalArgumentException
 if the number of vertices or edges is negativeIllegalArgumentException
 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
 ifG
isnull


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 vertexw
 the head vertex Throws:
IllegalArgumentException
 unless both0 <= v < V
and0 <= w < V

adj
public Iterable<Integer> adj(int v)
Returns the vertices adjacent from vertexv
in this digraph. Parameters:
v
 the vertex Returns:
 the vertices adjacent from vertex
v
in this digraph, as an iterable  Throws:
IllegalArgumentException
 unless0 <= v < V

outdegree
public int outdegree(int v)
Returns the number of directed edges incident from vertexv
. This is known as the outdegree of vertexv
. Parameters:
v
 the vertex Returns:
 the outdegree of vertex
v
 Throws:
IllegalArgumentException
 unless0 <= v < V

indegree
public int indegree(int v)
Returns the number of directed edges incident to vertexv
. This is known as the indegree of vertexv
. Parameters:
v
 the vertex Returns:
 the indegree of vertex
v
 Throws:
IllegalArgumentException
 unless0 <= 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.

main
public static void main(String[] args)
Unit tests theDigraph
data type. Parameters:
args
 the commandline arguments

