gishur.graph.core
Class DijkstraCursor

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

public class DijkstraCursor
extends TraverseAlgorithmCursor

An implementation of the Single Source Shortest Paths problem using the Dijkstra algorithm via a TraverseAlgorithmCursor. The Algorithm sets the following node properties: "ShortestPaths": Only for the source! This is a HashTable containing all the nodes of the graph as keys and the shortest path distances to these nodes as values. "ShortestPath.Predecessor.": only of the pred flag is set in the constructor! This property contains the previous node on the shortest path from the source (for the source node and nodes unreachable from the source, this property is not defined) count ist total ueberfluessig!!!!!!??????? Die Funktion set(Graphelement) wurde entfernt!!! _source darf nicht geaender werden!!! (hoechstens wenn vorher alle Properties und die gesamte _queue geloeschwerden!!!)

Version:
1.0
Author:
Simon Weidmann

Field Summary
static byte BOTH_MODE
          Mode-constant: use incoming and outgoing edges.
static int DIJKSTRA_COLOR_BLACK
           
static int DIJKSTRA_COLOR_BLUE
           
static int DIJKSTRA_COLOR_GRAY
           
static int DIJKSTRA_COLOR_GREEN
           
static int DIJKSTRA_COLOR_RED
           
static int DIJKSTRA_COLOR_WHITE
           
static int DIJKSTRA_STEP
          Trace label constant indicating that the algorithm has made one step forward.
static byte IN_MODE
          Mode-constant: use only incoming edges.
static byte OUT_MODE
          Mode-constant: use only outgoing edges.
 
Constructor Summary
DijkstraCursor(Graph graph, Node source, boolean pred, java.lang.String cost, java.util.Hashtable sp)
          Constructs a DijkstraCursor on the given Graph starting at the given Node.
DijkstraCursor(Graph graph, Node source, boolean pred, java.lang.String cost, java.lang.String mark_prefix)
          Constructs a DijkstraCursor on the given Graph starting at the given Node.
DijkstraCursor(Graph graph, Node source, byte mode, boolean pred, java.lang.String cost, java.util.Hashtable sp)
          Constructs a DijkstraCursor on the given Graph starting at the given Node with the specified mode.
DijkstraCursor(Graph graph, Node source, byte mode, boolean pred, java.lang.String cost, java.lang.String mark_prefix, Tracer tracer)
          Constructs a DijkstraCursor 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 DijkstraCursor (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.
 byte setMode(byte mode)
          Sets the working mode of this DijkstraCursor.
 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, set, 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

DIJKSTRA_COLOR_WHITE

public static final int DIJKSTRA_COLOR_WHITE

DIJKSTRA_COLOR_GRAY

public static final int DIJKSTRA_COLOR_GRAY

DIJKSTRA_COLOR_BLACK

public static final int DIJKSTRA_COLOR_BLACK

DIJKSTRA_COLOR_RED

public static final int DIJKSTRA_COLOR_RED

DIJKSTRA_COLOR_GREEN

public static final int DIJKSTRA_COLOR_GREEN

DIJKSTRA_COLOR_BLUE

public static final int DIJKSTRA_COLOR_BLUE

DIJKSTRA_STEP

public static final int DIJKSTRA_STEP
Trace label constant indicating that the algorithm has made one step forward.

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

DijkstraCursor

public DijkstraCursor(Graph graph,
                      Node source,
                      boolean pred,
                      java.lang.String cost,
                      java.util.Hashtable sp)
Constructs a DijkstraCursor on the given Graph starting at the given Node. The cursor position after creation is the first element.
Parameters:
graph - Graph to work on
source - Node to start from

DijkstraCursor

public DijkstraCursor(Graph graph,
                      Node source,
                      byte mode,
                      boolean pred,
                      java.lang.String cost,
                      java.util.Hashtable sp)
Constructs a DijkstraCursor 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
source - Node to start from
mode - the mode (see setMode(byte))

DijkstraCursor

public DijkstraCursor(Graph graph,
                      Node source,
                      boolean pred,
                      java.lang.String cost,
                      java.lang.String mark_prefix)
Constructs a DijkstraCursor on the given Graph starting at the given Node. The cursor position after creation is the first element.
Parameters:
graph - Graph to work on
source - Node to start from

DijkstraCursor

public DijkstraCursor(Graph graph,
                      Node source,
                      byte mode,
                      boolean pred,
                      java.lang.String cost,
                      java.lang.String mark_prefix,
                      Tracer tracer)
Constructs a DijkstraCursor 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
source - Node to start from
mode - the mode (see setMode(byte))
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 DijkstraCursor (one constant of {OUT_MODE,IN_MODE,BOTH_MODE}).
Returns:
the working mode of this DijkstraCursor.

setMode

public byte setMode(byte mode)
Sets the working mode of this DijkstraCursor. The given mode constant defines, which edges the 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

initStructures

protected void initStructures()
Initializes data structures. This method will be called, if the cursor Tidy up: delete local queue and all the local properties of nodes contained in the queue 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.