edu.princeton.cs.algorithms

Class Digraph

java.lang.Object

edu.princeton.cs.algorithms.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. Parallel edges and self-loops are permitted.

This implementation uses an adjacency-lists representation, which is a vertex-indexed array of Bag objects. All operations take constant time (in the worst case) except iterating over the vertices adjacent from a given vertex, which takes time proportional to the number of such vertices.

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 G.
Digraph(edu.princeton.cs.introcs.In in) Initializes a digraph from an input stream.
Digraph(int V) Initializes an empty digraph with V vertices.

Method Summary

Methods

Modifier and Type	Method and Description
void	addEdge(int v, int w) Adds the directed edge v->w to the digraph.
Iterable<Integer>	adj(int v) Returns the vertices adjacent from vertex v in the digraph.
int	E() Returns the number of edges in the digraph.
static void	main(String[] args) Unit tests the Digraph data type.
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 the digraph.

Methods inherited from class java.lang.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(edu.princeton.cs.introcs.In in)

Initializes a digraph from an 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:

IndexOutOfBoundsException - if the endpoints of any edge are not in prescribed range

IllegalArgumentException - if the number of vertices or edges is negative

Digraph

public Digraph(Digraph G)

Initializes a new digraph that is a deep copy of G.

Parameters:

G - the digraph to copy

Method Detail

V

public int V()

Returns the number of vertices in the digraph.

Returns:

the number of vertices in the digraph

E

public int E()

Returns the number of edges in the digraph.

Returns:

the number of edges in the digraph

addEdge

public void addEdge(int v,
           int w)

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

Parameters:

v - the tail vertex

w - the head vertex

Throws:

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

adj

public Iterable<Integer> adj(int v)

Returns the vertices adjacent from vertex v in the digraph.

Parameters:

v - the vertex

Returns:

the vertices adjacent from vertex v in the digraph, as an Iterable

Throws:

IndexOutOfBoundsException - 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. This method takes time proportional to E + V.

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.