com.mhhe.clrs2e
Class WeightedAdjacencyListGraph

java.lang.Object
  |
  +--com.mhhe.clrs2e.AdjacencyListGraph
        |
        +--com.mhhe.clrs2e.WeightedAdjacencyListGraph

All Implemented Interfaces:

Graph

public class WeightedAdjacencyListGraph

extends AdjacencyListGraph

Implementation of a weighted graph, using adjacency lists. The representation and use are similar to the superclass AdjacencyListGraph. The primary difference is that the inner class AdjacencyListGraph.Edge is subclassed here as WeightedAdjacencyListGraph.WeightedEdge, and objects of this subclass include a weight. The inner WeightedAdjacencyListGraph.EdgeIterator class overrides the AdjacencyListGraph.EdgeIterator class and implements the WeightedEdgeIterator interface, so that edge weights can be get and set during iterations through edges.

Nested Class Summary

class	WeightedAdjacencyListGraph.EdgeIterator Inner class that overrides AdjacencyListGraph.EdgeIterator to implement WeightedEdgeIterator.
protected static class	WeightedAdjacencyListGraph.WeightedEdge Inner class for weighted edges in adjacency lists.

Nested classes inherited from class com.mhhe.clrs2e.AdjacencyListGraph

AdjacencyListGraph.AdjListInfo, AdjacencyListGraph.VertexIterator

Field Summary

Fields inherited from class com.mhhe.clrs2e.AdjacencyListGraph

adj, directed, e, lastAdded

Constructor Summary

WeightedAdjacencyListGraph(int cardV, boolean directed)
Creates an empty WeightedAdjacencyListGraph.

Method Summary

void	addEdge(int u, int v) Unsupported, since edges in a weighted graph must have weights.
void	addEdge(int u, int v, double weight) Adds a weighted edge to this graph.
void	addEdge(com.mhhe.clrs2e.Vertex u, com.mhhe.clrs2e.Vertex v) Unsupported, since edges in a weighted graph must have weights.
void	addEdge(com.mhhe.clrs2e.Vertex u, com.mhhe.clrs2e.Vertex v, double weight) Adds a weighted edge to this graph.
java.util.Iterator	edgeIterator(int u) Returns an iterator that iterates through the weighted edges incident on a given vertex.
java.util.Iterator	edgeIterator(com.mhhe.clrs2e.Vertex u) Returns an iterator that iterates through the weighted edges incident on a given vertex.
protected com.mhhe.clrs2e.AdjacencyListGraph	makeEmptyGraph(int cardV, boolean directed) Creates and returns an empty WeightedAdjacencyListGraph with no edges, given the number of vertices and a boolean indicating whether the graph is directed.
java.lang.String	toString() Returns the String representation of this weighted graph.
com.mhhe.clrs2e.WeightedEdgeIterator	weightedEdgeIterator(int u) Returns an iterator, of type WeightedEdgeIterator (so that the caller does not need to cast the result), that iterates through the weighted edges incident on a given vertex.
com.mhhe.clrs2e.WeightedEdgeIterator	weightedEdgeIterator(com.mhhe.clrs2e.Vertex u) Returns an iterator, of type WeightedEdgeIterator (so that the caller does not need to cast the result), that iterates through the weighted edges incident on a given vertex.

Methods inherited from class com.mhhe.clrs2e.AdjacencyListGraph

addVertex, addVertex, addVertex, getCardE, getCardV, getVertex, isDirected, useSameVertices, vertexIterator

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

WeightedAdjacencyListGraph

public WeightedAdjacencyListGraph(int cardV,
                                  boolean directed)

Creates an empty WeightedAdjacencyListGraph.

Parameters:

cardV - How many vertices this graph will have.

directed - Flag indicating whether this graph is directed.

Method Detail

addEdge

public void addEdge(com.mhhe.clrs2e.Vertex u,
                    com.mhhe.clrs2e.Vertex v)

Unsupported, since edges in a weighted graph must have weights.

Specified by:

addEdge in interface Graph

Overrides:

addEdge in class AdjacencyListGraph

Parameters:

u - One vertex.

v - The other vertex.

Throws:

java.lang.UnsupportedOperationException - always.

addEdge

public void addEdge(int u,
                    int v)

Unsupported, since edges in a weighted graph must have weights.

Specified by:

addEdge in interface Graph

Overrides:

addEdge in class AdjacencyListGraph

Parameters:

u - The index of one vertex.

v - The index of the other vertex.

Throws:

java.lang.UnsupportedOperationException - always.

addEdge

public void addEdge(com.mhhe.clrs2e.Vertex u,
                    com.mhhe.clrs2e.Vertex v,
                    double weight)

Adds a weighted edge to this graph. The edge is specified by a pair of Vertex objects.

Parameters:

u - One vertex.

v - The other vertex.

weight - The weight of the edge.

addEdge

public void addEdge(int u,
                    int v,
                    double weight)

Adds a weighted edge to this graph. The edge is specified by a pair of vertex indices.

Parameters:

u - The index of one vertex.

v - The index of the other vertex.

weight - The weight of the edge.

edgeIterator

public java.util.Iterator edgeIterator(com.mhhe.clrs2e.Vertex u)

Returns an iterator that iterates through the weighted edges incident on a given vertex. Each incident edge is indicated by the corresponding adjacent vertex.

Specified by:

edgeIterator in interface Graph

Overrides:

edgeIterator in class AdjacencyListGraph

Parameters:

u - The vertex whose incident edges are returned by the iterator.

edgeIterator

public java.util.Iterator edgeIterator(int u)

Returns an iterator that iterates through the weighted edges incident on a given vertex. Each incident edge is indicated by the corresponding adjacent vertex.

Specified by:

edgeIterator in interface Graph

Overrides:

edgeIterator in class AdjacencyListGraph

Parameters:

u - The index of the vertex whose incident edges are returned by the iterator.

weightedEdgeIterator

public com.mhhe.clrs2e.WeightedEdgeIterator weightedEdgeIterator(com.mhhe.clrs2e.Vertex u)

Returns an iterator, of type WeightedEdgeIterator (so that the caller does not need to cast the result), that iterates through the weighted edges incident on a given vertex. Each incident edge is indicated by the corresponding adjacent vertex.

Parameters:

u - The vertex whose incident edges are returned by the iterator.

weightedEdgeIterator

public com.mhhe.clrs2e.WeightedEdgeIterator weightedEdgeIterator(int u)

Returns an iterator, of type WeightedEdgeIterator (so that the caller does not need to cast the result), that iterates through the weighted edges incident on a given vertex. Each incident edge is indicated by the corresponding adjacent vertex.

Parameters:

u - The index of the vertex whose incident edges are returned by the iterator.

makeEmptyGraph

protected com.mhhe.clrs2e.AdjacencyListGraph makeEmptyGraph(int cardV,
                                                            boolean directed)

Creates and returns an empty WeightedAdjacencyListGraph with no edges, given the number of vertices and a boolean indicating whether the graph is directed.

Overrides:

makeEmptyGraph in class AdjacencyListGraph

Parameters:

cardV - How many vertices in the new graph.

directed - Flag indicating whether this graph is directed.

toString

public java.lang.String toString()

Returns the String representation of this weighted graph.

Overrides:

toString in class AdjacencyListGraph