A pathfinding algorithm that calculates the shortest (that means the cheapest) paths for a set of edges through a GraphPartition .

Namespace: yWorks.yFiles.Layout.Router.Polyline
Assembly: yWorks.yFilesSilverlight.Algorithms (in yWorks.yFilesSilverlight.Algorithms.dll) Version: 2.4.0.0

Syntax

C#
public class PathSearch
Visual Basic
Public Class PathSearch

Remarks

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 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 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 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 PathSearchResult .

Inheritance Hierarchy

System..::..Object
  yWorks.yFiles.Layout.Router.Polyline..::..PathSearch

See Also