Finds the longest directed path in an acyclic graph.
Remarks
Other Path-Related Algorithms
@PRODUCT@ 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
Shortest Path Algorithms
@PRODUCT@ also supports a number of other algorithms that compute shortest paths in a graph:
- ShortestPath – finds the shortest path between two nodes
- SingleSourceShortestPaths – finds shortest paths from a single source node to several other nodes
- AllPairsShortestPaths – finds all shortest paths between pairs of several source and sink nodes
Examples
// prepare the longest path detection algorithm
const algorithm = new LongestPath()
// run the algorithm
const result = algorithm.run(graph)
// highlight the cycle
for (const edge of result.edges) {
graph.setStyle(edge, highlightLongestPathStyle)
}Type Details
- yFiles module
- view-layout-bridge
See Also
Constructors
Parameters
A map of options to pass to the method.
- costs - ItemMapping<IEdge,number>
- A mapping for edge costs. This option either sets the value directly or recursively sets properties to the instance of the costs 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 edge costs.
Remarks
The longest path of a graph is a path for which the sum of costs associated with the path edges is maximal.
If no costs are given, all edges have a uniform cost of 1. Path length is then solely determined by the number of edges.
Costs must not be negative.
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
// prepare the longest path detection algorithm
const algorithm = new LongestPath({
// 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 cycle
for (const edge of result.edges) {
graph.setStyle(edge, highlightLongestPathStyle)
}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
// prepare the longest path detection algorithm
const algorithm = new LongestPath({
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 cycle
for (const edge of result.edges) {
graph.setStyle(edge, highlightLongestPathStyle)
}Methods
Finds the longest directed path in an acyclic graph.
Preconditions
- The graph must be
.
Parameters
A map of options to pass to the method.
- graph - IGraph
- The input graph to run the algorithm on.
Returns
- ↪LongestPathResult
- A LongestPathResult containing the longest directed path in the graph.
Throws
- Exception({ name: 'InvalidOperationError' })
- If the algorithm can't create a valid result due to an invalid graph structure or wrongly configured properties.