Package edu.princeton.cs.algs4
Class EdgeWeightedDigraph
 Object

 edu.princeton.cs.algs4.EdgeWeightedDigraph

public class EdgeWeightedDigraph extends Object
TheEdgeWeightedDigraph
class represents an edgeweighted digraph of vertices named 0 through V  1, where each directed edge is of typeDirectedEdge
and has a realvalued weight. It supports the following two primary operations: add a directed edge to the digraph and iterate over all edges incident 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, and the number of edges E in the 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. All instance methods take Θ(1) time. (Though, iterating over the edges returned byadj(int)
takes time proportional to the outdegree of the vertex.) Constructing an empty edgeweighted digraph with V vertices takes Θ(V) time; constructing an edgeweighted digraph with E edges and V vertices takes Θ(E + V) time.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 Description EdgeWeightedDigraph(int V)
Initializes an empty edgeweighted digraph withV
vertices and 0 edges.EdgeWeightedDigraph(int V, int E)
Initializes a random edgeweighted digraph withV
vertices and E edges.EdgeWeightedDigraph(EdgeWeightedDigraph G)
Initializes a new edgeweighted digraph that is a deep copy ofG
.EdgeWeightedDigraph(In in)
Initializes an edgeweighted digraph from the specified input stream.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description void
addEdge(DirectedEdge e)
Adds the directed edgee
to this edgeweighted digraph.Iterable<DirectedEdge>
adj(int v)
Returns the directed edges incident from vertexv
.int
E()
Returns the number of edges in this edgeweighted digraph.Iterable<DirectedEdge>
edges()
Returns all directed edges in this edgeweighted digraph.int
indegree(int v)
Returns the number of directed edges incident to vertexv
.static void
main(String[] args)
Unit tests theEdgeWeightedDigraph
data type.int
outdegree(int v)
Returns the number of directed edges incident from vertexv
.String
toString()
Returns a string representation of this edgeweighted digraph.int
V()
Returns the number of vertices in this edgeweighted digraph.



Constructor Detail

EdgeWeightedDigraph
public EdgeWeightedDigraph(int V)
Initializes an empty edgeweighted digraph withV
vertices and 0 edges. Parameters:
V
 the number of vertices Throws:
IllegalArgumentException
 ifV < 0

EdgeWeightedDigraph
public EdgeWeightedDigraph(int V, int E)
Initializes a random edgeweighted digraph withV
vertices and E edges. Parameters:
V
 the number of verticesE
 the number of edges Throws:
IllegalArgumentException
 ifV < 0
IllegalArgumentException
 ifE < 0

EdgeWeightedDigraph
public EdgeWeightedDigraph(In in)
Initializes an edgeweighted 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:
IllegalArgumentException
 ifin
isnull
IllegalArgumentException
 if the endpoints of any edge are not in prescribed rangeIllegalArgumentException
 if the number of vertices or edges is negative

EdgeWeightedDigraph
public EdgeWeightedDigraph(EdgeWeightedDigraph G)
Initializes a new edgeweighted digraph that is a deep copy ofG
. Parameters:
G
 the edgeweighted digraph to copy


Method Detail

V
public int V()
Returns the number of vertices in this edgeweighted digraph. Returns:
 the number of vertices in this edgeweighted digraph

E
public int E()
Returns the number of edges in this edgeweighted digraph. Returns:
 the number of edges in this edgeweighted digraph

addEdge
public void addEdge(DirectedEdge e)
Adds the directed edgee
to this edgeweighted digraph. Parameters:
e
 the edge Throws:
IllegalArgumentException
 unless endpoints of edge are between0
andV1

adj
public Iterable<DirectedEdge> adj(int v)
Returns the directed edges incident from vertexv
. Parameters:
v
 the vertex Returns:
 the directed edges incident from vertex
v
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

edges
public Iterable<DirectedEdge> edges()
Returns all directed edges in this edgeweighted digraph. To iterate over the edges in this edgeweighted digraph, use foreach notation:for (DirectedEdge e : G.edges())
. Returns:
 all edges in this edgeweighted digraph, as an iterable

toString
public String toString()
Returns a string representation of this edgeweighted digraph.

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

