Remarks
Other Path-Related Algorithms
yFiles for HTML 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
yFiles for HTML 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)
}See Also
Developer's Guide
API
- longestPath
Members
Constructors
Properties
Gets or sets a mapping for edge costs.
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.
If nothing is set, all edges of the graph will be processed.
If only the ItemCollection<TItem>.excludes are set, all edges in the graph except those provided in the ItemCollection<TItem>.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.
If nothing is set, all nodes of the graph will be processed.
If only the ItemCollection<TItem>.excludes are set, all nodes in the graph except those provided in the ItemCollection<TItem>.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.
Parameters
- graph: IGraph
- The input graph to run the algorithm on.
Return Value
- 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.