| Package | com.yworks.yfiles.algo |
| Class | public class Paths |
| Inheritance | Paths  YObject Object |
| Method | Defined By | ||
|---|---|---|---|
Paths(init:Boolean = true) | Paths | ||
[static]
Constructs a node path from a given edge path. | Paths | ||
 | equals(o:Object):Boolean | YObject | |
findAllChains(graph:Graph, directed:Boolean):Vector.<Object> [static]
Returns all chains present in the given graph. | Paths | ||
[static]
Marks all edges that belong to a directed path from start to end node. | Paths | ||
[static]
Returns all simple directed or undirected paths that connect start with end node. | Paths | ||
[static]
A variant of findAllPaths2() that returns its result not as a list but as a special cursor that calculates the next path in the sequence only when needed. | Paths | ||
findAllPathsFiltered(graph:Graph, startNode:Node, endNode:Node, directed:Boolean, filter:Filter):Vector.<Object> [static]
A variant of findAllPaths2() that additionally allows to specify a filter for the paths to be returned. | Paths | ||
[static]
Returns the longest directed path within the given acyclic graph. | Paths | ||
[static]
Calculates the longest path from one vertex to all other vertices in a given acyclic graph
Precondition GraphCheckers.isAcyclic(g)
| Paths | ||
[static]
Returns the longest directed path within a given acyclic weighted graph. | Paths | ||
[static]
Returns an edge list that contains the edges of a undirected simple path within the given graph. | Paths | ||
[static]
Returns an edge list that contains the edges of a path from the given start node to the given end node, if such a path exists. | Paths | ||
findPathWithSorting(g:Graph, topSort:NodeList, startNode:Node, endNode:Node, predicate:EdgeMap):Boolean [static]
Returns whether or not there is a directed path from one node to another node in an acyclic graph
Precondition GraphChecker.isAcyclic(g)
| Paths | ||
getClass():Class [override] | Paths | ||
| hashCode():int | YObject | |
[static] | Paths | ||
| Method | Defined By | ||
|---|---|---|---|
initPaths():void | Paths | ||
| Paths | () | Constructor |
Hide Inherited Public Methods
Show Inherited Public Methodspublic function Paths(init:Boolean = true)init:Boolean (default = true) |
| constructNodePath | () | method |
public static function constructNodePath(path:EdgeList):NodeList
Constructs a node path from a given edge path.
The returned node path has length 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
path:EdgeList |
NodeList |
| findAllChains | () | method |
public static function findAllChains(graph:Graph, directed:Boolean):Vector.<Object>Returns all chains present in the given graph. A chain in a graph is a paths of maximal length, where each internal node on the path has degree 2. The internal nodes on directed chains all have in-degree 1 and out-degree 1.
Complexity O(g.N()+g.E())
Parameters
graph:Graph — the input graph
| |
directed:Boolean |
Vector.<Object> — an array of EdgeList objects, each of which has at least length 2. An edge list contains the edges that make up a chain. Method constructNodePath() can be used to convert an edge path to a node path.
|
See also
| findAllPaths | () | method |
public static function findAllPaths(g:Graph, start:Node, end:Node, pathEdges:EdgeMap):void
Marks all edges that belong to a directed path from start to end node.
Complexity O(g.N()+g.E())
Parameters
g:Graph — the input graph
| |
start:Node — the start node
| |
end:Node — the end node
| |
pathEdges:EdgeMap — the result. For each edge a boolean value will indicate whether or not it belongs to a path connecting the two nodes.
|
| findAllPaths2 | () | method |
public static function findAllPaths2(graph:Graph, startNode:Node, endNode:Node, directed:Boolean):Vector.<Object>
Returns all simple directed or undirected paths that connect start with end node.
One should note that the number of different paths connecting two nodes can be exponential in number of nodes and edges of a given graph. This said, even for small graphs the runtime and memory consumption of the algorithm can be excessive. To significantly lower memory consumption use findAllPathsCursor() instead.
Complexity O(2^(g.N()+g.E()))
Precondition graph, startNode, and endNode may not be null.
Parameters
graph:Graph — the input graph
| |
startNode:Node — the start node
| |
endNode:Node — the end node
| |
directed:Boolean — whether or not to consider the edges in the graph to be directed or not.
|
Vector.<Object> — an array of EdgeLists each representing a path between start and end node.
|
See also
| findAllPathsCursor | () | method |
public static function findAllPathsCursor(graph:Graph, startNode:Node, endNode:Node, directed:Boolean):YCursorA variant of findAllPaths2() that returns its result not as a list but as a special cursor that calculates the next path in the sequence only when needed. The returned cursor only supports the operation com.yworks.yfiles.base.YCursor.ok(), com.yworks.yfiles.base.YCursor.current(), com.yworks.yfiles.base.YCursor.size() and com.yworks.yfiles.base.YCursor.next() .
Parameters
graph:Graph | |
startNode:Node | |
endNode:Node | |
directed:Boolean |
YCursor |
See also
| findAllPathsFiltered | () | method |
public static function findAllPathsFiltered(graph:Graph, startNode:Node, endNode:Node, directed:Boolean, filter:Filter):Vector.<Object>A variant of findAllPaths2() that additionally allows to specify a filter for the paths to be returned.
Parameters
graph:Graph | |
startNode:Node | |
endNode:Node | |
directed:Boolean | |
filter:Filter — a filter that tests for each found EdgeList if it should make it to the result list.
|
Vector.<Object> |
See also
| findLongestPath | () | method |
public static function findLongestPath(g:Graph):EdgeListReturns the longest directed path within the given acyclic graph.
Precondition GraphChecker.isAcyclic(g)
Parameters
g:Graph — a directed acyclic graph
|
EdgeList — an edge list representing the longest directed path within the given graph
|
| findLongestPaths | () | method |
public static function findLongestPaths(g:Graph, startNode:Node, dist:EdgeMap, maxDist:NodeMap, predicate:EdgeMap):voidCalculates the longest path from one vertex to all other vertices in a given acyclic graph
Precondition GraphCheckers.isAcyclic(g)
Parameters
g:Graph — a directed acyclic graph.
| |
startNode:Node — the node, for which the distances are calculated.
| |
dist:EdgeMap — the distances for the edges.
| |
maxDist:NodeMap — here the result will be stored.
| |
predicate:EdgeMap — only edges for which predicate is true are considered.
|
| findLongestPathWeighted | () | method |
public static function findLongestPathWeighted(g:Graph, edgeLength:DataProvider):EdgeListReturns the longest directed path within a given acyclic weighted graph. 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.
Precondition GraphChecker.isAcyclic(g)
Precondition edgeLength.getInt(e) > 0 for all edges e of g
Parameters
g:Graph — a directed acyclic graph
| |
edgeLength:DataProvider — a data provider that must provide the length of each edge as an int value
|
EdgeList — an edge list representing the longest directed path within the given graph
|
| findLongPath | () | method |
public static function findLongPath(graph:Graph):EdgeListReturns an edge list that contains the edges of a undirected simple path within the given graph. The edges are returned in the order they appear in the found path.
A heuristic is used to find 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 to solve problem.Complexity O(graph.N() + graph.E())
Precondition GraphChecker.isSimple(graph);
Parameters
graph:Graph |
EdgeList |
| findPath | () | method |
public static function findPath(graph:Graph, startNode:Node, endNode:Node, directed:Boolean):EdgeListReturns an edge list that contains the edges of a path from the given start node to the given end node, if such a path exists. The edges are returned in the order they appear in the found path.
If the returned path is empty then no path between the given nodes was found.Precondition startNode != endNode
Complexity O(graph.N() + graph.E())
Parameters
graph:Graph — the input graph
| |
startNode:Node — the first node of the path
| |
endNode:Node — the last node of the path
| |
directed:Boolean — whether to search for a directed or undirected path
|
EdgeList |
| findPathWithSorting | () | method |
public static function findPathWithSorting(g:Graph, topSort:NodeList, startNode:Node, endNode:Node, predicate:EdgeMap):BooleanReturns whether or not there is a directed path from one node to another node in an acyclic graph
Precondition GraphChecker.isAcyclic(g)
Parameters
g:Graph — the acyclic graph which contains the two nodes.
| |
topSort:NodeList — a topological sorting of the nodes of the graph.
| |
startNode:Node | |
endNode:Node | |
predicate:EdgeMap — only edges for which predicate is true are considered.
|
Boolean |
| getClass | () | method |
override public function getClass():ClassReturnsClass |
| initPaths | () | method |
protected final function initPaths():void| newPaths | () | method |