AdjacencyListGraph

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 AdjacencyListGraph

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

All Implemented Interfaces:: Graph

Direct Known Subclasses:: FlowNetwork, WeightedAdjacencyListGraph

public class AdjacencyListGraph
extends java.lang.Object
implements Graph

Implementation of a graph, using adjacency lists.

The number of vertices, cardV, is specified in the constructor call, as is a flag indicating whether the graph is directed. The constructor creates an array adj of cardV objects. When the graph is fully defined, each object in the adj array is an AdjacencyListGraph.AdjListInfo object, consisting of a Vertex and a reference to the first edge in the list of edges incident on the vertex. We reference a Vertex object in each entry of adj so that we can determine which vertex we're looking at as we traverse the adj array.

Each edge is defined by an AdjacencyListGraph.Edge object, which contains a reference to a Vertex (indicating the adjacent vertex) and a reference to the next Edge in the adjacency list (null if this Edge object is the last one in the list).

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

protected static class AdjacencyListGraph.AdjListInfo
          Inner class for the adjacency list array.

protected static class AdjacencyListGraph.Edge
          Inner class for adjacency list edges.

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

class AdjacencyListGraph.VertexIterator
          Inner class for a vertex iterator.

Field Summary

protected AdjacencyListGraph.AdjListInfo[] adj
          An array of adjacency lists.

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.

Constructor Summary

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

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.

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.

protected com.mhhe.clrs2e.AdjacencyListGraph makeEmptyGraph(int cardV, boolean directed)
          Creates and returns an empty AdjacencyListGraph 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 graph.

com.mhhe.clrs2e.AdjacencyListGraph useSameVertices()
          Creates and returns a graph that uses the same set of vertices as 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.

adj

protected AdjacencyListGraph.AdjListInfo[] adj

An array of adjacency lists.

Constructor Detail