Represents all shortest paths between a single source node and multiple sink nodes nodes in a graph as computed by SingleSourceShortestPaths.
Type Details
- yfiles module
- view-layout-bridge
- yfiles-umd modules
- view-layout-bridge
- Legacy UMD name
- yfiles.analysis.SingleSourceShortestPathsResult
Properties
Gets a mapping from each node to its shortest distance from the source node.
Remarks
Since every shortest path consists of other shortest paths, this mapping not only contains the shortest distances to the sink nodes but also all nodes on the paths to the sinks.
The distance to a node is Number.POSITIVE_INFINITY if there is no path from source to that node.
Examples
const algorithm = new SingleSourceShortestPaths({
source: startNode,
sinks: targetNodes
})
const result = algorithm.run(graph)
for (const node of targetNodes) {
graph.setLabelText(
node.labels.get(0),
`Distance: ${result.distances.get(node)}`
)
}Gets a collection of shortest paths between the source node and sink nodes.
Remarks
This collection contains every existing shortest path between source and the sink nodes. This means that there may well be fewer paths than sinks if some of them are not reachable from the source node.
While the underlying algorithm always computes shortest paths to all nodes in the graph, this collection only contains paths to the initially configured sink nodes.
Gets a mapping from each node to the last incoming edge of the shortest path to this node.
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 mapping returns null for nodes that have no path from source.
Examples
// configure the shortest path algorithm
const algorithm = new SingleSourceShortestPaths({
// single source
source: startNode,
// 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 = 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 SingleSourceShortestPaths({
// single source
source: startNode,
// 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)
}See Also
Methods
Gets the shortest path from the configured source node to the given sink node if one exists.
Remarks
sink was not part of the sinks collection or no path between source and sink exists, the return value is null.Parameters
A map of options to pass to the method.
- sink - INode
- The sink (target, end) node of the path to get.
Returns
- ↪Path
- The shortest path between the source and the sink node.