C

AllPairsShortestPaths

Show Usages
Finds shortest paths between pairs of multiple sources and sinks.
Inheritance Hierarchy

Remarks

The shortest paths will be determined by invoking a single-source shortest path search for each node in sources. For n sources and m sinks the result thus may contain up to n ⋅ m distinct paths.

Other Shortest Path Algorithms

yFiles for HTML supports a number of other algorithms that compute shortest paths in a graph:

Other Path-Related Algorithms

yFiles for HTML also supports a number of other algorithms related to paths in a graph:

  • Paths – finds all paths between a set of source and a set of target nodes
  • Chains – finds all chains, that is, sequences of nodes that are each connected with just an edge without branches
  • Cycle – finds a cycle if one exists
  • LongestPath – finds the longest path in the graph

Examples

Highlighting the shortest path edges between multiple start and end nodes
// 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:
// calculate paths from startNode to all nodes in the graph
const result = algorithm.run(graph)
for (const sourceNode of sourceNodes) {
  for (const targetNode of targetNodes) {
    // and mark the edge path from start to the end node
    for (const edge of result.getPathBetween(sourceNode, targetNode)!
      .edges) {
      graph.setStyle(edge, highlightPathStyle)
    }
  }
}

See Also

Developer's Guide

Members

No filters for this type

Constructors

AllPairsShortestPaths

()

Parameters

Properties

costs

: ItemMapping<IEdge, number>
Gets or sets a mapping for the cost for 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 makes a shortest path the path with the fewest edges.

Negative costs are supported only for directed graphs and only if there is no cycle with negative costs. Negative costs are not supported for undirected graphs. run will throw an InvalidOperationError in these cases.

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()

directed

: boolean
Gets or sets a value indicating whether edge direction should be considered.
Default is true.
final

Property Value

true if the graph should be considered as directed, false otherwise.

sinks

: ItemCollection<INode>
Gets or sets a collection of sink (end, target) nodes.
The algorithm finds the shortest paths from all source nodes to all sink nodes. If either sources or sinks is empty, the result will contain no paths.
conversionfinal

Examples

// the sink nodes are provided as collection (the selected nodes)
algorithm = new AllPairsShortestPaths({
  sinks: graphComponent.selection.nodes,
})

// the sink nodes are the nodes in the graph for which the delegate returns true
// (nodes in the graph with "sink" as tag)
algorithm = new AllPairsShortestPaths({
  sinks: (node) => node.tag === 'sink',
})

See Also

Developer's Guide

sources

: ItemCollection<INode>
Gets or sets a collection of source (start) nodes.
The algorithm finds the shortest paths from all source nodes to all sink nodes. If either sources or sinks is empty, the result will contain no paths.
conversionfinal

Examples

// the source nodes are provided as collection (the selected nodes)
algorithm = new AllPairsShortestPaths({
  sources: graphComponent.selection.nodes,
})

// the source nodes are the nodes in the graph for which the delegate returns true
// (nodes in the graph with "source" as tag)
algorithm = new AllPairsShortestPaths({
  sources: (node) => node.tag === 'source',
})

See Also

Developer's Guide

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 AllPairsShortestPaths({
  // single source - single sink
  sources: sourceNodes,
  sinks: targetNodes,
  // Ignore edges without target arrow heads
  subgraphEdges: {
    excludes: (edge: IEdge): boolean =>
      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 path
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 AllPairsShortestPaths({
  // single source - single sink
  sources: sourceNodes,
  sinks: targetNodes,
  subgraphNodes: {
    // only consider elliptical nodes in the graph
    includes: (node: INode): boolean =>
      node.style instanceof ShapeNodeStyle &&
      node.style.shape === ShapeNodeShape.ELLIPSE,
    // but ignore the first node, regardless of its shape
    excludes: graph.nodes.first()!,
  },
})
// run the algorithm
const result = algorithm.run(graph)
// highlight the edge path
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): AllPairsShortestPathsResult
Finds all shortest paths between pairs of nodes from sources and sinks.
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

AllPairsShortestPathsResult
A AllPairsShortestPathsResult containing all shortest paths between nodes from sources and sinks.

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 shortest path edges between multiple start and end nodes
// 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:
// calculate paths from startNode to all nodes in the graph
const result = algorithm.run(graph)
for (const sourceNode of sourceNodes) {
  for (const targetNode of targetNodes) {
    // and mark the edge path from start to the end node
    for (const edge of result.getPathBetween(sourceNode, targetNode)!
      .edges) {
      graph.setStyle(edge, highlightPathStyle)
    }
  }
}