All Packages  Class Hierarchy  This Package  Previous  Next  Index

Class rpi.goldsd.graph.GraphBase

java.lang.Object
   |
   +----rpi.goldsd.graph.GraphBase

public abstract class GraphBase

extends Object

implements Cloneable, Drawable

Version:

2.1, 5/12/98

Author:

David Goldschmidt

See Also:

Vertex, Edge, DirectedEdge, Graph, Tree

DEFAULT_NAME

The default name of a graph.

edges

Hashtable containing references to all edges in this graph.

name

A reference to the user-defined name of this graph.

vertices

Hashtable containing references to all vertices in this graph.

GraphBase()

Constructs an unnamed empty graph.

GraphBase(GraphBase)

Constructs a graph by copying another graph.

GraphBase(int, int)

Constructs an empty graph with the specified initial vertex hashtable size and initial edge hashtable size.

GraphBase(String)

Constructs an empty graph with the specified name.

GraphBase(String, int, int)

Constructs an empty graph with the specified name, initial vertex hashtable size, and initial edge hashtable size.

addBase(Edge)

Adds the given edge to this graph if it is not already in this graph.

addBase(Vertex)

Adds the given vertex to this graph if it is not already in this graph.

clear()

Removes all vertices and edges from this graph.

clone()

Clones this graph.

contains(Edge)

Tests if a given edge exists in this graph.

contains(Vertex)

Tests if a given vertex exists in this graph.

edgeBetween(Vertex, Vertex)

Finds an edge of this graph that is between the two given vertices.

edges()

Returns an enumeration of the edges in this graph.

graphCopyHelper(GraphBase, GraphBase)

This protected static method performs a deep copy of all edges and vertices in the graph source to the graph target.

isDigraph()

Tests if this graph is a directed graph.

isEdgeBetween(Vertex, Vertex)

Tests if an edge exists in this graph that is between the two given vertices.

isEmpty()

Tests if this graph contains any vertices.

isWeighted()

Tests if this graph is a weighted graph.

mapToEdge(Hashable)

Maps the given key to an edge in this graph, if such a mapping exists in the underlying hashtable.

mapToVertex(Hashable)

Maps the given key to a vertex in this graph, if such a mapping exists in the underlying hashtable.

name()

Returns the user-defined name associated with this graph.

numEdges()

Returns the number of edges in this graph.

numVertices()

Returns the number of vertices in this graph.

printSummary()

Displays basic information about this graph.

printSummary(boolean)

Displays basic information about this graph.

rehash(Hashable, Hashable, Edge)

Rehashes an existing Edge object that is part of this graph, if necessary.

rehash(Hashable, Hashable, Vertex)

Rehashes an existing Vertex object that is part of this graph, if necessary.

setName(String)

Sets the name of this graph to the given String argument.

toString()

Returns a String representation of this graph (to keep output concise, the String representation currently consists of the name of the graph).

vertices()

Returns an enumeration of the vertices in this graph.

 public static final String DEFAULT_NAME

The default name of a graph.

 protected Table edges

Hashtable containing references to all edges in this graph.

 protected String name

A reference to the user-defined name of this graph.

 protected Table vertices

Hashtable containing references to all vertices in this graph.

 public GraphBase(String name,
                  int vertexTableSize,
                  int edgeTableSize)

Constructs an empty graph with the specified name, initial vertex hashtable size, and initial edge hashtable size.

Parameters:

name - the user-defined name of this graph.

vertexTableSize - the initial hashtable size for the hashtable used to contain the set of vertices.

edgeTableSize - the initial hashtable size for the hashtable used to contain the set of edges.

 public GraphBase(int vertexTableSize,
                  int edgeTableSize)

Constructs an empty graph with the specified initial vertex hashtable size and initial edge hashtable size.

Parameters:

vertexTableSize - the initial hashtable size for the hashtable used to contain the set of vertices.

edgeTableSize - the initial hashtable size for the hashtable used to contain the set of edges.

 public GraphBase(String name)

Constructs an empty graph with the specified name.

Parameters:

name - the user-defined name of this graph.

 public GraphBase()

Constructs an unnamed empty graph.

 public GraphBase(GraphBase G)

Constructs a graph by copying another graph.

Parameters:

G - the graph to copy.

 public abstract Object clone()

Clones this graph. Classes that extend the GraphBase class must implement the clone() method.

Returns:

a new graph that is a clone of this graph.

Overrides:

clone in class Object

 protected static final void graphCopyHelper(GraphBase target,
                                             GraphBase source)

This protected static method performs a deep copy of all edges and vertices in the graph source to the graph target. Note that the target graph is assumed to be constructed, with the name, vertices, and edges properly initialized (i.e. the two Table objects should be empty).

Parameters:

target - the target graph object (should be an empty graph).

source - the source graph object.

 public boolean contains(Edge E)

Tests if a given edge exists in this graph.

Parameters:

E - the edge to test.

Returns:

true if the given edge E is in this graph; false otherwise.

 public boolean contains(Vertex V)

Tests if a given vertex exists in this graph.

Parameters:

V - the vertex to test.

Returns:

true if the given vertex V is in this graph; false otherwise.

 public Edge edgeBetween(Vertex V1,
                         Vertex V2)

Finds an edge of this graph that is between the two given vertices. The two vertices and the corresponding edge, if present, must be part of this graph for this method to return an Edge object.

Parameters:

V1 - the first vertex of the pair.

V2 - the second vertex of the pair.

Returns:

the Edge object that is between the two given vertices V1 and V2; or null if no such edge exists.

 public Enumeration edges()

Returns an enumeration of the edges in this graph.

Returns:

an enumeration of the edges in this graph.

 public boolean isDigraph()

Tests if this graph is a directed graph.

Returns:

true if this graph is a directed graph (i.e. contains directed edges); false otherwise.

 public boolean isEdgeBetween(Vertex V1,
                              Vertex V2)

Tests if an edge exists in this graph that is between the two given vertices. The two vertices and the corresponding edge, if present, must be part of this graph for this method to return true.

Parameters:

V1 - the first vertex of the pair.

V2 - the second vertex of the pair.

Returns:

true if an edge exists in this graph that is between the two given vertices V1 and V2; false otherwise.

 public boolean isEmpty()

Tests if this graph contains any vertices.

Returns:

true if this graph contains no vertices; false otherwise.

 public boolean isWeighted()

Tests if this graph is a weighted graph.

Returns:

true if this graph is a weighted graph (i.e. contains weighted edges); false otherwise.

 public Edge mapToEdge(Hashable key)

Maps the given key to an edge in this graph, if such a mapping exists in the underlying hashtable.

Parameters:

key - the unique key identifying an edge.

Returns:

the edge identified by the given key; or null if key does not map to an edge of this graph.

 public Vertex mapToVertex(Hashable key)

Maps the given key to a vertex in this graph, if such a mapping exists in the underlying hashtable.

Parameters:

key - the unique key identifying a vertex.

Returns:

the vertex identified by the given key; or null if key does not map to a vertex of this graph.

 public String name()

Returns the user-defined name associated with this graph.

Returns:

the user-defined name associated with this graph.

 public int numEdges()

Returns the number of edges in this graph.

Returns:

the number of edges in this graph.

 public int numVertices()

Returns the number of vertices in this graph.

Returns:

the number of vertices in this graph.

 public void printSummary(boolean printVertices)

Displays basic information about this graph.

Parameters:

printVertices - if set to true, this method displays summary information for each of the vertices in this graph.

 public void printSummary()

Displays basic information about this graph.

 public String toString()

Returns a String representation of this graph (to keep output concise, the String representation currently consists of the name of the graph).

Returns:

a String representation of this graph.

Overrides:

toString in class Object

 public Enumeration vertices()

Returns an enumeration of the vertices in this graph.

Returns:

an enumeration of the vertices in this graph.

 protected synchronized void addBase(Edge E) throws DuplicateElementException, InAnotherGraphException, VertexNotFoundException

Adds the given edge to this graph if it is not already in this graph. The two endpoint vertices associated with the given edge must already be in this graph.

Parameters:

E - the edge to be added to this graph.

Throws: DuplicateElementException

if the key is already present in the set of vertices.

Throws: InAnotherGraphException

if the edge is already in a different graph.

Throws: VertexNotFoundException

if either of the endpoint vertices of the edge are not in this graph.

 protected synchronized void addBase(Vertex V) throws DuplicateElementException, InAnotherGraphException

Adds the given vertex to this graph if it is not already in this graph.

Parameters:

V - the vertex to be added to this graph.

Throws: DuplicateElementException

if the key is already present in the set of vertices.

Throws: InAnotherGraphException

if the vertex is already in a different graph.

 public synchronized void clear()

Removes all vertices and edges from this graph.

 protected void rehash(Hashable oldData,
                       Hashable newData,
                       Edge E)

Rehashes an existing Edge object that is part of this graph, if necessary.

Parameters:

oldData - the old Hashable object used to locate the old Edge object in the underlying hashtable.

newData - the new Hashable object that should replace the old Hashable object associated with the given Edge object.

E - the Edge object that contains the old Hashable object oldData.

 protected void rehash(Hashable oldData,
                       Hashable newData,
                       Vertex V)

Rehashes an existing Vertex object that is part of this graph, if necessary.

Parameters:

oldData - the old Hashable object used to locate the old Vertex object in the underlying hashtable.

V - the Vertex object that contains a new Hashable object.

 public String setName(String name)

Sets the name of this graph to the given String argument.

Parameters:

name - the new name of this graph.

Returns:

the old name of this graph.

All Packages  Class Hierarchy  This Package  Previous  Next  Index