package rpi.goldsd.graph;
import java.util.*;
import rpi.goldsd.container.*;
/**
* The Vertex class is used to represent a single vertex,
* and is associated with zero or one GraphBase objects.
*
* @see GraphBase
* @version 2.2, 5/11/98
* @author David Goldschmidt
*/
public class Vertex implements Cloneable, Hashable
{
private static final IntSequence I = new IntSequence();
private static final Enumeration keys = I.sequence();
/* ****************** CONSTRUCTOR METHODS ****************** */
/**
* Constructs a vertex with the initial user-defined object to be
* associated with this vertex.
* @param data the user-defined object to be associated with this vertex.
*/
public Vertex( Hashable data )
{
this.associatedGraph = null;
this.data = data;
this.incidentEdges = new Vector();
this.incomingEdges = new Vector();
}
/**
* Constructs a vertex with the initial String object to be
* associated with this vertex. The String object is converted
* to a Str object since the Str class implements
* the Hashable interface.
* @param s the String object to be associated with this vertex.
*/
public Vertex( String s ) { this( new Str( s ) ); }
/**
* Constructs a vertex with the initial integer value to be
* associated with this vertex. The integer value is converted
* to a Int object since the Int class implements
* the Hashable interface.
* @param i the integer value to be associated with this vertex.
*/
public Vertex( int i ) { this( new Int( i ) ); }
/**
* Constructs a vertex by copying the attributes of another vertex.
* Note that the new vertex does not contain any incident or incoming
* edges and is not associated with a graph.
* @param V the vertex to be copied.
*/
public Vertex( Vertex V ) { this( V.data() ); }
/**
* Clones this vertex. Note that the new vertex does not contain
* any incident or incoming edges and is not associated with a graph.
* @return a new vertex that is a clone of this vertex.
*/
public Object clone() { return new Vertex( data ); }
/**
* Constructs a vertex with default attributes. Since each Vertex
* object must be associated with a Hashable object, the default
* constructor generates a unique Hashable key of type Int.
*/
public Vertex() { this( (Hashable)keys.nextElement() ); }
/* ****************** ACCESSOR METHODS ****************** */
/**
* Returns a reference to the Hashable object that is
* associated with this vertex.
* @return a reference to the Hashable object that is
* associated with this vertex.
*/
public Hashable data() { return data; }
/**
* Returns the degree of this vertex. For directed edges
* that are incident with this vertex, the degree is the sum of
* the in-degree and the out-degree.
* @return the degree of this vertex.
*/
public int degree() { return outDegree() + inDegree(); }
/**
* Returns a reference to the graph that contains this vertex, if any.
* @return a reference to the graph that contains this vertex; or
* null if this vertex is not associated with a graph.
*/
public GraphBase graph() { return associatedGraph; }
/**
* Returns the hash value of the Hashable data associated with
* this vertex.
* @return the hash value of the Hashable data associated with
* this vertex.
*/
public int hash() { return data.hash(); }
/**
* Returns the hash value of the Hashable data associated with
* this vertex.
* @param tableSize the size of the table that will potentially hold this
* Vertex object and others.
* @return the hash value of the Hashable data associated with
* this vertex.
*/
public int hash( int tableSize ) { return data.hash( tableSize ); }
/**
* Returns an enumeration of the edges incident with this vertex.
* @return an enumeration of the edges incident with this vertex.
*/
public Enumeration incidentEdges() { return incidentEdges.elements(); }
/**
* Returns an enumeration of the incoming directed edges that
* are incident with this vertex.
* @return an enumeration of the incoming directed edges incident
* with this vertex.
*/
public Enumeration incomingEdges() { return incomingEdges.elements(); }
/**
* Returns the in-degree of this vertex.
* @return the in-degree of this vertex.
*/
public int inDegree() { return incomingEdges.size(); }
/**
* Tests if two vertices are "equal" based on their Hashable data
* objects.
* @param C the right-hand side of the comparison.
* @return true if this vertex is "equal" to the given vertex
* C based on the Hashable data objects;
* false otherwise.
*/
public boolean isEqualTo( Comparable C )
{
if ( C instanceof Vertex ) return data.isEqualTo( ((Vertex)C).data() );
else return data.isEqualTo( C );
}
/**
* Tests if the given edge is incident with this vertex. For
* directed edges, only outgoing edges are considered to be incident
* with this vertex.
* @param E the edge to test.
* @return true if the given edge E is incident with
* this vertex; false otherwise.
*/
public boolean isIncident( Edge E ) { return incidentEdges.contains( E ); }
/**
* Tests if this vertex is associated with a graph.
* @return true if this vertex is associated with a graph;
* false otherwise.
*/
public boolean isInGraph() { return associatedGraph != null; }
/**
* Tests if this vertex is associated with the given graph.
* @param G the graph to test.
* @return true if this vertex is associated with the
* given graph G; false otherwise.
*/
public boolean isInGraph( GraphBase G ) { return associatedGraph == G; }
/**
* Tests if one vertex is "less than" another based on the Hashable
* data objects.
* @param C the right-hand side of the comparison.
* @return true if this vertex is "less than" the given vertex
* C based on the Hashable data objects;
* false otherwise.
*/
public boolean isLessThan( Comparable C )
{
if ( C instanceof Vertex ) return data.isLessThan( ((Vertex)C).data() );
else return data.isLessThan( C );
}
/**
* Returns the number of edges incident with this vertex. For
* directed edges, only outgoing edges are considered incident
* with this vertex.
* @return the number of edges incident with this vertex.
*/
public int numIncidentEdges() { return degree(); }
/**
* Returns the out-degree of this vertex.
* @return the out-degree of this vertex.
*/
public int outDegree() { return incidentEdges.size(); }
/** Displays information about this vertex. */
public void printSummary()
{
System.out.print( " " + this + ": " );
Enumeration e = incidentEdges();
if ( ! e.hasMoreElements() )
{
System.out.println( "no incident edges." );
return;
}
Edge E = (Edge)e.nextElement();
System.out.print( "" + E + " (" + E.traverseFrom( this ) + ")" );
while ( e.hasMoreElements() )
{
E = (Edge)e.nextElement();
System.out.print( ", " + E + " (" + E.traverseFrom( this ) + ")" );
}
System.out.println( "." );
}
/**
* Returns a String representation of this vertex. The
* toString() method is applied to the Hashable object
* associated with this vertex.
* @return a String representation of this vertex.
*/
public String toString() { return "" + data; }
/* ****************** MUTATOR METHODS ****************** */
/**
* Adds an incident edge to this vertex.
* @param E the edge to be added to the list of incident edges
* for this vertex.
*/
protected void addIncidentEdge( Edge E ) { incidentEdges.addElement( E ); }
/**
* Adds an incoming directed edge to this vertex.
* @param E the directed edge to be added to the list of incoming edges
* for this vertex.
*/
protected void addIncomingEdge( DirectedEdge E )
{
incomingEdges.addElement( E );
}
/** Removes all incident edges from this vertex. */
protected void removeAllIncidentEdges() { incidentEdges = new Vector(); }
/** Removes all incoming edges from this vertex. */
protected void removeAllIncomingEdges() { incomingEdges = new Vector(); }
/**
* Finds and removes an incident edge from this vertex.
* @param E the edge to be removed from the list of incident
* edges for this vertex.
*/
protected void removeIncidentEdge( Edge E )
{
incidentEdges.removeElement( E );
}
/**
* Finds and removes an incoming directed edge from this vertex.
* @param E the directed edge to be removed from the list of incoming
* edges for this vertex.
*/
protected void removeIncomingEdge( DirectedEdge E )
{
incomingEdges.removeElement( E );
}
/**
* Sets the Hashable object that is associated with this vertex.
* @param data the new Hashable object.
* @return the old Hashable object associated with this vertex.
*/
public Hashable setData( Hashable data )
{
Hashable oldData = this.data;
if ( isInGraph() )
associatedGraph.rehash( oldData, data, this );
else
this.data = data;
return oldData;
}
/**
* Sets the associatedGraph reference to the graph G.
* @param G the graph that this vertex is to be associated with.
*/
protected void setInGraph( GraphBase G ) { associatedGraph = G; }
/* ****************** CLASS ATTRIBUTES ****************** */
/**
* A reference to the graph that this vertex is associated with;
* or null if this vertex is not associated with a graph.
*/
protected GraphBase associatedGraph;
/** The Hashable object associated with this vertex. */
protected Hashable data;
/**
* A reference to the Vector used to contain the set of edges
* incident with this vertex. For directed edges, only outgoing
* edges are stored in this Vector.
*/
protected Vector incidentEdges;
/**
* A reference to the Vector used to contain the set of incoming
* directed edges incident to this vertex.
*/
protected Vector incomingEdges;
/** Status field used internally by the static Algorithms class. */
protected int status;
/** Rank field used internally by the static Algorithms class. */
protected int rank;
/** Used by the static Algorithms class. */
protected double distance;
/** Used by the static Algorithms class. */
protected Vertex parent;
/** Used by the static Algorithms class. */
protected Vertex min;
}