gishur.graph.core
Class TraverseAlgorithmCursor

java.lang.Object
  |
  +--gishur.core.CursorAdapter
        |
        +--gishur.graph.core.GraphCursor
              |
              +--gishur.graph.core.TraverseAlgorithmCursor
All Implemented Interfaces:
Cursor, java.util.Enumeration
Direct Known Subclasses:
BFSCursor, DFSCursor, DijkstraCursor

public abstract class TraverseAlgorithmCursor
extends GraphCursor

This class should be used to implement Graph-Traversals. Although it extends the GraphCursor class, backward navigation is realized just as simple 'n-1' forward steps from the beginning. If one likes to traverse a graph and then navigate on the traversal, one should use the TraverseCursor in conjunction with this class.

The implementation of new algorithms should be easy; just overwrite the selectFirst() and selectNext(...) methods properly. In order to make backward navigation possible, one should also overwrite the rollback(...)-methods. A simple execution of the algorithm can be performed via execute(), otherwise it can be used like a normal GraphCursor.

A TraverseAlgorithmCursor makes property entries on the GraphElements under a special prefix. Via setting 'local' properties one can make more temporary entries on the traversed elements. These entries should also be removed by backward stepping (see rollback(...)). The local entries with the local keys "next" and "prev" are written and removed automatically. They can be read via the various getProperty(...)-methods.

Version:
1.0
Author:
Thomas Wolf

Constructor Summary
protected TraverseAlgorithmCursor(Graph g)
          Constructor.
 
Method Summary
 void addFilter(Filter f)
          Adds a Filter to the Filter-pipeline so that the move of the Cursor will furthermore happen on only these elments which are not filtered out by f and the other registered Filters.
 void bottom()
          Sets the Cursor to the last element.
 java.lang.String cursorID()
          Returns the cursor id.
protected  GraphCursor edges(Node n)
          Returns a GraphCursor, that enumerates the connected Edges of the specified Node.
 java.lang.Object element()
          Returns the element to which this Cursor points at the moment.
 void execute()
          Executes the TraverseAlgorithmCursor, that means, the cursor traverses the whole Graph to the end.
 boolean getBoolProperty(GraphElement e, java.lang.String key)
          Method to get a property value which is not an object, but a boolean.
 double getDoubleProperty(GraphElement e, java.lang.String key)
          Method to get a property value which is not an object, but a double.
 Edge getEdgeProperty(GraphElement e, java.lang.String key)
          Returns a property value like getProperty(gishur.graph.core.GraphElement, java.lang.String) which is casted to Edge, if this is possible, otherwise null.
 float getFloatProperty(GraphElement e, java.lang.String key)
          Method to get a property value which is not an object, but a float.
 GraphElement getGraphElementProperty(GraphElement e, java.lang.String key)
          Returns a property value like getProperty(gishur.graph.core.GraphElement, java.lang.String) which is casted to GraphElement, if this is possible, otherwise null.
 int getIntProperty(GraphElement e, java.lang.String key)
          Method to get a property value which is not an object, but an int.
 long getLongProperty(GraphElement e, java.lang.String key)
          Method to get a property value which is not an object, but a long.
 Node getNodeProperty(GraphElement e, java.lang.String key)
          Returns a property value like getProperty(gishur.graph.core.GraphElement, java.lang.String) which is casted to Node, if this is possible, otherwise null.
 java.lang.Object getProperty(GraphElement e, java.lang.String key)
          Returns a property value stored locally at the given GraphElement specific to this TraverseAlgorithmCursor, specified by key.
 short getShortProperty(GraphElement e, java.lang.String key)
          Method to get a property value which is not an object, but a short.
 Graph graph()
          Returns the Graph, on which the Cursor works.
 GraphElement graphElement()
          Returns the element under the actual position as an GraphElement, if this is possible (i.e. the position is valid and points to an GraphElement.
protected  boolean hasProperty(GraphElement e, java.lang.String key)
          Returns true, if a property with the given key specific to this TraverseAlgorithmCursor exists.
protected  GraphCursor inEdges(Node n)
          Returns a GraphCursor, that enumerates the incoming Edges of the specified Node.
protected  void initStructures()
          Initializes data structures.
protected  GraphCursor inNodes(GraphElement e)
          Returns a GraphCursor, that enumerates the source Nodes of the incoming Edges of the specified Node or Edge.
 void invalidate()
          Sets the Cursor to an invalid position.
 int length()
          Returns the number of elements in the underlying structure of this Cursor.
protected  GraphCursor nodes(GraphElement e)
          Returns a GraphCursor, that enumerates the (other) Nodes of the connected Edges of the specified Node or Edge.
protected  GraphCursor outEdges(Node n)
          Returns a GraphCursor, that enumerates the outgoing Edges of the specified Node.
protected  GraphCursor outNodes(GraphElement e)
          Returns a GraphCursor, that enumerates the target Nodes of the outgoing Edges of the specified Node or Edge.
 void relative(int step)
          Moves the Cursor step positions within the underlying structure.
 void removeFilter(Filter f)
          Removes f from the Filter pipeline of this GraphCursor.
protected  java.lang.Object removeProperty(GraphElement e, java.lang.String key)
          Removes the property defined by key specific to this TraverseAlgorithmCursor and returns its value.
protected  void rollback(GraphElement e)
          Makes the last traverse step (see selectNext(gishur.graph.core.GraphElement)) undone.
protected abstract  GraphElement selectFirst()
          Selects the first GraphElement of the Graph according to the traversal strategy.
protected abstract  GraphElement selectNext(GraphElement e)
          Selects the next GraphElement of the Graph after the given according to the traversal strategy.
 void set(GraphElement e)
          Sets the TraverseAlgorithmCursor to a new (start) element.
protected  void setProperty(GraphElement e, java.lang.String key, boolean value)
          Sets a boolean-value as value.
protected  void setProperty(GraphElement e, java.lang.String key, double value)
          Sets a double-value as value.
protected  void setProperty(GraphElement e, java.lang.String key, float value)
          Sets a float-value as value.
protected  void setProperty(GraphElement e, java.lang.String key, int value)
          Sets an int-value as value.
protected  void setProperty(GraphElement e, java.lang.String key, long value)
          Sets a long-value as value.
protected  void setProperty(GraphElement e, java.lang.String key, java.lang.Object value)
          Sets a property of the given GraphElement specific to this TraverseAlgorithmCursor, specified by the String key to the given value.
protected  void setProperty(GraphElement e, java.lang.String key, short value)
          Sets a short-value as value.
 java.lang.String toString()
          Overrides java.lang.Object.toString().
 boolean valid()
          Checks if the Cursor's actual position is valid.
 
Methods inherited from class gishur.graph.core.GraphCursor
edge, filter, isEdge, isNode, node, validElement
 
Methods inherited from class gishur.core.CursorAdapter
getBookmark, hasMoreElements, next, next, nextElement, prev, prev, set, set, top
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Constructor Detail

TraverseAlgorithmCursor

protected TraverseAlgorithmCursor(Graph g)
Constructor. After construction the TraverseAlgorithmCursor should be invalid. This cannot be done securly by this class. Be shure to call invalidate() at the end of subclass-constructors!
Method Detail

toString

public java.lang.String toString()
Overrides java.lang.Object.toString().
Overrides:
toString in class java.lang.Object
See Also:
Object.toString()

cursorID

public java.lang.String cursorID()
Returns the cursor id.
Returns:
the cursor id.

initStructures

protected void initStructures()
Initializes data structures. This method will be called, if the cursor invalidates (before the first step).

selectFirst

protected abstract GraphElement selectFirst()
Selects the first GraphElement of the Graph according to the traversal strategy. Filtering will be done after this method. This method must be overwritten properly.
Returns:
the next GraphElement according to the travesal.

selectNext

protected abstract GraphElement selectNext(GraphElement e)
Selects the next GraphElement of the Graph after the given according to the traversal strategy. The given GraphElement specifies the step/position to step from. (This has nothing to do with the Cursor position!) This method must be overwritten properly.
Parameters:
e - the actual GraphElement
Returns:
the next GraphElement according to the travesal.

rollback

protected void rollback(GraphElement e)
Makes the last traverse step (see selectNext(gishur.graph.core.GraphElement)) undone. The given GraphElement specifies the step/position to make undone. (This has nothing to do with the Cursor position!) This method should be overwritten properly. Otherwise a GraphException will be thrown, if a function needs to call this method; the cursor can only be used as enumeration.
Parameters:
e - the actual GraphElement

set

public void set(GraphElement e)
Sets the TraverseAlgorithmCursor to a new (start) element. This method should be overwritten properly. Otherwise a GraphException will be thrown.
Overrides:
set in class GraphCursor
Parameters:
e - the new GraphElement to set the cursor to

graph

public Graph graph()
Returns the Graph, on which the Cursor works.
Overrides:
graph in class GraphCursor
Returns:
the Graph, on which the Cursor works.

element

public java.lang.Object element()
Returns the element to which this Cursor points at the moment.
Returns:
the element "under" the Cursor

graphElement

public GraphElement graphElement()
Returns the element under the actual position as an GraphElement, if this is possible (i.e. the position is valid and points to an GraphElement.
Overrides:
graphElement in class GraphCursor
Returns:
the element on the actual position as an GraphElement

relative

public void relative(int step)
Moves the Cursor step positions within the underlying structure.
Parameters:
step - the number of elements to move

valid

public boolean valid()
Checks if the Cursor's actual position is valid.
Returns:
true, if the Cursor points to a valid position, and false otherwise

invalidate

public void invalidate()
Sets the Cursor to an invalid position.

length

public int length()
Returns the number of elements in the underlying structure of this Cursor.
Returns:
the number of elements in the underlying structure

bottom

public void bottom()
Sets the Cursor to the last element.
Overrides:
bottom in class CursorAdapter

execute

public void execute()
Executes the TraverseAlgorithmCursor, that means, the cursor traverses the whole Graph to the end.

addFilter

public void addFilter(Filter f)
Adds a Filter to the Filter-pipeline so that the move of the Cursor will furthermore happen on only these elments which are not filtered out by f and the other registered Filters. If f==null nothing happens and the method returns.
Overrides:
addFilter in class GraphCursor
Parameters:
f - the new Filter to add to the pipeline

removeFilter

public void removeFilter(Filter f)
Removes f from the Filter pipeline of this GraphCursor. If f==null or f is not part of the Filter pipe, the method returns effectiveless.
Overrides:
removeFilter in class GraphCursor
Parameters:
f - the Filter to remove

outEdges

protected final GraphCursor outEdges(Node n)
Returns a GraphCursor, that enumerates the outgoing Edges of the specified Node.
Parameters:
n - the given Node
Returns:
a GraphCursor, that enumerates the outgoing Edges

inEdges

protected final GraphCursor inEdges(Node n)
Returns a GraphCursor, that enumerates the incoming Edges of the specified Node.
Parameters:
n - the given Node
Returns:
a GraphCursor, that enumerates the incoming Edges

edges

protected final GraphCursor edges(Node n)
Returns a GraphCursor, that enumerates the connected Edges of the specified Node.
Parameters:
n - the given Node
Returns:
a GraphCursor, that enumerates the connected Edges

outNodes

protected final GraphCursor outNodes(GraphElement e)
Returns a GraphCursor, that enumerates the target Nodes of the outgoing Edges of the specified Node or Edge.
Parameters:
e - the given Node or Edge
Returns:
a GraphCursor

inNodes

protected final GraphCursor inNodes(GraphElement e)
Returns a GraphCursor, that enumerates the source Nodes of the incoming Edges of the specified Node or Edge.
Parameters:
e - the given Node or Edge
Returns:
a GraphCursor

nodes

protected final GraphCursor nodes(GraphElement e)
Returns a GraphCursor, that enumerates the (other) Nodes of the connected Edges of the specified Node or Edge.
Parameters:
e - the given Node or Edge
Returns:
a GraphCursor

setProperty

protected void setProperty(GraphElement e,
                           java.lang.String key,
                           java.lang.Object value)
Sets a property of the given GraphElement specific to this TraverseAlgorithmCursor, specified by the String key to the given value.
Parameters:
e - the GraphElement, where the property should be stored
key - the key-string specifying the property to change
value - the value to set as property
Throws:
java.lang.NullPointerExecption - if key or value is null

hasProperty

protected boolean hasProperty(GraphElement e,
                              java.lang.String key)
Returns true, if a property with the given key specific to this TraverseAlgorithmCursor exists.
Parameters:
e - the GraphElement, where the property should be stored
key - the key value
Returns:
true if the specified property is contained

getProperty

public java.lang.Object getProperty(GraphElement e,
                                    java.lang.String key)
Returns a property value stored locally at the given GraphElement specific to this TraverseAlgorithmCursor, specified by key.
Parameters:
e - the GraphElement, where the property should be stored
key - the key-string specifying the property to return
Returns:
the property value stored with key key or null, if no such key has been found

removeProperty

protected java.lang.Object removeProperty(GraphElement e,
                                          java.lang.String key)
Removes the property defined by key specific to this TraverseAlgorithmCursor and returns its value. If the given key does not specify a valid property, null will be returned.
Parameters:
e - the GraphElement, where the property should be stored
key - the key specifying the property to remove
Returns:
the value which was mapped to this key in the properties

setProperty

protected void setProperty(GraphElement e,
                           java.lang.String key,
                           int value)
Sets an int-value as value.

setProperty

protected void setProperty(GraphElement e,
                           java.lang.String key,
                           short value)
Sets a short-value as value.

setProperty

protected void setProperty(GraphElement e,
                           java.lang.String key,
                           long value)
Sets a long-value as value.

setProperty

protected void setProperty(GraphElement e,
                           java.lang.String key,
                           float value)
Sets a float-value as value.

setProperty

protected void setProperty(GraphElement e,
                           java.lang.String key,
                           double value)
Sets a double-value as value.

setProperty

protected void setProperty(GraphElement e,
                           java.lang.String key,
                           boolean value)
Sets a boolean-value as value.

getIntProperty

public int getIntProperty(GraphElement e,
                          java.lang.String key)
Method to get a property value which is not an object, but an int.
Parameters:
e - the GraphElement, where the property should be stored
key - the key-string specifying the property to return
Returns:
the property value stored with key key

getShortProperty

public short getShortProperty(GraphElement e,
                              java.lang.String key)
Method to get a property value which is not an object, but a short.
Parameters:
e - the GraphElement, where the property should be stored
key - the key-string specifying the property to return
Returns:
the property value stored with key key

getLongProperty

public long getLongProperty(GraphElement e,
                            java.lang.String key)
Method to get a property value which is not an object, but a long.
Parameters:
e - the GraphElement, where the property should be stored
key - the key-string specifying the property to return
Returns:
the property value stored with key key

getFloatProperty

public float getFloatProperty(GraphElement e,
                              java.lang.String key)
Method to get a property value which is not an object, but a float.
Parameters:
e - the GraphElement, where the property should be stored
key - the key-string specifying the property to return
Returns:
the property value stored with key key

getDoubleProperty

public double getDoubleProperty(GraphElement e,
                                java.lang.String key)
Method to get a property value which is not an object, but a double.
Parameters:
e - the GraphElement, where the property should be stored
key - the key-string specifying the property to return
Returns:
the property value stored with key key

getBoolProperty

public boolean getBoolProperty(GraphElement e,
                               java.lang.String key)
Method to get a property value which is not an object, but a boolean.
Parameters:
e - the GraphElement, where the property should be stored
key - the key-string specifying the property to return
Returns:
the property value stored with key key

getGraphElementProperty

public GraphElement getGraphElementProperty(GraphElement e,
                                            java.lang.String key)
Returns a property value like getProperty(gishur.graph.core.GraphElement, java.lang.String) which is casted to GraphElement, if this is possible, otherwise null.
Parameters:
e - the GraphElement, where the property should be stored
key - the key-string specifying the property to return
Returns:
the GraphElement stored with key key

getNodeProperty

public Node getNodeProperty(GraphElement e,
                            java.lang.String key)
Returns a property value like getProperty(gishur.graph.core.GraphElement, java.lang.String) which is casted to Node, if this is possible, otherwise null.
Parameters:
e - the GraphElement, where the property should be stored
key - the key-string specifying the property to return
Returns:
the Node stored with key key

getEdgeProperty

public Edge getEdgeProperty(GraphElement e,
                            java.lang.String key)
Returns a property value like getProperty(gishur.graph.core.GraphElement, java.lang.String) which is casted to Edge, if this is possible, otherwise null.
Parameters:
e - the GraphElement, where the property should be stored
key - the key-string specifying the property to return
Returns:
the Edge stored with key key