C

ShortestPathResult

Show Usages
Represents the shortest path between two nodes in a graph as computed by ShortestPath.
Inheritance Hierarchy

Remarks

This class cannot be instantiated

Members

No filters for this type

Properties

distance

: number
readonly
Gets the distance of the path.

This is the sum of edge costs along the path. If there are no edge costs, the distance is the number of edges in the path.

If there is no path between the two nodes, this is equal to Number.POSITIVE_INFINITY.

readonlyfinal

Examples

algorithm.source = startNode
algorithm.sink = endNode
const result = algorithm.run(graph)
console.log(result.distance) // the distance between startNode and endNode

edges

: ResultItemCollection<IEdge>
readonly
Gets a collection of edges along the path.
If there is no path between the two nodes (or source and sink are identical), this is empty.
readonlyfinal

nodes

: ResultItemCollection<INode>
readonly
Gets a collection of nodes along the path, starting with the source node and ending with the sink node.
If there is no path between the two nodes, this collection is empty.
readonlyfinal

path

: Path
readonly
Gets the shortest path found between source and sink if one exists.
If there is no path between the two nodes, this is null.
readonlyfinal

predecessors

: ResultItemMapping<INode, IEdge>
readonly
Gets a mapping from each node to the last incoming edge of the shortest path to this node.

This is a common representation of a shortest path tree which exploits the fact that any shortest path in a graph has sub-paths that themselves are also shortest paths. A shortest path to a given node can be reconstructed backwards by querying this mapping for that node, following the returned edge to its source node, and continuing to query the mapping until the source node of the shortest-path search is reached.

This mapping returns null for nodes that are not part of the found shortest path.

readonlyfinal

Examples

Starting the target or sink node one can walk along the edges to the start node.
// configure the shortest path algorithm
const algorithm = new ShortestPath({
  // single source - single sink
  source: startNode,
  sink: endNode,
  // add edge cost mapping which returns the actual length of the edge
  costs: (edge) =>
    edge.style.renderer
      .getPathGeometry(edge, edge.style)
      .getPath()!
      .getLength(),
})

// run the algorithm
const result = algorithm.run(graph)

// highlight the edge path
const predResultsMap = result.predecessors
let walker: INode = endNode
let edge: IEdge | null = predResultsMap.get(walker)
while (edge !== null) {
  graph.setStyle(edge, highlightPathStyle)
  walker = edge.opposite(walker) as INode
  edge = predResultsMap.get(walker)
}