Represents all shortest paths between pairs of source and sink nodes as computed by AllPairsShortestPaths.
Type Details
- yfiles module
- view-layout-bridge
- yfiles-umd modules
- view-layout-bridge
- Legacy UMD name
- yfiles.analysis.AllPairsShortestPathsResult
Properties
Gets a collection of shortest paths between the source nodes and sink nodes.
Methods
Gets the length of the shortest path between source and sink.
Remarks
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.Parameters
A map of options to pass to the method.
Returns
- ↪number
- The distance between a given
sourcenode and a givensinknode or Number.POSITIVE_INFINITY if there is no path between them orsourcewas not part of the sources.
Gets the shortest path between a given source and sink node if one exists.
Gets a mapping from each node to the last incoming edge of the shortest path to source.
Remarks
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.
Parameters
A map of options to pass to the method.
- source - INode
- The source node to get the predecessor mapping for.
Returns
- ↪ResultItemMapping<INode,IEdge>
- A mapping from which shortest paths between
sourceand other nodes can be reconstructed onullifsourcewas not part of sources.
Examples
// 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 = endNode
let edge = predResultsMap.get(walker)
while (edge !== null) {
graph.setStyle(edge, highlightPathStyle)
walker = edge.opposite(walker)
edge = predResultsMap.get(walker)
}
}// 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)
}
}