Computes the k shortest paths connecting a pair of nodes in a directed graph with non-negative edge costs.
Remarks
This method computes the k shortest paths from the source node to the sink node in a directed graph. The paths are ranked by their total cost, with the first path being the shortest.
The graph must have non-negative edge costs, as provided by the costs mapper.
Examples
// configure the shortest path algorithm
const algorithm = new KShortestPaths()
algorithm.source = startNode
algorithm.sink = endNode
// add edge cost mapping which returns the actual length of the edge
algorithm.costs = (edge) =>
edge.style.renderer
.getPathGeometry(edge, edge.style)
.getPath()!
.getLength()
// run the algorithm
const result = algorithm.run(graph)
// highlight the edge paths
for (const path of result.paths) {
for (const edge of path.edges) {
graph.setStyle(edge, highlightPathStyle)
}
}Type Details
- yFiles module
- view-layout-bridge
Constructors
Parameters
A map of options to pass to the method.
- source - ItemCollection<INode>
- The source (start) node of the path. This option either sets the value directly or recursively sets properties to the instance of the source property on the created object.
- sink - ItemCollection<INode>
- The sink (end, target) node of the path. This option either sets the value directly or recursively sets properties to the instance of the sink property on the created object.
- costs - ItemMapping<IEdge,number>
- A mapping for the cost of traversing an edge. This option either sets the value directly or recursively sets properties to the instance of the costs property on the created object.
- simplePaths - boolean
- A boolean value indicating whether the returned paths should be simple, meaning no node is repeated within any path. This option sets the simplePaths property on the created object.
- k - number
- A non-negative integer specifying the number of shortest paths to find. This option sets the k property on the created object.
- subgraphNodes - ItemCollection<INode>
- The collection of nodes which define a subset of the graph for the algorithms to work on. This option either sets the value directly or recursively sets properties to the instance of the subgraphNodes property on the created object.
- subgraphEdges - ItemCollection<IEdge>
- The collection of edges which define a subset of the graph for the algorithms to work on. This option either sets the value directly or recursively sets properties to the instance of the subgraphEdges property on the created object.
Properties
Gets or sets a mapping for the cost of traversing an edge.
Remarks
For the shortest path algorithm, this is a measure of the edge's length, so more expensive (higher cost) edges are considered longer and avoided if there's a shorter (cheaper) path elsewhere in the graph.
When no costs are provided, uniform costs of 1 are assumed for all edges. This considers the paths with the fewest edges as shortest paths.
Examples
// setting the cost for traversing e1 and e2 to 1.0
algorithm.costs.mapper.set(e1, 1.0)
algorithm.costs.mapper.set(e2, 1.0)
// all other edges are not set and return 0// returns the length of the actual edge path as cost
algorithm.costs = (edge) =>
edge.style.renderer
.getPathGeometry(edge, edge.style)
.getPath()!
.getLength()Gets or sets a non-negative integer specifying the number of shortest paths to find.
Remarks
If set to 0, the method returns an KShortestPathsResult with an empty paths enumerable.
Default is 1.
Property Value
Gets or sets a boolean value indicating whether the returned paths should be simple, meaning no node is repeated within any path.
Remarks
false may decrease the runtime for graphs with cycles. Default is true.Property Value
true the returned paths should be simple, meaning no node is repeated within any path, false otherwise.Gets or sets the sink (end, target) node of the path.
Remarks
Examples
// the item is the explicitly set Item (the end node)
algorithm = new KShortestPaths()
algorithm.sink = endNode
// the item is the first item in the Source (the first selected node)
algorithm = new KShortestPaths()
algorithm.sink = graphComponent.selection.nodes
// the item is the first in the graph for which the predicate returns true
// (the first node in the graph with "sink" as tag)
algorithm = new KShortestPaths()
algorithm.sink = (node) => node.tag === 'Sink'Gets or sets the source (start) node of the path.
Remarks
Examples
// the item is the explicitly set Item (the start node)
algorithm = new KShortestPaths()
algorithm.source = startNode
algorithm = new KShortestPaths()
algorithm.source = graphComponent.selection.nodes
algorithm = new KShortestPaths()
algorithm.source = (node) => node.tag === 'Source'Gets or sets the collection of edges which define a subset of the graph for the algorithms to work on.
Remarks
If nothing is set, all edges of the graph will be processed.
If only the excludes are set, all edges in the graph except those provided in the excludes are processed.
Note that edges which start or end at nodes which are not in the subgraphNodes are automatically not considered by the algorithm.
ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.
Examples
// configure the shortest path algorithm
const algorithm = new KShortestPaths()
// set source and sink
algorithm.source = startNode
algorithm.sink = endNode
// Ignore edges without target arrow heads
algorithm.subgraphEdges.excludes = (edge) =>
edge.style instanceof PolylineEdgeStyle &&
edge.style.targetArrow instanceof Arrow &&
edge.style.targetArrow.type === ArrowType.NONE
// run the algorithm
const result = algorithm.run(graph)
// highlight the edge paths
for (const path of result.paths) {
for (const edge of path.edges) {
graph.setStyle(edge, highlightPathStyle)
}
}Gets or sets the collection of nodes which define a subset of the graph for the algorithms to work on.
Remarks
If nothing is set, all nodes of the graph will be processed.
If only the excludes are set, all nodes in the graph except those provided in the excludes are processed.
ItemCollection<T> instances may be shared among algorithm instances and will be (re-)evaluated upon (re-)execution of the algorithm.
Examples
// configure the shortest path algorithm
const algorithm = new KShortestPaths()
algorithm.source = startNode
algorithm.sink = endNode
// only consider elliptical nodes in the graph
algorithm.subgraphNodes = {
predicate: (node) =>
(node.style as ShapeNodeStyle).shape === ShapeNodeShape.ELLIPSE,
excludes: {
items: [graph.nodes.first()],
},
}
// run the algorithm
const result = algorithm.run(graph)
// highlight the edge paths
for (const path of result.paths) {
for (const edge of path.edges) {
graph.setStyle(edge, highlightPathStyle)
}
}algorithm.subgraphNodes = graphComponent.selection.nodesalgorithm.subgraphNodes.excludes = (n) => graph.isGroupNode(n)algorithm.subgraphNodes = graphComponent.selection.nodes
algorithm.subgraphNodes.excludes = (n) => graph.isGroupNode(n)Methods
Finds the k shortest paths between pairs of the source and the sink nodes.
Parameters
A map of options to pass to the method.
- graph - IGraph
- The graph on which the shortest paths are computed.
Returns
Throws
- Exception({ name: 'InvalidOperationError' })
- If the algorithm can't create a valid result due to an invalid graph structure or wrongly configured properties.
Examples
// configure the shortest path algorithm
const algorithm = new KShortestPaths()
algorithm.source = startNode
algorithm.sink = endNode
// add edge cost mapping which returns the actual length of the edge
algorithm.costs = (edge) =>
edge.style.renderer
.getPathGeometry(edge, edge.style)
.getPath()!
.getLength()
// run the algorithm
const result = algorithm.run(graph)
// highlight the edge paths
for (const path of result.paths) {
for (const edge of path.edges) {
graph.setStyle(edge, highlightPathStyle)
}
}