edu.princeton.cs.algorithms

Class EdgeWeightedGraph

java.lang.Object

edu.princeton.cs.algorithms.EdgeWeightedGraph

public class EdgeWeightedGraph
extends 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.

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 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.

Author:

Robert Sedgewick, 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(edu.princeton.cs.introcs.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

Methods

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

Methods inherited from class java.lang.Object

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

Throws:

IllegalArgumentException - if V < 0

EdgeWeightedGraph

public EdgeWeightedGraph(int V,
                 int E)

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

EdgeWeightedGraph

public EdgeWeightedGraph(edu.princeton.cs.introcs.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:

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

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 the edge-weighted graph.

Returns:

the number of vertices in the edge-weighted graph

E

public int E()

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

Returns:

the number of edges in the edge-weighted graph

addEdge

public void addEdge(Edge e)

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

Parameters:

e - the edge

Throws:

IndexOutOfBoundsException - unless both endpoints are between 0 and V-1

adj

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

IndexOutOfBoundsException - unless 0 <= v < V

edges

public Iterable<Edge> edges()

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

Returns:

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

toString

public String toString()

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

main

public static void main(String[] args)

Unit tests the EdgeWeightedGraph data type.