| Package | com.yworks.yfiles.layout.router.polyline |
| Class | public class PathSearch |
| Inheritance | PathSearch  YObject Object |
It is based on an A*-algorithm and uses com.yworks.yfiles.layout.router.polyline.PartitionCell s as steps between source node and target node. In each step, the algorithm takes a com.yworks.yfiles.layout.router.polyline.CellEntrance, that consists mainly of a PartitionCell and from where it was entered, from a queue with all seen CellEntrances, determines all possible neighbor cells and their enter intervals and enqueues the resulting CellEntrances. To influence the order in which the CellEntrances will be processed, the path search assigns real costs (like Dijkstra) as well as heuristic costs (A*-algorithm's heuristic) to the enqueued CellEntrances. 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 (com.yworks.yfiles.layout.router.polyline.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 CellEntrances that are created for the currently entered PartitionCell and calculate shorter enter intervals that are less expensive to pass.
The algorithm gets a com.yworks.yfiles.layout.router.polyline.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 com.yworks.yfiles.layout.router.polyline.PathSearchContext.pathSearchResult.
See also
| Method | Defined By | ||
|---|---|---|---|
PathSearch(init:Boolean = true)
Creates a new instance
| PathSearch | ||
addAdditionalEnterIntervalCalculator(enterIntervalCalculator:EnterIntervalCalculator):Boolean
Adds a new interval calculator to the list of registered interval calculators. | PathSearch | ||
addPathSearchExtension(extension:PathSearchExtension):Boolean
Adds the given extension to the list of path search extensions. | PathSearch | ||
clear():void
Resets all registered path search extensions and com.yworks.yfiles.util.DataProviders added by PathSearch. | PathSearch | ||
 | equals(o:Object):Boolean | YObject | |
findPaths(context:PathSearchContext):void
Finds paths for the edges in the given context and stores them in its PathSearchResult (com.yworks.yfiles.layout.router.polyline.PathSearchContext.pathSearchResult). | PathSearch | ||
getClass():Class [override] | PathSearch | ||
Returns the path for the given edge, if it has been finalized already. | PathSearch | ||
| hashCode():int | YObject | |
init(configuration:PathSearchConfiguration):void
Initializes the path search. | PathSearch | ||
[static]
Creates a new instance
| PathSearch | ||
removeAdditionalEnterIntervalCalculator(enterIntervalCalculator:EnterIntervalCalculator):Boolean
Removes the given interval calculator from the list of registered interval calculators. | PathSearch | ||
removePathSearchExtension(extension:PathSearchExtension):Boolean
Removes the given extension from the list of path search extensions. | PathSearch | ||
| Method | Defined By | ||
|---|---|---|---|
calculateCosts(currentEntrance:CellEntrance, enteredCell:PartitionCell, enterIntervals:Vector.<Object>, lastEdgeCellInfos:Vector.<Object>, context:PathSearchContext, costs:Vector.<Number>, maxAllowedCosts:Vector.<Number>):void
Returns the costs for getting from the current com.yworks.yfiles.layout.router.polyline.CellEntrance to the neighboring com.yworks.yfiles.layout.router.polyline.PartitionCell using different enter intervals. | PathSearch | ||
Returns estimated costs for the rest of the path when using the given com.yworks.yfiles.layout.router.polyline.CellEntrance for the next step in path search. | PathSearch | ||
decreasePenaltySettings(penaltySettings:PenaltySettings, decreaseFactor:Number, context:PathSearchContext):void
Decreases the given penalty settings for the current edge. | PathSearch | ||
finalizePath(path:Path):void
Informs all registered path search extensions about completing a path by calling their finalizePath(Path) (com.yworks.yfiles.layout.router.polyline.PathSearchExtension.finalizePath()) method. | PathSearch | ||
findPathsForCurrentEdge(context:PathSearchContext):void
Finds the path for the current edge in the given context. | PathSearch | ||
handleNeighbor(currentEntrance:CellEntrance, neighborCell:PartitionCell, context:PathSearchContext):void
Adds com.yworks.yfiles.layout.router.polyline.CellEntrance s for every interval through which the neighbor cell can be entered from the current entrance to the queue. | PathSearch | ||
initPathSearch():void
Initializes this object. | PathSearch | ||
| PathSearch | () | Constructor |
Hide Inherited Public Methods
Show Inherited Public Methodspublic function PathSearch(init:Boolean = true)Creates a new instance
Parametersinit:Boolean (default = true) |
| addAdditionalEnterIntervalCalculator | () | method |
public function addAdditionalEnterIntervalCalculator(enterIntervalCalculator:EnterIntervalCalculator):BooleanAdds a new interval calculator to the list of registered interval calculators.
Parameters
enterIntervalCalculator:EnterIntervalCalculator — The calculator to add.
|
Boolean — true, if the calculator could be added, false otherwise.
|
| addPathSearchExtension | () | method |
public function addPathSearchExtension(extension:PathSearchExtension):BooleanAdds the given extension to the list of path search extensions.
Parameters
extension:PathSearchExtension — The extension to add to this path search.
|
Boolean — true, if the extension has been added, false otherwise.
|
| calculateCosts | () | method |
protected function calculateCosts(currentEntrance:CellEntrance, enteredCell:PartitionCell, enterIntervals:Vector.<Object>, lastEdgeCellInfos:Vector.<Object>, context:PathSearchContext, costs:Vector.<Number>, maxAllowedCosts:Vector.<Number>):voidReturns the costs for getting from the current com.yworks.yfiles.layout.router.polyline.CellEntrance to the neighboring com.yworks.yfiles.layout.router.polyline.PartitionCell using different enter intervals. It is called by handleNeighbor() to determine the costs for all com.yworks.yfiles.layout.router.polyline.CellEntrance s that it will create and enqueue afterwards.
The costs for the given enter intervals are retrieved from all registered PathSearchExtension (com.yworks.yfiles.layout.router.polyline.PathSearchExtension) s. The calculation stops when it reaches the given maximum cost value.
Parameters
currentEntrance:CellEntrance — the current cell entrance.
| |
enteredCell:PartitionCell — the cell to enter.
| |
enterIntervals:Vector.<Object> — the different entering intervals of the entered cell.
| |
lastEdgeCellInfos:Vector.<Object> — information about how the last cell was crossed.
| |
context:PathSearchContext — context information.
| |
costs:Vector.<Number> — The array the calculated costs for entering the neighbor cell via the according enter intervals shall be written to.
| |
maxAllowedCosts:Vector.<Number> — the maximum costs an enter interval may induce. If this cost is exceeded, no further additional costs for this interval are calculated. Note that the entries in this array get modified during cost calculation
|
See also
| calculateHeuristicCosts | () | method |
protected function calculateHeuristicCosts(entrance:CellEntrance, context:PathSearchContext):NumberReturns estimated costs for the rest of the path when using the given com.yworks.yfiles.layout.router.polyline.CellEntrance for the next step in path search. It is called by handleNeighbor() 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 (com.yworks.yfiles.layout.router.polyline.PathSearchExtension) s.
Parameters
entrance:CellEntrance — The current entrance.
| |
context:PathSearchContext — Context information.
|
Number — the heuristic costs for the rest of the past if using the given entrance.
|
See also
| clear | () | method |
public function clear():void
Resets all registered path search extensions and com.yworks.yfiles.util.DataProviders added by PathSearch.
So, PathSearch is ready to calculate paths for a new layout.
See also
| decreasePenaltySettings | () | method |
protected function decreasePenaltySettings(penaltySettings:PenaltySettings, decreaseFactor:Number, context:PathSearchContext):voidDecreases the given penalty settings for the current edge.
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.
Parameters
penaltySettings:PenaltySettings — The penalty settings whose penalties shall be reduced.
| |
decreaseFactor:Number — 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:PathSearchContext — The context of the current path search.
|
| finalizePath | () | method |
protected function finalizePath(path:Path):voidInforms all registered path search extensions about completing a path by calling their finalizePath(Path) (com.yworks.yfiles.layout.router.polyline.PathSearchExtension.finalizePath()) method. That way, extensions can collect data about this path to use it later in path search.
Parameters
path:Path — The path to finalize.
|
See also
| findPaths | () | method |
public function findPaths(context:PathSearchContext):voidFinds paths for the edges in the given context and stores them in its PathSearchResult (com.yworks.yfiles.layout.router.polyline.PathSearchContext.pathSearchResult).
It initializes its extensions using com.yworks.yfiles.layout.router.polyline.PathSearchExtension.initializeEdges() and delegates the path search for each edge to findPathsForCurrentEdge().
The paths calculations for all edges are finalized by calling the extensions' com.yworks.yfiles.layout.router.polyline.PathSearchExtension.finalizeEdges() 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 com.yworks.yfiles.layout.router.polyline.PathSearchExtension.finalizePathSearchResult() callback.
Parameters
context:PathSearchContext — The context to use during the path search.
|
See also
| findPathsForCurrentEdge | () | method |
protected function findPathsForCurrentEdge(context:PathSearchContext):voidFinds the path for the current edge in the given context. This method:
Parameters
context:PathSearchContext |
See also
| getClass | () | method |
override public function getClass():ClassReturnsClass |
| getFinalizedPath | () | method |
public function getFinalizedPath(edge:Edge):PathReturns the path for the given edge, if it has been finalized already.
Parameters
edge:Edge — The edge to return the path for.
|
Path — The finalized path for the given edge or null if no path has been found and finalized.
|
| handleNeighbor | () | method |
protected function handleNeighbor(currentEntrance:CellEntrance, neighborCell:PartitionCell, context:PathSearchContext):voidAdds com.yworks.yfiles.layout.router.polyline.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.
Parameters
currentEntrance:CellEntrance — the current cell entrance
| |
neighborCell:PartitionCell — the neighbor cell that is handled.
| |
context:PathSearchContext — context information
|
See also
| init | () | method |
public function init(configuration:PathSearchConfiguration):voidInitializes the path search.
This method also calls com.yworks.yfiles.layout.router.polyline.PathSearchExtension.initialize() for all registered path search extensions.
Parameters
configuration:PathSearchConfiguration — The configuration, the path search shall use.
|
See also
| initPathSearch | () | method |
protected final function initPathSearch():void
Initializes this object. See the documentation of the corresponding factory method newPathSearch() for details.
See also
| newPathSearch | () | method |
| removeAdditionalEnterIntervalCalculator | () | method |
public function removeAdditionalEnterIntervalCalculator(enterIntervalCalculator:EnterIntervalCalculator):BooleanRemoves the given interval calculator from the list of registered interval calculators.
Parameters
enterIntervalCalculator:EnterIntervalCalculator — The calculator to remove.
|
Boolean — true, if an interval calculator was removed as a result of this call.
|
| removePathSearchExtension | () | method |
public function removePathSearchExtension(extension:PathSearchExtension):BooleanRemoves the given extension from the list of path search extensions.
Parameters
extension:PathSearchExtension — The extension to remove from the path search.
|
Boolean — true, if an extension was removed as a result of this call.
|