C

KShortestPaths

Show Usages
Computes the k shortest paths connecting a pair of nodes in a directed graph with non-negative edge costs.
Inheritance Hierarchy

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.

The results provide a collection of the found Paths.

Examples

Highlighting the k shortest path edges between a start and an end node
// 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)
  }
}

Members

No filters for this type

Constructors

KShortestPaths

()

Parameters

Properties

costs

: ItemMapping<IEdge, number>
Gets or sets a mapping for the cost of traversing an edge.

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.

conversionfinal

Examples

Mapping a value to some edges
// 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
Using a delegate to determine the cost
// returns the length of the actual edge path as cost
algorithm.costs = (edge) =>
  edge.style.renderer
    .getPathGeometry(edge, edge.style)
    .getPath()!
    .getLength()

k

: number
Gets or sets a non-negative integer specifying the number of shortest paths to find.

If set to 0, the method returns an KShortestPathsResult with an empty paths enumerable.

Default is 1.

final

Property Value

A non-negative integer specifying the number of shortest paths to find.

simplePaths

: boolean
Gets or sets a boolean value indicating whether the returned paths should be simple, meaning no node is repeated within any path.
Setting this to false may decrease the runtime for graphs with cycles. Default is true.
final

Property Value

true the returned paths should be simple, meaning no node is repeated within any path, false otherwise.

sink

: ItemCollection<INode>
Gets or sets the sink (end, target) node of the path.
If multiple nodes are provided, the first valid sink node is used.
conversionfinal

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'

source

: ItemCollection<INode>
Gets or sets the source (start) node of the path.
If multiple nodes are provided, the first valid source node is used.
conversionfinal

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'

subgraphEdges

: ItemCollection<IEdge>
Gets or sets the collection of edges which define a subset of the graph for the algorithms to work on.

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.

The edges provided here must be part of the graph which is passed to the run method.
conversionfinal

Examples

Calculating shortest paths on a subset of the graph
// 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)
  }
}

subgraphNodes

: ItemCollection<INode>
Gets or sets the collection of nodes which define a subset of the graph for the algorithms to work on.

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.

The nodes provided here must be part of the graph which is passed to the run method.
conversionfinal

Examples

Calculating shortest paths on a subset of the graph
// 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)
  }
}
Considering only selected nodes
algorithm.subgraphNodes = graphComponent.selection.nodes
Ignoring all group nodes
algorithm.subgraphNodes.excludes = (n) => graph.isGroupNode(n)
Considering selected nodes but ignoring group nodes
algorithm.subgraphNodes = graphComponent.selection.nodes
algorithm.subgraphNodes.excludes = (n) => graph.isGroupNode(n)

Methods

run

(graph: IGraph): KShortestPathsResult
Finds the k shortest paths between pairs of the source and the sink nodes.
The result obtained from this algorithm is a snapshot which is no longer valid once the graph has changed, e.g. by adding or removing nodes or edges.
final

Parameters

graph: IGraph
The graph on which the shortest paths are computed.

Return Value

KShortestPathsResult
A KShortestPathsResult containing all shortest paths between source and sink.

Throws

Exception ({ name: 'InvalidOperationError' })
If the algorithm can't create a valid result due to an invalid graph structure or wrongly configured properties.

Examples

Highlighting the k shortest path edges between a start and an end node
// 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)
  }
}