Package algs42

Class Digraph

java.lang.Object

algs42.Digraph

public class Digraph
extends Object

The Digraph class represents an directed graph of vertices named 0 through V-1. It supports the following operations: add an edge to the graph, iterate over all of the neighbors incident to a vertex. Parallel edges and self-loops are permitted.

For additional documentation, see Section 5.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Field Summary

Fields

Modifier and Type	Field	Description
private final Bag<Integer>[]	adj
private int	E
private int[]	indegree
private final int	V

Constructor Summary

Constructors

Constructor	Description
Digraph(int V)	Create 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.

Method Summary

Modifier and Type	Method	Description
void	addEdge(int v, int w)	Add the directed edge v->w to the digraph.
Iterable<Integer>	adj(int v)	Return the list of vertices pointed to from vertex v as an Iterable.
int	E()	Return the number of edges in the digraph.
int	indegree(int v)	Returns the number of directed edges incident to vertex v.
static void	main(String[] args)	Test client.
int	outdegree(int v)	Returns the number of directed edges incident from vertex v.
Digraph	reverse()	Return the reverse of the digraph.
void	toGraphviz(String filename)	Save a graphviz representation of the graph.
String	toString()	Return a string representation of the digraph.
int	V()	Return the number of vertices in the digraph.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Details

V

private final int V

E

private int E

adj

private final Bag<Integer>[] adj

indegree

private int[] indegree

Constructor Details

Digraph

public Digraph(int V)

Create an empty digraph with V vertices.

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 Details

V

public int V()

Return the number of vertices in the digraph.

E

public int E()

Return the number of edges in the digraph.

addEdge

public void addEdge(int v,
 int w)

Add the directed edge v->w to the digraph.

Throws:

IndexOutOfBoundsException - unless both 0 <= v < V and 0 <= w < V

adj

public Iterable<Integer> adj(int v)

Return the list of vertices pointed to from vertex v as an Iterable.

Throws:

IndexOutOfBoundsException - 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 {@code 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()

Return the reverse of the digraph.

toString

public String toString()

Return a string representation of the digraph.

Overrides:

toString in class Object

toGraphviz

public void toGraphviz(String filename)

Save a graphviz representation of the graph. See graphviz.org.

main

public static void main(String[] args)

Test client.