AdjacencyMatrixGraph

Package

Class

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

com.mhhe.clrs2e
Class AdjacencyMatrixGraph

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

All Implemented Interfaces:: Graph

Direct Known Subclasses:: WeightedAdjacencyMatrixGraph

public class AdjacencyMatrixGraph
extends java.lang.Object
implements Graph

Implementation of a graph, using an adjacency matrix.

The number of vertices, cardV, is specified in the constructor call, as is a flag indicating whether the graph is directed. The constructor creates two arrays: an array vertices of Vertex objects with length cardV, and the adjacency matrix (a cardV x cardV 2-dimensional array) a of boolean. When the graph is fully defined, each object in the vertices array references a Vertex object, and the matrix entry a[u][v] is true if and only if edge (u,v) is present in this graph, where u and v are vertex indices. We reference a Vertex object in each entry of vertices so that we can determine which vertex we're looking at as we traverse the vertices array.

If the graph is directed, then adding an edge (u,v) adds just (u,v). If, on the other hand, the graph is undirected, then adding an edge (u,v) also adds the edge (v,u). If the graph is undirected, therefore, do not call addEdge(u, v) and also addEdge(v, u).

In method calls that require vertex arguments, you may refer to a vertex either by its index (0 to cardV-1) or a reference to a Vertex object. (In method calls that require two vertices as arguments, both must be indices or both must be references to Vertex objects.) When adding vertices to the graph via the addVertex methods, you may specify just the vertex's name, the name and index, or a Vertex object. If you give just the name, or you specify a Vertex object that does not have an index, the index used will be 1 greater than the index of the previous vertex added. (An index of 0 is used for the first vertex added.)

The normal way to create a graph is to first call the constructor, then perform a sequence of addVertex calls to define the vertices, and finally perform a sequence of addEdge calls to define the edges in terms of the added vertices.

This class provides two types of iterators: for iterating through all the vertices and for iterating through the edges incident on a given vertex. The usual way of using these iterators is by the following schema, where g references the graph:

Iterator vertexIter = g.vertexIterator(); while (vertexIter.hasNext()) { Vertex u = (Vertex) vertexIter.next(); Iterator edgeIter = g.edgeIterator(u); while (edgeIter.hasNext()) { Vertex v = (Vertex) edgeIter.next(); // Code that operates on edge (u,v) goes here. } }

Nested Class Summary

class AdjacencyMatrixGraph.EdgeIterator
          Inner class for an iterator that iterates through the edges incident on a given vertex.

class AdjacencyMatrixGraph.VertexIterator
          Inner class for a vertex iterator.

Field Summary

protected boolean[][] a
          The adjacency matrix.

protected boolean directed
          true if this graph is directed, false if undirected.

protected int e
          How many edges this graph has.

protected int lastAdded
          The index of the last vertex added to this graph.

protected com.mhhe.clrs2e.Vertex[] vertices
          An array of all the vertices in this graph.

Constructor Summary

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

Method Summary

void addEdge(int u, int v)
          Adds an edge to this graph.

void addEdge(com.mhhe.clrs2e.Vertex u, com.mhhe.clrs2e.Vertex v)
          Adds an edge to this graph.

com.mhhe.clrs2e.Vertex addVertex(int index, java.lang.String name)
          Adds a vertex to this graph.

com.mhhe.clrs2e.Vertex addVertex(java.lang.String name)
          Adds a vertex to this graph.

com.mhhe.clrs2e.Vertex addVertex(com.mhhe.clrs2e.Vertex v)
          Adds a vertex to this graph, given a Vertex.

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 edges incident on a given vertex.

java.util.Iterator edgeIterator(com.mhhe.clrs2e.Vertex u)
          Returns an iterator that iterates through the edges incident on a given vertex.

int getCardE()
          Returns the number of edges in this graph.

int getCardV()
          Returns the number of vertices in this graph.

com.mhhe.clrs2e.Vertex getVertex(int index)
          Returns the vertex with a given index.

boolean isDirected()
          Returns true if this graph is directed, false if undirected.

java.lang.String toString()
          Returns the String representation of this graph.

java.util.Iterator vertexIterator()
          Returns an iterator that iterates though all the vertices in the graph.

Methods inherited from class java.lang.Object

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

Field Detail

directed

protected boolean directed

true if this graph is directed, false if undirected.

lastAdded

protected int lastAdded

The index of the last vertex added to this graph.

e

protected int e

How many edges this graph has.

vertices

protected com.mhhe.clrs2e.Vertex[] vertices

An array of all the vertices in this graph.

a

protected boolean[][] a

The adjacency matrix.

Constructor Detail