package rpi.goldsd.graph;
import rpi.goldsd.container.*;
/**
* The Tree class is a subclass of the GraphBase class and
* is used to represent a tree. A tree is a graph that adheres to the
* following additional set of requirements:
*
*
* - The graph must be connected.
*
- The graph must be acyclic.
*
- The tree must be rooted at a specified vertex.
*
*
* @see GraphBase
* @version 2.1, 5/12/98
* @author David Goldschmidt
*/
public class Tree extends GraphBase
{
/* ****************** CONSTRUCTOR METHODS ****************** */
/**
* Constructs a tree with the specified root vertex, name,
* initial vertex hashtable size, and initial edge hashtable size.
* @param root the root vertex of this tree.
* @param name the user-defined name of this tree.
* @param vertexTableSize the initial hashtable size for the hashtable
* used to contain the set of vertices.
* @param edgeTableSize the initial hashtable size for the
* hashtable used to contain the set of edges.
*/
public Tree( Vertex root, String name, int vertexTableSize,
int edgeTableSize )
{
super( name, vertexTableSize, edgeTableSize );
addBase( root );
this.root = root;
}
/**
* Constructs a tree with the specified name, initial vertex hashtable
* size, and initial edge hashtable size. Note that a root vertex is
* not specified in this protected method; this method is used by the
* clone() method of the Tree class.
* @param name the user-defined name of this tree.
* @param vertexTableSize the initial hashtable size for the hashtable
* used to contain the set of vertices.
* @param edgeTableSize the initial hashtable size for the
* hashtable used to contain the set of edges.
*/
protected Tree( String name, int vertexTableSize, int edgeTableSize )
{
super( name, vertexTableSize, edgeTableSize );
this.root = null;
}
/**
* Constructs a tree with the specified root vertex, initial
* vertex hashtable size and initial edge hashtable size.
* @param root the root vertex of this tree.
* @param vertexTableSize the initial hashtable size for the hashtable
* used to contain the set of vertices.
* @param edgeTableSize the initial hashtable size for the
* hashtable used to contain the set of edges.
*/
public Tree( Vertex root, int vertexTableSize, int edgeTableSize )
{
super( vertexTableSize, edgeTableSize );
addBase( root );
this.root = root;
}
/**
* Constructs a tree with the specified root vertex and name.
* @param root the root vertex of this tree.
* @param name the user-defined name of this tree.
*/
public Tree( Vertex root, String name )
{
super( name );
addBase( root );
this.root = root;
}
/**
* Constructs a tree by copying another tree.
* @param T the tree to copy.
*/
public Tree( Tree T )
{
super( T );
this.root = this.mapToVertex( T.root.data() );
}
/**
* Clones this tree.
* @return a new tree that is a clone of this tree.
*/
public Object clone()
{
Tree T = new Tree( "Clone of " + name, vertices.getTableSize(),
edges.getTableSize() );
super.graphCopyHelper( T, this );
T.root = T.mapToVertex( this.root.data() );
return T;
}
/**
* Constructs an unnamed tree with the specified root vertex.
* @param root the root vertex of this tree.
*/
public Tree( Vertex root )
{
super();
addBase( root );
this.root = root;
}
/**
* Default constructor is not used, since a tree must, by definition,
* have a root vertex.
*/
protected Tree()
{
super();
this.root = null;
}
/* ****************** ACCESSOR METHODS ****************** */
/**
* Returns a reference to the root vertex of this tree.
* @return a reference to the root vertex of this tree.
*/
public Vertex root() { return root; }
/* ****************** MUTATOR METHODS ****************** */
/**
* Adds an edge and corresponding vertex to this tree. To maintain
* the properties of a tree, an edge and corresponding vertex must
* be added as an atomic method. Adding an unattached vertex is
* not allowed.
*
* The given edge must have an endpoint vertex that exists in this
* tree and another endpoint vertex that is the second argument V.
* @param E the edge to be added to this tree.
* @param V the vertex to be added to this tree.
* @exception IllegalArgumentException if the vertex and edge arguments
* are not connected.
* @exception rpi.goldsd.container.DuplicateElementException if
* the key of either the edge or the vertex to be added
* is already present in the set of edges and vertices,
* respectively.
* @exception rpi.goldsd.graph.InAnotherGraphException if the
* edge or vertex is already in a different graph.
* @exception rpi.goldsd.graph.VertexNotFoundException if the
* endpoint vertex that is to already exist in this
* tree does not exist in this tree.
*/
public void add( Edge E, Vertex V )
throws rpi.goldsd.container.DuplicateElementException,
InAnotherGraphException, VertexNotFoundException,
IllegalArgumentException
{
if ( E.isInGraph( this ) ) throw
new DuplicateElementException( "Duplicate edge: " + E );
else if ( E.isInGraph() ) throw
new InAnotherGraphException( "Edge " + E + " is in another graph." );
if ( V.isInGraph( this ) ) throw
new DuplicateElementException( "Duplicate vertex: " + V );
else if ( V.isInGraph() ) throw
new InAnotherGraphException( "Vertex " + V + " is in another graph." );
Vertex startVertex = E.startVertex();
Vertex endVertex = E.endVertex();
if ( E instanceof DirectedEdge && startVertex == V ) throw
new IllegalArgumentException( "Directed edge " + E + " not added." );
Vertex shouldBeInGraph;
if ( startVertex == V )
shouldBeInGraph = endVertex;
else if ( endVertex == V )
shouldBeInGraph = startVertex;
else throw
new IllegalArgumentException( "Edge " + E +
" not connected to vertex " + V + "." );
if ( ! contains( shouldBeInGraph ) ) throw
new VertexNotFoundException( "Vertex " + shouldBeInGraph +
" not in graph." );
addBase( V );
addBase( E );
}
/**
* Removes all vertices and edges from this tree, except for the
* root Vertex object.
*/
public void clear()
{
Vertex root = this.root;
super.clear();
addBase( root );
this.root = root;
}
/* ****************** CLASS ATTRIBUTES ****************** */
/** A reference to the root Vertex object of this tree. */
protected Vertex root;
}