beowulf.model.graph
Class UndirectedGraph

java.lang.Object
  extended bybeowulf.model.graph.AbstractGraphModel
      extended bybeowulf.model.graph.UndirectedGraph
All Implemented Interfaces:
GraphModel, Serializable

public class UndirectedGraph
extends AbstractGraphModel
implements Serializable

This class is a model of a Graph. It consists of collections of nodes and edges, each of which have their own analogous classes. The class is optimized for speed, not for space. Much of the data is stored in multiple ways so that it will be quickly accessible. One can add nodes and edges arbitrarily. Edges of course must start at one node and end at another. An edge from node A to node B is different than one from node B to node A. Edges between nodes can be accessed in collections of
1) Those going to a particular node
2) Those going from a particular node
3) All Edges


Version:
1.0, 6/9/2003
Author:
Andy Scukanec (ags at cs dot cornell dot edu)
See Also:
Serialized Form

Field Summary
protected  Vector edgeList
          A vector of all of the edges.
protected  Vector nodeList
          The vector containing all of the nodes.
protected  VectorMatrix transitionMatrix
          A matrix in that holds transitions between nodes.
protected  Vector usedIndices
          Holds a list of used indices for identifying a particular node.
protected  boolean useDotEquals
          Holds a flag that tells this object whether to use .equals for object comparison, or ==.
protected  Map valueToIndex
          Translates a nodes contents into an identifying number.
 
Fields inherited from class beowulf.model.graph.AbstractGraphModel
listenerList
 
Constructor Summary
UndirectedGraph()
          Basic constructor for a Graph.
UndirectedGraph(boolean newUseDotEquals)
          This constructor lets the user choose whether reference equality (==) or semantic equality (.equals()) will be used in differentiating between nodes in a graph.
 
Method Summary
 void addEdge(Edge edge)
          This method will add a new edge to the graph.
 void addEdge(Object sourceValue, Object destinationValue, Object cost)
          This method will add a new edge to the graph.
 void addNode(Object value)
          This method adds a new node to the graph, and associates the parameter as the value of the node.
 int getEdgeCount()
          Returns the number of edges in the graph.
 Vector getEdges()
          Returns a list of all edges in the graph.
 Vector getEdgesFrom(Object value)
          Given the value of some node, this method will return a list of all edges originating at this node.
 Vector getEdgesFromTo(Object sourceValue, Object destValue)
          Given the value of the source node and the destination node, this method will return a list of all edges going between the two nodes.
 Vector getEdgesTo(Object value)
          Given the value of some node, this method will return a list of all edges ending at this node.
 int getNodeCount()
          Returns the number of nodes in the graph.
 Vector getNodes()
          Returns a list of the values of each node in the graph.
 boolean getUseDotEquals()
          Returns true if this graph instance uses .equals for object comparison.
 boolean isDirected()
          Returns whether or not the graph is directed.
 boolean isSimple()
          Returns whether or not the graph is simple (ie - there are no edges from some node to itself and there is at most one edge between any two different nodes).
 Object removeEdge(Edge toRemove)
          This method will remove the edge from the graph.
 Object removeEdge(Object sourceValue, Object destinationValue, Object cost)
          This method will remove the edge with the indicated source and destination values from the graph.
 void removeNode(Object value)
          Given a node's value, this method will find and remove that node, and any associated edges from the graph.
 String toString()
          Returns a basic string representation of this graph.
 String toString(boolean fullThing)
          This method is implemented simply to keep with the possibility of a verbose representation of a Graph.
 
Methods inherited from class beowulf.model.graph.AbstractGraphModel
addGraphListener, fireEdgeAdded, fireEdgeRemoved, fireNodeAdded, fireNodeRemoved, getGraphListeners, getListeners, removeGraphListener
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

transitionMatrix

protected VectorMatrix transitionMatrix
A matrix in that holds transitions between nodes.


nodeList

protected Vector nodeList
The vector containing all of the nodes.


edgeList

protected Vector edgeList
A vector of all of the edges.


valueToIndex

protected Map valueToIndex
Translates a nodes contents into an identifying number.


usedIndices

protected Vector usedIndices
Holds a list of used indices for identifying a particular node.


useDotEquals

protected boolean useDotEquals
Holds a flag that tells this object whether to use .equals for object comparison, or ==.

Constructor Detail

UndirectedGraph

public UndirectedGraph()
Basic constructor for a Graph. Does the basic set up so that the Graph is usable, and assumes that semantic equality will be used.


UndirectedGraph

public UndirectedGraph(boolean newUseDotEquals)
This constructor lets the user choose whether reference equality (==) or semantic equality (.equals()) will be used in differentiating between nodes in a graph. A value of true for the parameter indicates semantic equality.

Parameters:
newUseDotEquals - True if this graph should use .equals.
Method Detail

getUseDotEquals

public boolean getUseDotEquals()
Returns true if this graph instance uses .equals for object comparison.

Specified by:
getUseDotEquals in interface GraphModel
Returns:
True if this graph instance uses .equals for object comparison, false otherwise.

getNodes

public Vector getNodes()
Returns a list of the values of each node in the graph. The graph should not be changed while this Vector is in use.

Specified by:
getNodes in interface GraphModel
Returns:
A list of the values of each node in the graph.

getEdges

public Vector getEdges()
Returns a list of all edges in the graph. The graph should not be changed while this Vector is being used.

Specified by:
getEdges in interface GraphModel
Returns:
A list of all edges in the graph.

getNodeCount

public int getNodeCount()
Returns the number of nodes in the graph.

Specified by:
getNodeCount in interface GraphModel
Returns:
The number of nodes in the graph.

getEdgeCount

public int getEdgeCount()
Returns the number of edges in the graph.

Specified by:
getEdgeCount in interface GraphModel
Returns:
the number of edges in the graph.

isDirected

public boolean isDirected()
Returns whether or not the graph is directed.

Specified by:
isDirected in interface GraphModel
Returns:
False, because instances of UndirectedGraph are undirected.

isSimple

public boolean isSimple()
Returns whether or not the graph is simple (ie - there are no edges from some node to itself and there is at most one edge between any two different nodes).

Specified by:
isSimple in interface GraphModel
Returns:
Whether or not the graph is simple.

getEdgesFromTo

public Vector getEdgesFromTo(Object sourceValue,
                             Object destValue)
Given the value of the source node and the destination node, this method will return a list of all edges going between the two nodes. If there are no edges going between the two nodes, this method will return an empty Vector. It is highly recommended that you do not modify the Vector returned.

Specified by:
getEdgesFromTo in interface GraphModel
Parameters:
sourceValue - The value of the source node.
destValue - The value of the destination node.
Returns:
A list of all edges going between the two nodes.

getEdgesFrom

public Vector getEdgesFrom(Object value)
Given the value of some node, this method will return a list of all edges originating at this node. The graph should not be changed until this enumeration is done being used.

Specified by:
getEdgesFrom in interface GraphModel
Parameters:
value - The value of some node in the graph.
Returns:
A list of the edges going from the associated node.

getEdgesTo

public Vector getEdgesTo(Object value)
Given the value of some node, this method will return a list of all edges ending at this node. The graph should not be changed until this enumeration is done being used.

Specified by:
getEdgesTo in interface GraphModel
Parameters:
value - The value of some node in the graph.
Returns:
A list of the edges going to the associated node.

removeNode

public void removeNode(Object value)
Given a node's value, this method will find and remove that node, and any associated edges from the graph.

Specified by:
removeNode in class AbstractGraphModel
Parameters:
value - The value of the node to be removed.

addNode

public void addNode(Object value)
This method adds a new node to the graph, and associates the parameter as the value of the node. If there exists a node in the graph with a value that is the same (according to .equals()) as the parameter, a RuntimException will be thrown with an error message stating that a graph cannot have two copies of the same node.

Specified by:
addNode in class AbstractGraphModel
Parameters:
value - The value of the node to be added.

removeEdge

public Object removeEdge(Edge toRemove)
This method will remove the edge from the graph. The cost of the edge removed will be returned.

Specified by:
removeEdge in class AbstractGraphModel
Parameters:
toRemove - The edge to be removed.
Returns:
The cost of the edge that was removed.

removeEdge

public Object removeEdge(Object sourceValue,
                         Object destinationValue,
                         Object cost)
This method will remove the edge with the indicated source and destination values from the graph. The cost of the edge removed will be returned.

Specified by:
removeEdge in class AbstractGraphModel
Parameters:
sourceValue - The value of the source node of the edge.
destinationValue - The value of the destination node of the edge.
cost - The cost of the edge to be removed.
Returns:
The cost of the edge that was removed.

addEdge

public void addEdge(Object sourceValue,
                    Object destinationValue,
                    Object cost)
This method will add a new edge to the graph. The new edge will have the indicated source value, destination value, and cost. If an edge was already in place between the indicated source and destination, this function will simply replace the old cost of that edge with the new cost. If either the sourceValue or destinationValue is not a value of a node in the graph, a RuntimeException will be thrown stating so in an error message.

Specified by:
addEdge in class AbstractGraphModel
Parameters:
sourceValue - The value of the source node of the new edge.
destinationValue - The value of the destination node of the new edge.
cost - The cost of the new edge.

addEdge

public void addEdge(Edge edge)
This method will add a new edge to the graph. If an edge was already in place between the indicated source and destination, this function will simply replace the old cost of that edge with the new cost. If either the sourceValue or destinationValue is not a value of a node in the graph, a RuntimeException will be thrown stating so in an error message.

Specified by:
addEdge in class AbstractGraphModel
Parameters:
edge - The edge to be added to the graph.

toString

public String toString()
Returns a basic string representation of this graph.

Returns:
A basic string representation of this graph.

toString

public String toString(boolean fullThing)
This method is implemented simply to keep with the possibility of a verbose representation of a Graph. UndirectedGraphs have succinct enough full representations to always return those, so we do.

Specified by:
toString in interface GraphModel
Parameters:
fullThing - Unused.
Returns:
A string representation of this graph.