edu.princeton.cs.algs4

Class EdgeWeightedDigraph

java.lang.Object

edu.princeton.cs.algs4.EdgeWeightedDigraph

public class EdgeWeightedDigraph
extends java.lang.Object

The EdgeWeightedDigraph class represents a edge-weighted digraph of vertices named 0 through V - 1, where each directed edge is of type DirectedEdge and has a real-valued weight. It supports the following two primary operations: add a directed edge to the digraph and iterate over all of edges incident from a given vertex. It also provides methods for returning the number of vertices V and the number of edges E. 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 edges incident from a given vertex, which takes time proportional to the number of such edges.

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

Constructor Summary

Constructors

Constructor and Description
EdgeWeightedDigraph(EdgeWeightedDigraph G) Initializes a new edge-weighted digraph that is a deep copy of G.
EdgeWeightedDigraph(In in) Initializes an edge-weighted digraph from the specified input stream.
EdgeWeightedDigraph(int V) Initializes an empty edge-weighted digraph with V vertices and 0 edges.
EdgeWeightedDigraph(int V, int E) Initializes a random edge-weighted digraph with V vertices and E edges.

Method Summary

Modifier and Type	Method and Description
void	addEdge(DirectedEdge e) Adds the directed edge e to this edge-weighted digraph.
java.lang.Iterable<DirectedEdge>	adj(int v) Returns the directed edges incident from vertex v.
int	E() Returns the number of edges in this edge-weighted digraph.
java.lang.Iterable<DirectedEdge>	edges() Returns all directed edges in this edge-weighted digraph.
int	indegree(int v) Returns the number of directed edges incident to vertex v.
static void	main(java.lang.String[] args) Unit tests the EdgeWeightedDigraph data type.
int	outdegree(int v) Returns the number of directed edges incident from vertex v.
java.lang.String	toString() Returns a string representation of this edge-weighted digraph.
int	V() Returns the number of vertices in this edge-weighted digraph.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

EdgeWeightedDigraph

public EdgeWeightedDigraph(int V)

Initializes an empty edge-weighted digraph with V vertices and 0 edges.

Parameters:

V - the number of vertices

Throws:

java.lang.IllegalArgumentException - if V < 0

EdgeWeightedDigraph

public EdgeWeightedDigraph(int V,
                           int E)

Initializes a random edge-weighted digraph with V vertices and E edges.

Parameters:

V - the number of vertices

E - the number of edges

Throws:

java.lang.IllegalArgumentException - if V < 0

java.lang.IllegalArgumentException - if E < 0

EdgeWeightedDigraph

public EdgeWeightedDigraph(In in)

Initializes an edge-weighted 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 and edge weights, with each entry separated by whitespace.

Parameters:

in - the input stream

Throws:

java.lang.IllegalArgumentException - if the endpoints of any edge are not in prescribed range

java.lang.IllegalArgumentException - if the number of vertices or edges is negative

EdgeWeightedDigraph

public EdgeWeightedDigraph(EdgeWeightedDigraph G)

Initializes a new edge-weighted digraph that is a deep copy of G.

Parameters:

G - the edge-weighted digraph to copy

Method Detail

V

public int V()

Returns the number of vertices in this edge-weighted digraph.

Returns:

the number of vertices in this edge-weighted digraph

E

public int E()

Returns the number of edges in this edge-weighted digraph.

Returns:

the number of edges in this edge-weighted digraph

addEdge

public void addEdge(DirectedEdge e)

Adds the directed edge e to this edge-weighted digraph.

Parameters:

e - the edge

Throws:

java.lang.IllegalArgumentException - unless endpoints of edge are between 0 and V-1

adj

public java.lang.Iterable<DirectedEdge> adj(int v)

Returns the directed edges incident from vertex v.

Parameters:

v - the vertex

Returns:

the directed edges incident from vertex v as an Iterable

Throws:

java.lang.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:

java.lang.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:

java.lang.IllegalArgumentException - unless 0 <= v < V

edges

public java.lang.Iterable<DirectedEdge> edges()

Returns all directed edges in this edge-weighted digraph. To iterate over the edges in this edge-weighted digraph, use foreach notation: for (DirectedEdge e : G.edges()).

Returns:

all edges in this edge-weighted digraph, as an iterable

toString

public java.lang.String toString()

Returns a string representation of this edge-weighted digraph.

Overrides:

toString in class java.lang.Object

Returns:

the number of vertices V, followed by the number of edges E, followed by the V adjacency lists of edges

main

public static void main(java.lang.String[] args)

Unit tests the EdgeWeightedDigraph data type.

Parameters:

args - the command-line arguments