beowulf.model.graph
Class Graph

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

public class Graph
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.1, 11/7/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
Graph()
          Basic and only constructor for a Graph.
Graph(boolean newUseDotEquals)
          Basic and only constructor for 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.
 void clear()
          This will remove all nodes and edges from the graph.
 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)
          If the boolean parameter is true, this method will return a full description of the graph in the form of a string.
 
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

Graph

public Graph()
Basic and only constructor for a Graph. Does the basic set up so that the Graph is usable.


Graph

public Graph(boolean newUseDotEquals)
Basic and only constructor for a Graph. Does the basic set up so that the Graph is usable. The only parameter tells the Graph whether or not to use .equals for object comparison.

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 until this enumeration is done being used.

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 until this enumeration is done 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. Always returns true.

Specified by:
isDirected in interface GraphModel
Returns:
True, because instances of Graph are directed.

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:
True if and only if 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. If the graph is changed, the Vector that was return will become invalid, and it is unspecified as to what its contents will be.

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.

clear

public void clear()
This will remove all nodes and edges from the graph. This is merely a convenience method that calls removeNode repeatedly.


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)
If the boolean parameter is true, this method will return a full description of the graph in the form of a string. Otherwise, the method will return the same string as .toString()

Specified by:
toString in interface GraphModel
Parameters:
fullThing - Whether or not to return a lengthy description.
Returns:
A string representation of this graph.