C

AllPairsShortestPathsResult

Show Usages
Represents all shortest paths between pairs of source and sink nodes as computed by AllPairsShortestPaths.
Inheritance Hierarchy

Remarks

This class cannot be instantiated

Members

No filters for this type

Properties

paths

: ResultItemCollection<Path>
readonly
Gets a collection of shortest paths between the source nodes and sink nodes.
This collection contains every existing shortest path between pairs of nodes from sources and sinks. Thus for n sources and m sinks there may be up to n ⋅ m distinct paths. However, there may be fewer paths than that if some sink nodes are not reachable from some source nodes.
readonlyfinal

Methods

getDistanceBetween

(source: INode, sink: INode): number
Gets the length of the shortest path between source and sink.
If source was not in the collection of source nodes, the result is Number.POSITIVE_INFINITY. This is also the result if there is no path between source and sink.
final

Parameters

source: INode
The path's source node.
sink: INode
The path's sink node.

Return Value

number
The distance between a given source node and a given sink node, or Number.POSITIVE_INFINITY if there is no path between them or source was not part of the sources.

getPathBetween

(source: INode, sink: INode): Path
Gets the shortest path between a given source and sink node if one exists.
final

Parameters

source: INode
The path's source node.
sink: INode
The path's sink node.

Return Value

Path
The shortest path between a given source and sink node or null if there is no path between them or either source or sink was not part of the sources or sinks.

getPredecessorsForSource

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

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 tree is rooted in the source node and since this result represents many paths between pairs of source and target nodes, this mapping can be retrieved for each source node.

final

Parameters

source: INode
The source node to get the predecessor mapping for.

Return Value

ResultItemMapping<INode, IEdge>
A mapping from which shortest paths between source and other nodes can be reconstructed or null if source was not part of sources.

Examples

Starting with a target (sink) node one can walk along the edges to the source (start) node.
// configure the shortest path algorithm
const algorithm = new AllPairsShortestPaths({
  // multiple source and sink nodes
  sources: sourceNodes,
  sinks: targetNodes,
  // 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)

for (const sourceNode of sourceNodes) {
  // highlight the edge path
  const predResultsMap = result.getPredecessorsForSource(sourceNode)!
  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)
  }
}