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
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. |
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 java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
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.
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 onsource
- 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 onsource
- Node
to start frommode
- 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 onsource
- 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 onsource
- Node
to start frommode
- the mode (see setMode(byte)
)
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.