|
Search this API | ||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object y.layout.router.polyline.PathSearch
public class PathSearch
A pathfinding algorithm that calculates the shortest (that means the cheapest) paths for a set of edges through a
GraphPartition
.
It is based on an A*-algorithm and uses
PartitionCell
s as steps between source node and target node.
In each step, the algorithm takes a CellEntrance
, that consists mainly of a PartitionCell
and
from where it was entered, from a queue with all seen CellEntrance
s, determines all possible neighbor
cells and their enter intervals and enqueues the resulting CellEntrances
.
To influence the order in which the CellEntrance
s will be processed, the path search assigns real
costs (like Dijkstra) as well as heuristic costs (A*-algorithm's heuristic) to the enqueued
CellEntrance
s. The real costs arise from entering a neighbor cell, e.g. a bend has to be created,
while the heuristic costs are an estimation of how expensive it will be to reach the target node continuing the
path with this neighbor cell. Therefor, the path search prefers searching in the direction where the target node
lies. The CellEntrance
with the lowest combined costs is processed next until a target cell is reached.
PathSearchExtension
s modify the path search as they are able to add start
entrances and weigh them with costs. They also add real and heuristic costs to CellEntrance
s that are
created for the currently entered PartitionCell
and calculate shorter enter intervals that are less
expensive to pass.
The algorithm gets a PathSearchContext
which provides information about the graph and the currently routed
edge. It also stores the results of the path search that can be retrieved calling
PathSearchContext.getPathSearchResult()
.
addPathSearchExtension(PathSearchExtension)
,
addAdditionalEnterIntervalCalculator(EnterIntervalCalculator)
Constructor Summary | |
---|---|
PathSearch()
Creates a new instance |
Method Summary | |
---|---|
boolean |
addAdditionalEnterIntervalCalculator(EnterIntervalCalculator enterIntervalCalculator)
Adds a new interval calculator to the list of registered interval calculators. |
boolean |
addPathSearchExtension(PathSearchExtension extension)
Adds the given extension to the list of path search extensions. |
protected double[] |
calculateCosts(CellEntrance currentEntrance,
PartitionCell enteredCell,
OrthogonalInterval[] enterIntervals,
EdgeCellInfo[] lastEdgeCellInfos,
PathSearchContext context,
double[] maxAllowedCosts)
Returns the costs for getting from the current CellEntrance to the neighboring PartitionCell using
different enter intervals. |
protected double |
calculateHeuristicCosts(CellEntrance entrance,
PathSearchContext context)
Returns estimated costs for the rest of the path when using the given CellEntrance for the next step in
path search. |
void |
clear()
Resets all registered path search extensions and DataProviders added by PathSearch . |
protected void |
decreasePenaltySettings(PenaltySettings penaltySettings,
double decreaseFactor,
PathSearchContext context)
Decreases the given penalty settings for the current edge. |
protected void |
finalizePath(Path path)
Informs all registered path search extensions about completing a path by calling their finalizePath(Path) method. |
void |
findPaths(PathSearchContext context)
Finds paths for the edges in the given context and stores them in its PathSearchResult . |
protected void |
findPathsForCurrentEdge(PathSearchContext context)
Finds the path for the current edge in the given context. |
Path |
getFinalizedPath(Edge edge)
Returns the path for the given edge, if it has been finalized already. |
protected void |
handleNeighbor(CellEntrance currentEntrance,
PartitionCell neighborCell,
PathSearchContext context)
Adds CellEntrance s for every interval through which the neighbor cell can be entered from the current
entrance to the queue. |
void |
init(PathSearchConfiguration configuration)
Initializes the path search. |
boolean |
removeAdditionalEnterIntervalCalculator(EnterIntervalCalculator enterIntervalCalculator)
Removes the given interval calculator from the list of registered interval calculators. |
boolean |
removePathSearchExtension(PathSearchExtension extension)
Removes the given extension from the list of path search extensions. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
---|
public PathSearch()
Method Detail |
---|
public boolean addPathSearchExtension(PathSearchExtension extension)
extension
- The extension to add to this path search.
true
, if the extension has been added, false
otherwise.public boolean removePathSearchExtension(PathSearchExtension extension)
extension
- The extension to remove from the path search.
true
, if an extension was removed as a result of this call.public boolean addAdditionalEnterIntervalCalculator(EnterIntervalCalculator enterIntervalCalculator)
enterIntervalCalculator
- The calculator to add.
true
, if the calculator could be added, false
otherwise.public boolean removeAdditionalEnterIntervalCalculator(EnterIntervalCalculator enterIntervalCalculator)
enterIntervalCalculator
- The calculator to remove.
true
, if an interval calculator was removed as a result of this call.public void init(PathSearchConfiguration configuration)
This method also calls PathSearchExtension.initialize(PathSearchConfiguration)
for all registered
path search extensions.
configuration
- The configuration, the path search shall use.public void clear()
DataProviders
added by PathSearch
. So,
PathSearch
is ready to calculate paths for a new layout.
PathSearchExtension.cleanup()
public Path getFinalizedPath(Edge edge)
edge
- The edge to return the path for.
null
if no path has been found and finalized.protected void findPathsForCurrentEdge(PathSearchContext context)
PathSearchExtension.initializeCurrentEdge(PathSearchContext)
for all extensionsfinalizePath(Path)
call if it is a valid target entrance and/orhandleNeighbor(CellEntrance, PartitionCell, PathSearchContext)
for all neighbor cells of the entered cellPathSearchExtension.finalizeCurrentEdge(PathSearchContext)
for all extensions
protected void decreasePenaltySettings(PenaltySettings penaltySettings, double decreaseFactor, PathSearchContext context)
If finding a path for the current edge takes too long according to the maximum duration of the edge router,
the path search for the current edge is canceled and restarted using decreased penalties. The
decreaseFactor
indicates, how strong the penalties shall be reduced.
If overriding this method please note that the penalty for creating bends should not be reduced as this results in more possible turns of the edge path and therefore a longer runtime of the path search. Furthermore not all penalties should be decreased equally as these decreases would neutralize each other.
penaltySettings
- The penalty settings whose penalties shall be reduced.decreaseFactor
- A factor with values between 0 and 1 that indicates how strong to reduce the penalties.
0 means no reduction while 1 means to strongest reduction.context
- The context of the current path search.public void findPaths(PathSearchContext context)
PathSearchResult
.
It initializes its extensions using PathSearchExtension.initializeEdges(PathSearchContext)
and
delegates the path search for each edge to findPathsForCurrentEdge(PathSearchContext)
.
The paths calculations for all edges are finalized by calling the extensions'
PathSearchExtension.finalizeEdges(PathSearchContext)
method and after that the path search result
if filled with the path for each edge.
At last the extensions are asked to finalize the path search result using their
PathSearchExtension.finalizePathSearchResult(PathSearchResult)
callback.
context
- The context to use during the path search.PathSearchContext.getEdges()
,
PathSearchContext.getPathSearchResult()
protected void finalizePath(Path path)
finalizePath(Path)
method. That way, extensions can collect data about this
path to use it later in path search.
path
- The path to finalize.protected void handleNeighbor(CellEntrance currentEntrance, PartitionCell neighborCell, PathSearchContext context)
CellEntrance
s for every interval through which the neighbor cell can be entered from the current
entrance to the queue. The algorithm calls this method in every step for every neighbor of the current cell to
collect all next possible entrances for the current path. This path consists of several entrances where each knows
the entrance they were entered through.
After calculating all possible enter intervals to the given neighbor cell, each interval gets rated with costs.
If there already is an entrance for the neighbor cell whose interval is the same as one of these intervals, this
entrance will be used and re-enqueued, so the path search can still reach it. The current entrance is set as its
predecessor within the current path and its enter interval and costs will be updated.
If there is an entrance for the neighbor cell whose interval is intersected by a current interval, new entrances
will be created with the new enter intervals and enqueued. The same happens if there is no entrance that matches
one of the current intervals, yet. Costs will be added.
If there are some entries afterwards, that are intersected by the current interval and have higher costs, they
will be removed from the queue.
currentEntrance
- the current cell entranceneighborCell
- the neighbor cell that is handled.context
- context informationcalculateCosts(CellEntrance, PartitionCell, OrthogonalInterval[], EdgeCellInfo[], PathSearchContext, double[])
,
calculateHeuristicCosts(CellEntrance, PathSearchContext)
protected double[] calculateCosts(CellEntrance currentEntrance, PartitionCell enteredCell, OrthogonalInterval[] enterIntervals, EdgeCellInfo[] lastEdgeCellInfos, PathSearchContext context, double[] maxAllowedCosts)
CellEntrance
to the neighboring PartitionCell
using
different enter intervals. It is called by handleNeighbor(CellEntrance, PartitionCell, PathSearchContext)
to determine the costs for all CellEntrance
s that it will create and enqueue afterwards.
The costs for the given enter intervals are retrieved from all registered PathSearchExtension
s. The calculation stops when it reaches the given maximum cost value.
currentEntrance
- the current cell entrance.enteredCell
- the cell to enter.enterIntervals
- the different entering intervals of the entered cell.lastEdgeCellInfos
- information about how the last cell was crossed.context
- context information.maxAllowedCosts
- the maximum costs an enter interval may induce. If this cost is exceeded, no further
additional costs for this interval are calculated.
PathSearchExtension.calculateCosts(CellEntrance, PartitionCell, OrthogonalInterval, EdgeCellInfo, double)
protected double calculateHeuristicCosts(CellEntrance entrance, PathSearchContext context)
CellEntrance
for the next step in
path search. It is called by handleNeighbor(CellEntrance, PartitionCell, PathSearchContext)
to determine the heuristic part of the costs the entrance will be enqueued with.
The heuristic costs for the given entrance are retrieved from all registered PathSearchExtension
s.
entrance
- The current entrance.context
- Context information.
PathSearchExtension.calculateHeuristicCosts(CellEntrance)
|
© Copyright 2000-2013, yWorks GmbH. All rights reserved. |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |