This class provides methods for finding paths within a graph that have certain properties.
Remarks
Note: Methods of this class work with instances of Graph. To work with various types of paths in an IGraph use one of the following classes instead:
Definitions
- A path of length
kfrom nodeuto nodevin a graph is a sequencev0, v1, v2, ... , vkof nodes such thatu = v0, v = vkand(vi-1, vi)inE, for eachi = 1, 2, .. , k. - A path is called simple if no node appears twice.
- A chain is a path of maximum length in which each internal node has degree
2. - The longest path problem is the problem of finding a simple path of maximum length in a given graph. The longest path problem is
NP-hard for undirected graphs, but can be solved in linear time for directed acyclic graphs.
Type Details
- yfiles module
- algorithms
- yfiles-umd modules
- All layout modules, view-layout-bridge
- Legacy UMD name
- yfiles.algorithms.Paths
Static Methods
Constructs a path of nodes from a given path of edges.
Remarks
path.size()+1, if the given path is not empty. Otherwise, the returned path will be empty. The i-th node in the returned path will be either source or target node of the i-th edge in the given path.Parameters
A map of options to pass to the method.
- path - EdgeList
- the given path of edges
Returns
- ↪YNodeList
- a path of nodes from the given path of edges
Returns all chains present in the given graph.
Remarks
Note: This method works with instances of Graph. To find all chains in an IGraph use Chains instead.
A chain is a path of maximum length in which each internal node has degree 2.
The internal nodes on directed chains all have in-degree 1 and out-degree 1.
Complexity
O(graph.N() + graph.E())
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- directed - boolean
trueif the chain should be considered as directed,falseotherwise
Returns
- ↪EdgeList[]
- an array of EdgeLists each of which contains the edges (at least two) that make up a chain
See Also
Finds all edges that belong to a directed path from a start node to an end node.
Remarks
Complexity
O(graph.N() + graph.E())
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- startNode - YNode
- the given start node
- endNode - YNode
- the given end node
- pathEdges - IEdgeMap
- the IEdgeMap that will be filled during the execution with a boolean value indicating whether or not an edge belongs to a path connecting the two given nodes
Domain Edge Values boolean trueif an edge edge belongs to a path connecting the two given nodes,falseotherwise
Returns all simple directed or undirected paths that connect a start node with an end node.
Remarks
Complexity
O(2^ (graph.N() + graph.E()))
Preconditions
- Input graph,
startnode andendnode must not benull.
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- startNode - YNode
- the given start node
- endNode - YNode
- the given end node
- directed - boolean
trueif the path should be considered as directed,falseotherwise
Returns
findAllPaths
(graph: Graph, startNode: YNode, endNode: YNode, directed: boolean, filter: function(EdgeList):boolean) : EdgeListA variant of findAllPaths which returns all simple directed or undirected paths between two given nodes and, additionally, allows to specify a filter for the paths to be returned.
Remarks
Complexity
O(2^ (graph.N() + graph.E()))
Preconditions
- Input graph,
startnode andendnode must not benull.
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- startNode - YNode
- the given start node
- endNode - YNode
- the given end node
- directed - boolean
trueif the path should be considered as directed,falseotherwise- filter - function(EdgeList):boolean
- a predicate that accepts or rejects a found EdgeList and adds it to the result
Signature Details
function(obj: EdgeList) : booleanRepresents the method that defines a set of criteria and determines whether the specified object meets those criteria.Parameters
- obj - EdgeList
- The object to compare against the criteria defined within the method represented by this delegate.
Returns
- boolean
trueif obj meets the criteria defined within the method represented by this delegate; otherwise,false.
Returns
A variant of findAllPaths, which returns all simple directed or undirected paths between two given nodes as a special cursor that calculates the next path in the sequence, only when needed.
Remarks
Note: This method works with instances of Graph. To find all paths between two nodes in an IGraph use Paths instead.
The returned cursor only supports the operation ok, current, size and next.
Complexity
O(2^ (graph.N() + graph.E()))
Preconditions
- Input graph,
startnode andendnode must not benull.
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- startNode - YNode
- the given start node
- endNode - YNode
- the given end node
- directed - boolean
trueif the path should be considered as directed,falseotherwise
Returns
Returns the longest directed path in a given acyclic weighted graph.
Remarks
Note: This method works with instances of Graph. To find the longest path in an IGraph use LongestPath with negative weights instead.
All edges of the graph have an integral length associated with them. The longest path is defined as one of all directed paths within the graph for which the edge lengths of all contained edges sum up to a maximum.
Preconditions
- The graph must be
. edgeLength.getInt(e) >= 0for all edgeseof the graph
Parameters
A map of options to pass to the method.
- graph - Graph
- a directed acyclic graph
- edgeLength - IDataProvider
- the IDataProvider that returns the non-negative integer length of each edge
Domain Edge Values number a non-negative value representing the length of each edge
Returns
findLongestPaths
(graph: Graph, startNode: YNode, dist: IEdgeMap, maxDist: INodeMap, predicate: IEdgeMap)Calculates the longest path from a given node to all other node in a given directed acyclic graph.
Remarks
Preconditions
- The graph must be
.
Parameters
A map of options to pass to the method.
- graph - Graph
- a directed acyclic graph
- startNode - YNode
- the node for which the distances are calculated
- dist - IEdgeMap
- the IEdgeMap that returns the distance (i.e. weight) of type double for each edge
Domain Edge Values number a value representing the distance (i.e. weight) of each edge of the graph - maxDist - INodeMap
- the INodeMap that will be filled during the execution and holds the maximum distance between the given node and all other nodes
Domain YNode Values number a value the maximum distance between the given node and all other nodes - predicate - IEdgeMap
- the IEdgeMap that returns a boolean value indicating whether or not an edge should be considered during the path search
Domain Edge Values boolean trueif an edge should be considered during the path search,falseotherwise
Returns an EdgeList containing the edges of an undirected simple path within the given graph.
Remarks
The edges are returned in the order that they appear in the found path.
A heuristic is used for finding a path that is long. It is not guaranteed, though, that the returned path is actually the longest path within the given graph, since that is a well known hard problem.
Complexity
O(graph.N() + graph.E())
Preconditions
- The graph must be
.
Parameters
A map of options to pass to the method.
- graph - Graph
- the given graph
Returns
Returns an EdgeList containing the edges of a path from the given start node to the given end node, if such a path exists.
Remarks
Note: This method works with instances of Graph. To find a path between two nodes in an IGraph use Paths instead.
The edges are returned in the order that they appear in the found path. If the returned path is empty, no path between the given nodes was found.
Complexity
O(graph.N() + graph.E())
Preconditions
startNode != endNode
Parameters
A map of options to pass to the method.
- graph - Graph
- the input graph
- startNode - YNode
- the first node of the path
- endNode - YNode
- the last node of the path
- directed - boolean
trueif the path should be directed,falseotherwise
Returns
findPath
(graph: Graph, topSort: YNodeList, startNode: YNode, endNode: YNode, predicate: IEdgeMap) : booleanReturns whether or not a directed path from a start node to another node in an acyclic graph exists.
Remarks
Preconditions
- The graph must be
.
Parameters
A map of options to pass to the method.
- graph - Graph
- an acyclic graph which contains the two nodes
- topSort - YNodeList
- a list of nodes sorted in topological order
- startNode - YNode
- endNode - YNode
- predicate - IEdgeMap
- the IEdgeMap that returns a boolean value indicating whether or not an edge should be considered during the path search
Domain Edge Values boolean trueif an edge should be considered during the path search,falseotherwise
Returns
- ↪boolean
trueif a directed path from a start node to another node exists,falseotherwise