Opus5
Class AbstractGraph

java.lang.Object
  |
  +--Opus5.AbstractObject
        |
        +--Opus5.AbstractContainer
              |
              +--Opus5.AbstractGraph

All Implemented Interfaces:

Comparable, Container, Graph

Direct Known Subclasses:

GraphAsLists, GraphAsMatrix

public abstract class AbstractGraph

extends AbstractContainer

implements Graph

The AbstractGraph class is the base class from which all concrete undirected and directed graph classes are derived. This abstract class provides default implementations for various methods declared in the Graph and the Digraph interfaces.

Version:

$Id: AbstractGraph.java,v 3.5 1998/07/28 12:58:55 brpreiss Exp $

Author:

Bruno R. Preiss, P.Eng.

See Also:

Graph, Digraph

Inner Class Summary

protected static class	AbstractGraph.Counter A counter object.
protected class	AbstractGraph.GraphEdge Represents an edge in this graph.
protected class	AbstractGraph.GraphVertex Represents a vertex in this graph.

Field Summary

protected int	numberOfEdges The number of edges in this graph.
protected int	numberOfVertices The number of vertices in this graph.
protected Vertex[]	vertex The vertices.

Fields inherited from class Opus5.AbstractContainer

count

Fields inherited from interface Opus5.Graph

copyright

Constructor Summary

AbstractGraph(int size)
Constructs an AbstractGraph with the specified size.

Method Summary

void	accept(Visitor visitor) Accepts a visitor and makes it visit the vertices in this graph.
protected abstract void	addEdge(Edge edge) Adds an edge to this graph.
void	addEdge(int v, int w) Adds an edge to this graph that connects the specified vertices.
void	addEdge(int v, int w, java.lang.Object weight) Adds an edge to this graph that connects the specified vertices and has the specified weight.
void	addVertex(int v) Adds a vertex to this graph with the specified number.
void	addVertex(int v, java.lang.Object weight) Adds a vertex to this graph with the specified number and weight.
protected void	addVertex(Vertex v) Adds the specified vertex to this graph.
void	breadthFirstTraversal(Visitor visitor, int start) Causes a visitor to visit the vertices of this directed graph in breadth-first traversal order starting from a given vertex.
void	depthFirstTraversal(PrePostVisitor visitor, int start) Causes a visitor to visit the vertices of this graph in depth-first traversal order starting from a given vertex.
protected abstract Enumeration	getEmanatingEdges(int v) Returns an enumeration that enumerates the edges that emanate from the specified vertex.
Enumeration	getEnumeration() Returns an enumeration that enumerates the vertices in this graph.
protected abstract Enumeration	getIncidentEdges(int v) Returns an enumeration that enumerates the edges incident upon the specified vertex.
int	getNumberOfEdges() Returns the number of edges in this graph.
int	getNumberOfVertices() Returns the number of vertices in this graph.
Vertex	getVertex(int v) Returns the vertex with the specified vertex number.
Enumeration	getVertices() Returns an enumeration that enumerates the vertices in this graph.
boolean	isConnected() Tests whether this graph is connected.
boolean	isCyclic() Tests whether this graph is cyclic.
boolean	isDirected() Tests whether this graph is a directed graph.
boolean	isStronglyConnected() Tests whether this graph is strongly connected.
void	purge() Purges the vertices from this graph.
void	topologicalOrderTraversal(Visitor visitor) Causes a visitor to visit the vertices of this graph in topological order.
java.lang.String	toString() Returns a string representation of this graph.

Methods inherited from class Opus5.AbstractContainer

getCount, hashCode, isEmpty, isFull

Methods inherited from class Opus5.AbstractObject

compare, compareTo, equals, isEQ, isGE, isGT, isLE, isLT, isNE

Methods inherited from class java.lang.Object

clone, finalize, getClass, notify, notifyAll, wait, wait, wait

Methods inherited from interface Opus5.Graph

getEdge, getEdges, isEdge

Methods inherited from interface Opus5.Container

getCount, isEmpty, isFull

Methods inherited from interface Opus5.Comparable

compare, isEQ, isGE, isGT, isLE, isLT, isNE

Field Detail

numberOfVertices

protected int numberOfVertices

The number of vertices in this graph.

numberOfEdges

protected int numberOfEdges

The number of edges in this graph.

vertex

protected Vertex[] vertex

The vertices.

Constructor Detail

AbstractGraph

public AbstractGraph(int size)

Constructs an AbstractGraph with the specified size.

Parameters:

size - The maximum number of vertices.

Method Detail

purge

public void purge()

Purges the vertices from this graph.

Specified by:

purge in interface Container

addVertex

protected void addVertex(Vertex v)

Adds the specified vertex to this graph.

Parameters:

v - The vertex to add.

Throws:

java.lang.IllegalArgumentException - If the number of the vertex is not the next number in sequence.

addVertex

public final void addVertex(int v,
                            java.lang.Object weight)

Adds a vertex to this graph with the specified number and weight.

Specified by:

addVertex in interface Graph

Parameters:

v - The number of the vertex to be added.

weight - The weight to be associated with this vertex.

addVertex

public final void addVertex(int v)

Adds a vertex to this graph with the specified number.

Specified by:

addVertex in interface Graph

Parameters:

v - The number of the vertex to be added.

getVertex

public Vertex getVertex(int v)

Returns the vertex with the specified vertex number.

Specified by:

getVertex in interface Graph

Parameters:

v - The vertex number.

Returns:

The vertex with the specified vertex number.

getVertices

public Enumeration getVertices()

Returns an enumeration that enumerates the vertices in this graph.

Specified by:

getVertices in interface Graph

Returns:

an enumeration that enumerates the vertices in this graph.

getIncidentEdges

protected abstract Enumeration getIncidentEdges(int v)

Returns an enumeration that enumerates the edges incident upon the specified vertex.

Parameters:

v - The number of the specified vertex.

Returns:

An enumeration that enumerates the edges incident upon the specified vertex.

getEmanatingEdges

protected abstract Enumeration getEmanatingEdges(int v)

Returns an enumeration that enumerates the edges that emanate from the specified vertex.

Parameters:

v - The number of the specified vertex.

Returns:

An enumeration that enumerates the edges that emanate from the specified vertex.

addEdge

protected abstract void addEdge(Edge edge)

Adds an edge to this graph.

Parameters:

edge - The edge to be added to this graph.

isDirected

public boolean isDirected()

Tests whether this graph is a directed graph. A graph is a directed graph if it implements the Digraph interface.

Specified by:

isDirected in interface Graph

Returns:

True if this graph is a directed graph.

addEdge

public final void addEdge(int v,
                          int w,
                          java.lang.Object weight)

Adds an edge to this graph that connects the specified vertices and has the specified weight. Implemented as follows:

 addEdge (new GraphEdge (v, w, weight));
 

Specified by:

addEdge in interface Graph

Parameters:

v - The number of the vertex from which the edge emanates.

w - The number of the vertex upon which the edge is incident.

weight - The weight associated with the edge. Implemented

addEdge

public final void addEdge(int v,
                          int w)

Adds an edge to this graph that connects the specified vertices. Implemented as follows:

 addEdge (v, w, null);
 

Specified by:

addEdge in interface Graph

Parameters:

v - The number of the vertex from which the edge emanates.

w - The number of the vertex upon which the edge is incident.

weight - The weight associated with the edge. Implemented

getNumberOfVertices

public int getNumberOfVertices()

Returns the number of vertices in this graph.

Specified by:

getNumberOfVertices in interface Graph

Returns:

The number of vertices in this graph.

getNumberOfEdges

public int getNumberOfEdges()

Returns the number of edges in this graph.

Specified by:

getNumberOfEdges in interface Graph

Returns:

The number of edges in this graph.

accept

public void accept(Visitor visitor)

Accepts a visitor and makes it visit the vertices in this graph.

Specified by:

accept in interface Container

Overrides:

accept in class AbstractContainer

Parameters:

visitor - The visitor to accept.

depthFirstTraversal

public void depthFirstTraversal(PrePostVisitor visitor,
                                int start)

Causes a visitor to visit the vertices of this graph in depth-first traversal order starting from a given vertex. This method invokes the preVisit and postVisit methods of the visitor for each vertex in this graph. The default implementation is recursive. The default implementation never invokes the inVisit method of the visitor. The traversal continues as long as the isDone method of the visitor returns false.

Specified by:

depthFirstTraversal in interface Graph

Parameters:

visitor - The visitor to accept.

start - The vertex at which to start the traversal.

See Also:

PrePostVisitor

breadthFirstTraversal

public void breadthFirstTraversal(Visitor visitor,
                                  int start)

Causes a visitor to visit the vertices of this directed graph in breadth-first traversal order starting from a given vertex. This method invokes the visit method of the visitor for each vertex in this graph. The default implementation is iterative and uses a queue to keep track of the vertices to be visited. The traversal continues as long as the isDone method of the visitor returns false.

Specified by:

breadthFirstTraversal in interface Graph

Parameters:

visitor - The visitor to accept.

start - The vertex at which to start the traversal.

See Also:

Visitor

topologicalOrderTraversal

public void topologicalOrderTraversal(Visitor visitor)

Causes a visitor to visit the vertices of this graph in topological order. This method takes a visitor and, as long as the IsDone method of that visitor returns false, this method invokes the Visit method of the visitor for each vertex in the graph. The order in which the vertices are visited is given by a topological sort of the vertices.

Parameters:

visitor - The visitor to accept.

See Also:

Visitor

toString

public java.lang.String toString()

Returns a string representation of this graph.

Overrides:

toString in class AbstractContainer

Returns:

A string representation of this graph.

isConnected

public boolean isConnected()

Tests whether this graph is connected. The default implementation does a depth-first traversal and counts the number of vertices visited. If all the vertices are visited, the graph is connected.

Specified by:

isConnected in interface Graph

Returns:

True if this graph is connected; false otherwise.

isStronglyConnected

public boolean isStronglyConnected()

Tests whether this graph is strongly connected. The default implementation does a depth-first traversal starting at each vertex in this graph. If every traversal visits all the vertices in this graph, the graph is strongly connected.

Returns:

True if this graph is strongly connected; false otherwise.

See Also:

Graph.isConnected()

isCyclic

public boolean isCyclic()

Tests whether this graph is cyclic. The default implementation does a topological order traversal and counts the number of vertices visited. If every vertex in this graph is visited, the graph is acyclic.

Specified by:

isCyclic in interface Graph

Returns:

True if this graph is cyclic; false otherwise.

getEnumeration

public Enumeration getEnumeration()

Returns an enumeration that enumerates the vertices in this graph.

Specified by:

getEnumeration in interface Container

Returns:

An enumeration that enumerates the vertices in this graph. This method is implemented as follows:

 return getVertices ();
 

See Also:

getVertices()