edu.princeton.cs.algorithms

Class EdgeWeightedDigraph

java.lang.Object

edu.princeton.cs.algorithms.EdgeWeightedDigraph

public class EdgeWeightedDigraph
extends 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 @link{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.

Author:

Robert Sedgewick, 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(edu.princeton.cs.introcs.In in) Initializes an edge-weighted digraph from an 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

Methods

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

Methods inherited from class java.lang.Object

clone, equals, finalize, 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. param V the number of vertices

Throws:

IllegalArgumentException - if V < 0

EdgeWeightedDigraph

public EdgeWeightedDigraph(int V,
                   int E)

Initializes a random edge-weighted digraph with V vertices and E edges. param V the number of vertices param E the number of edges

Throws:

IllegalArgumentException - if V < 0

IllegalArgumentException - if E < 0

EdgeWeightedDigraph

public EdgeWeightedDigraph(edu.princeton.cs.introcs.In in)

Initializes an edge-weighted 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 and edge weights, 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

EdgeWeightedDigraph

public EdgeWeightedDigraph(EdgeWeightedDigraph G)

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

Parameters:

G - the edge-weighted graph to copy

Method Detail

V

public int V()

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

Returns:

the number of vertices in the edge-weighted digraph

E

public int E()

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

Returns:

the number of edges in the edge-weighted digraph

addEdge

public void addEdge(DirectedEdge e)

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

Parameters:

e - the edge

adj

public 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:

IndexOutOfBoundsException - unless 0 <= v < V

edges

public Iterable<DirectedEdge> edges()

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

Returns:

all edges in the edge-weighted graph as an Iterable.

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 number of directed edges incident from vertex v

Throws:

IndexOutOfBoundsException - unless 0 <= v < V

toString

public String toString()

Returns a string representation of the edge-weighted digraph. 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 of edges

main

public static void main(String[] args)

Unit tests the EdgeWeightedDigraph data type.