edu.princeton.cs.algs4

Class EdgeWeightedGraph

java.lang.Object

edu.princeton.cs.algs4.EdgeWeightedGraph

public class EdgeWeightedGraph
extends java.lang.Object

The EdgeWeightedGraph class represents an edge-weighted graph of vertices named 0 through V – 1, where each undirected edge is of type Edge and has a real-valued weight. It supports the following two primary operations: add an edge to the graph, iterate over all of the edges incident to a 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. By convention, a self-loop v-v appears in the adjacency list of v twice and contributes two to the degree of v.

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 to a given vertex, which takes time proportional to the number of such edges.

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

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
void	addEdge(Edge e) Adds the undirected edge e to this edge-weighted graph.
java.lang.Iterable<Edge>	adj(int v) Returns the edges incident on vertex v.
int	degree(int v) Returns the degree of vertex v.
int	E() Returns the number of edges in this edge-weighted graph.
java.lang.Iterable<Edge>	edges() Returns all edges in this edge-weighted graph.
static void	main(java.lang.String[] args) Unit tests the EdgeWeightedGraph data type.
java.lang.String	toString() Returns a string representation of the edge-weighted graph.
int	V() Returns the number of vertices in this edge-weighted graph.

Methods inherited from class java.lang.Object

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

Constructor Detail

EdgeWeightedGraph

public EdgeWeightedGraph(int V)

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

Parameters:

V - the number of vertices

Throws:

java.lang.IllegalArgumentException - if V < 0

EdgeWeightedGraph

public EdgeWeightedGraph(int V,
                         int E)

Initializes a random edge-weighted graph 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

EdgeWeightedGraph

public EdgeWeightedGraph(In in)

Initializes an edge-weighted graph 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:

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

EdgeWeightedGraph

public EdgeWeightedGraph(EdgeWeightedGraph G)

Initializes a new edge-weighted graph 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 this edge-weighted graph.

Returns:

the number of vertices in this edge-weighted graph

E

public int E()

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

Returns:

the number of edges in this edge-weighted graph

addEdge

public void addEdge(Edge e)

Adds the undirected edge e to this edge-weighted graph.

Parameters:

e - the edge

Throws:

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

adj

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

Returns the edges incident on vertex v.

Parameters:

v - the vertex

Returns:

the edges incident on vertex v as an Iterable

Throws:

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

degree

public int degree(int v)

Returns the degree of vertex v.

Parameters:

v - the vertex

Returns:

the degree of vertex v

Throws:

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

edges

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

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

Returns:

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

toString

public java.lang.String toString()

Returns a string representation of the edge-weighted graph. This method takes time proportional to E + V.

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 EdgeWeightedGraph data type.

Parameters:

args - the command-line arguments