Opus5
Interface Graph

All Superinterfaces:

Comparable, Container

All Known Subinterfaces:

Digraph

All Known Implementing Classes:

AbstractGraph

public interface Graph

extends Container

Encapsulates methods common to all graphs (both directed and undirected).

Version:

$Id: Graph.java,v 3.3 1998/07/28 13:42:23 brpreiss Exp $

Author:

Bruno R. Preiss, P.Eng.

Field Summary

static java.lang.String

copyright

Method Summary

void	addEdge(int v, int w) Adds an unweighted edge to this graph that connects the two vertices specified by their vertex numbers.
void	addEdge(int v, int w, java.lang.Object weight) Adds a weighted edge to this graph that connects the two vertices specified by their vertex numbers.
void	addVertex(int v) Adds an unweighted vertex with a specified number to this graph.
void	addVertex(int v, java.lang.Object weight) Adds a weighted vertex with a specified number 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 directed graph in depth-first traversal order starting from a given vertex.
Edge	getEdge(int v, int w) Returns the edge that connects the two vertices specified by their vertex numbers.
Enumeration	getEdges() Returns an enumeration that enumerates the edges in this graph.
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 in this graph with the specified 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	isEdge(int v, int w) Tests whether there is an edge in this graph that connects the two vertices specified by their numbers.

Methods inherited from interface Opus5.Container

accept, getCount, getEnumeration, isEmpty, isFull, purge

Methods inherited from interface Opus5.Comparable

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

Field Detail

copyright

public static final java.lang.String copyright

Method Detail

getNumberOfEdges

public int getNumberOfEdges()

Returns the number of edges in this graph.

Returns:

The number of edges in this graph.

getNumberOfVertices

public int getNumberOfVertices()

Returns the number of vertices in this graph.

Returns:

The number of vertices in this graph.

isDirected

public boolean isDirected()

Tests whether this graph is a directed graph.

Returns:

True if this graph is directed; false otherwise.

See Also:

Digraph

addVertex

public void addVertex(int v)

Adds an unweighted vertex with a specified number to this graph.

Parameters:

v - The number of the vertex to add.

Throws:

ContainerFullException - If no more vertices can be added to this graph.

addVertex

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

Adds a weighted vertex with a specified number to this graph.

Parameters:

v - The number of the vertex to add.

weight - The weight to be associated with the vertex.

Throws:

ContainerFullException - If no more vertices can be added to this graph.

getVertex

public Vertex getVertex(int v)

Returns the vertex in this graph with the specified number.

Parameters:

v - The number of the vertex to be returned.

Returns:

The vertext with the specified number.

See Also:

Vertex

addEdge

public void addEdge(int v,
                    int w)

Adds an unweighted edge to this graph that connects the two vertices specified by their vertex numbers.

Parameters:

v - The vertex at the tail of the edge.

w - The vertex at the head of the edge.

addEdge

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

Adds a weighted edge to this graph that connects the two vertices specified by their vertex numbers.

Parameters:

v - The vertex at the tail of the edge.

w - The vertex at the head of the edge.

weight - The weight to be associated with the edge.

getEdge

public Edge getEdge(int v,
                    int w)

Returns the edge that connects the two vertices specified by their vertex numbers.

Parameters:

v - The vertex at the tail of the edge.

w - The vertex at the head of the edge.

Returns:

The edge that connects the given vertices.

isEdge

public boolean isEdge(int v,
                      int w)

Tests whether there is an edge in this graph that connects the two vertices specified by their numbers.

Parameters:

v - The vertex at the tail of the edge.

w - The vertex at the head of the edge.

Returns:

True if the edge exists; false otherwise.

See Also:

Edge

isConnected

public boolean isConnected()

Tests whether this graph is connected. If this graph is an directed graph, this method tests whether the graph is weakly connected.

Returns:

True if this graph is (weakly) connected; false otherwise.

See Also:

Digraph.isStronglyConnected()

isCyclic

public boolean isCyclic()

Tests whether this graph is cyclic.

Returns:

True if this graph is cyclic; false otherwise.

getVertices

public Enumeration getVertices()

Returns an enumeration that enumerates the vertices in this graph.

Returns:

An Enumeration that enumerates the vertices in this graph

See Also:

Enumeration

getEdges

public Enumeration getEdges()

Returns an enumeration that enumerates the edges in this graph.

Returns:

An enumeration that enumerates the edges in this graph.

See Also:

Enumeration

depthFirstTraversal

public void depthFirstTraversal(PrePostVisitor visitor,
                                int start)

Causes a visitor to visit the vertices of this directed 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 traversal continues as long as the IsDone method of the visitor returns false.

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 traversal continues as long as the IsDone method of the visitor returns false.

Parameters:

visitor - The visitor to accept.

start - The vertex at which to start the traversal.

See Also:

Visitor