com.mhhe.clrs2e
Class WeightedAdjacencyMatrixGraph

java.lang.Object
  |
  +--com.mhhe.clrs2e.AdjacencyMatrixGraph
        |
        +--com.mhhe.clrs2e.WeightedAdjacencyMatrixGraph

All Implemented Interfaces:

Graph

public class WeightedAdjacencyMatrixGraph

extends AdjacencyMatrixGraph

Implementation of a weighted graph, using an adjacency matrix. The representation and use are related to the superclass AdjacencyMatrixGraph. The primary difference is that here the 2-dimensional matrix a is of double rather than of boolean, where the matrix entry a[u][v] contains the weight of edge (u,v). There is also an instance variable absentValue; if a[u][v] equals absentValue, then edge (u,v) is not present in the graph. Also, 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

WeightedAdjacencyMatrixGraph.EdgeIterator Inner class that overrides AdjacencyListGraph.EdgeIterator to implement WeightedEdgeIterator.

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

AdjacencyMatrixGraph.VertexIterator

Field Summary

protected double[][]	a Weighted adjacency matrix; a[u][v] is the weight of edge (u,v).
protected double	absentValue The value indicating an absent edge; if a[u][v] equals absentValue, then edge (u,v) is not present in the graph.

Fields inherited from class com.mhhe.clrs2e.AdjacencyMatrixGraph

directed, e, lastAdded, vertices

Constructor Summary

WeightedAdjacencyMatrixGraph(int cardV, boolean directed, double absent)
Creates an empty WeightedAdjacencyMatrixGraph.

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.
boolean	edgeExists(int u, int v) Returns a flag indicating whether an edge exists.
boolean	edgeExists(com.mhhe.clrs2e.Vertex u, com.mhhe.clrs2e.Vertex v) Returns a flag indicating whether an edge exists.
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.
double	getWeight(int u, int v) Returns the weight of an edge.
double	getWeight(com.mhhe.clrs2e.Vertex u, com.mhhe.clrs2e.Vertex v) Returns the weight of an edge.
java.lang.String	toString() Returns the String representation of this 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.AdjacencyMatrixGraph

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

Methods inherited from class java.lang.Object

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

Field Detail

a

protected double[][] a

Weighted adjacency matrix; a[u][v] is the weight of edge (u,v).

absentValue

protected double absentValue

The value indicating an absent edge; if a[u][v] equals absentValue, then edge (u,v) is not present in the graph.

Constructor Detail

WeightedAdjacencyMatrixGraph

public WeightedAdjacencyMatrixGraph(int cardV,
                                    boolean directed,
                                    double absent)

Creates an empty WeightedAdjacencyMatrixGraph.

Parameters:

cardV - How many vertices this graph will have.

directed - Flag indicating whether this graph is directed.

absent - The value that indicates an absent edge.

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 AdjacencyMatrixGraph

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 AdjacencyMatrixGraph

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 AdjacencyMatrixGraph

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 AdjacencyMatrixGraph

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.

edgeExists

public boolean edgeExists(com.mhhe.clrs2e.Vertex u,
                          com.mhhe.clrs2e.Vertex v)

Returns a flag indicating whether an edge exists. The edge is specified as a pair of Vertex objects.

Overrides:

edgeExists in class AdjacencyMatrixGraph

Parameters:

u - One endpoint of the edge.

v - The other endpoint of the edge.

edgeExists

public boolean edgeExists(int u,
                          int v)

Returns a flag indicating whether an edge exists. The edge is specified as a pair of vertex indices.

Overrides:

edgeExists in class AdjacencyMatrixGraph

Parameters:

u - One endpoint of the edge.

v - The other endpoint of the edge.

getWeight

public double getWeight(com.mhhe.clrs2e.Vertex u,
                        com.mhhe.clrs2e.Vertex v)

Returns the weight of an edge. The edge is specified as a pair of Vertex objects.

Parameters:

u - One endpoint of the edge.

v - The other endpoint of the edge.

getWeight

public double getWeight(int u,
                        int v)

Returns the weight of an edge. The edge is specified as a pair of vertex indices.

Parameters:

u - One endpoint of the edge.

v - The other endpoint of the edge.

toString

public java.lang.String toString()

Returns the String representation of this graph.

Overrides:

toString in class AdjacencyMatrixGraph