gishur.graph.core
Class DFSCursor

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

public class DFSCursor
extends TraverseAlgorithmCursor

An implementation of the well-known Depth-First-Search algorithm via a TraverseAlgorithmCursor.

Version:
1.0
Author:
Thomas Wolf

Field Summary
static byte BOTH_MODE
          Mode-constant: use incoming and outgoing edges.
static int DFS_COLOR_BLACK
           
static int DFS_COLOR_GRAY
           
static int DFS_COLOR_WHITE
           
static byte IN_MODE
          Mode-constant: use only incoming edges.
static byte OUT_MODE
          Mode-constant: use only outgoing edges.
 
Constructor Summary
DFSCursor(Graph graph, Node start)
          Constructs a DFSCursor on the given Graph starting at the given Node.
DFSCursor(Graph graph, Node start, byte mode)
          Constructs a DFSCursor on the given Graph starting at the given Node with the specified mode.
DFSCursor(Graph graph, Node start, byte mode, java.lang.String mark_prefix)
          Constructs a DFSCursor on the given Graph starting at the given Node with the specified mode.
 
Method Summary
 void addLocalFilter(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.
protected  void initStructures()
          Initializes data structures.
 byte mode()
          Returns the working mode of this BFSCursor (one constant of {OUT_MODE,IN_MODE,BOTH_MODE}).
 void removeLocalFilter(Filter f)
          Removes f from the Filter pipeline of this GraphCursor.
protected  GraphElement selectFirst()
          Selects the first GraphElement of the Graph according to the traversal strategy.
protected  GraphElement selectNext(GraphElement e)
          Selects the next GraphElement of the Graph after the given according to the traversal strategie.
 void set(GraphElement e)
          Sets the DFSCursor to a new (start) element.
 byte setMode(byte mode)
          Sets the working mode of this BFSCursor.
 java.lang.String toString()
          Overrides java.lang.Object.toString().
 
Methods inherited from class gishur.graph.core.TraverseAlgorithmCursor
addFilter, bottom, cursorID, edges, element, execute, getBoolProperty, getDoubleProperty, getEdgeProperty, getFloatProperty, getGraphElementProperty, getIntProperty, getLongProperty, getNodeProperty, getProperty, getShortProperty, graph, graphElement, hasProperty, inEdges, inNodes, invalidate, length, nodes, outEdges, outNodes, relative, removeFilter, removeProperty, rollback, setProperty, setProperty, setProperty, setProperty, setProperty, setProperty, setProperty, 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
 

Field Detail

DFS_COLOR_WHITE

public static final int DFS_COLOR_WHITE

DFS_COLOR_GRAY

public static final int DFS_COLOR_GRAY

DFS_COLOR_BLACK

public static final int DFS_COLOR_BLACK

OUT_MODE

public static final byte OUT_MODE
Mode-constant: use only outgoing edges.

IN_MODE

public static final byte IN_MODE
Mode-constant: use only incoming edges.

BOTH_MODE

public static final byte BOTH_MODE
Mode-constant: use incoming and outgoing edges.
Constructor Detail

DFSCursor

public DFSCursor(Graph graph,
                 Node start,
                 byte mode,
                 java.lang.String mark_prefix)
Constructs a DFSCursor on the given Graph starting at the given Node with the specified mode. The cursor position after creation is invalid. If mark_prefix!=null, the cursor writes its results to the properties of the Nodes and Edges it traverses, namely the following:

Properties Summary
Key Value Type Values Meaning
mark_prefix.color int DFS_COLOR_WHITE, DFS_COLOR_GRAY or DFS_COLOR_BLACK. White indicates an undiscovered Node, gray a Node whose descendants have not been visited completely, and black identifies a completely visited Node. Edges can only be colored black to indicate that they are part of the DFS-tree.
mark_prefix.dtime int 1 - ... The discovery time of a Node. Each discovery of a Node and each finishing of a visit takes one time unit.
mark_prefix.ftime int 2 - ... The finishing time of a Node. A Node is 'discovered' when all Nodes reachable from him has been visited. Each discovery of a Node and each finishing of a visit takes one time unit.

The properties will not be removed, if the cursor moves backward. Only if a GraphElement is discoverd again, its properties will be reset.
Parameters:
graph - Graph to work on
start - Node to start from
mode - the mode (see setMode(byte))
mark_prefix - the prefix used to make DFS-marking

DFSCursor

public DFSCursor(Graph graph,
                 Node start,
                 byte mode)
Constructs a DFSCursor on the given Graph starting at the given Node with the specified mode. The cursor position after creation is the first element.
Parameters:
graph - Graph to work on
start - Node to start from
mode - the mode (see setMode(byte))

DFSCursor

public DFSCursor(Graph graph,
                 Node start)
Constructs a DFSCursor on the given Graph starting at the given Node. The cursor position after creation is the first element.
Parameters:
graph - Graph to work on
start - Node to start from
Method Detail

toString

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

mode

public byte mode()
Returns the working mode of this BFSCursor (one constant of {OUT_MODE,IN_MODE,BOTH_MODE}).
Returns:
the working mode of this BFSCursor.

setMode

public byte setMode(byte mode)
Sets the working mode of this BFSCursor. The given mode constant defines, which edges the Breath-First-Search-Algorithm takes. Setting the working mode invalidates the whole cursor (see TraverseAlgorithmCursor.invalidate()).
Parameters:
mode - working mode constant (one of {OUT_MODE, IN_MODE,BOTH_MODE})
Returns:
the former mode

addLocalFilter

public void addLocalFilter(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.
Parameters:
f - the new Filter to add to the pipeline

removeLocalFilter

public void removeLocalFilter(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.
Parameters:
f - the Filter to remove

set

public void set(GraphElement e)
Sets the DFSCursor to a new (start) element. The method accepts only Nodes, that must be contained by the Graph, where this GraphCursor works on. Otherwise a IllegalArgumentException will be thrown.
Overrides:
set in class TraverseAlgorithmCursor
Parameters:
e - the new GraphElement to set the cursor to

initStructures

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

selectFirst

protected GraphElement selectFirst()
Selects the first GraphElement of the Graph according to the traversal strategy. Filtering will be done after this method.
Overrides:
selectFirst in class TraverseAlgorithmCursor
Returns:
the next GraphElement according to the travesal.

selectNext

protected GraphElement selectNext(GraphElement e)
Selects the next GraphElement of the Graph after the given according to the traversal strategie. The given GraphElement specifies the step/position to step from. (This has nothing to do with the Cursor position!)
Overrides:
selectNext in class TraverseAlgorithmCursor
Parameters:
e - the actual GraphElement
Returns:
the next GraphElement according to the travesal.