
Search this API  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object y.algo.Paths
public class Paths
This class provides methods for finding paths within a graph that have certain properties.
k
from node u
to node v
in a graph is a sequence
v0, v1, v2, ... , vk
of nodes such that u = v0, v = vk
and
(vi1, vi)
in E
, for each i = 1, 2, .. , k
.2
.NP
hard for undirected graphs, but can be solved in linear time for
directed acyclic graphs.
Method Summary  

static NodeList 
constructNodePath(EdgeList path)
Constructs a path of nodes from a given path of edges . 
static EdgeList[] 
findAllChains(Graph graph,
boolean directed)
Returns all chains present in the given graph. 
static EdgeList[] 
findAllPaths(Graph graph,
Node startNode,
Node endNode,
boolean directed)
Returns all simple directed or undirected paths that connect a start node with an end
node. 
static EdgeList[] 
findAllPaths(Graph graph,
Node startNode,
Node endNode,
boolean directed,
Filter filter)
A variant of findAllPaths(Graph, Node, Node, boolean) 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. 
static void 
findAllPaths(Graph graph,
Node startNode,
Node endNode,
EdgeMap pathEdges)
Finds all edges that belong to a directed path from a start node to an end node. 
static YCursor 
findAllPathsCursor(Graph graph,
Node startNode,
Node endNode,
boolean directed)
A variant of findAllPaths(Graph, Node, Node, boolean) ,
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. 
static EdgeList 
findLongestPath(Graph graph)
Returns the longest directed path in the given acyclic graph. 
static EdgeList 
findLongestPath(Graph graph,
DataProvider edgeLength)
Returns the longest directed path in a given acyclic weighted graph. 
static void 
findLongestPaths(Graph graph,
Node startNode,
EdgeMap dist,
NodeMap maxDist,
EdgeMap predicate)
Calculates the longest path from a given node to all other node in a given directed acyclic graph. 
static EdgeList 
findLongPath(Graph graph)
Returns an EdgeList containing the edges of an undirected simple path within the given graph. 
static boolean 
findPath(Graph graph,
NodeList topSort,
Node startNode,
Node endNode,
EdgeMap predicate)
Returns whether or not a directed path from a start node to another node in an acyclic graph exists. 
static EdgeList 
findPath(Graph graph,
Node startNode,
Node endNode,
boolean directed)
Returns an EdgeList containing the edges of a path from the given start node to the given end node,
if such a path exists. 
Methods inherited from class java.lang.Object 

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait 
Method Detail 

public static EdgeList findPath(Graph graph, Node startNode, Node endNode, boolean directed)
EdgeList
containing 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 that they appear in the found path. If the returned path is empty, no path between the given nodes was found.
startNode != endNode
O(graph.N() + graph.E())
graph
 the input graphstartNode
 the first node of the pathendNode
 the last node of the pathdirected
 true
if the path should be directed, false
otherwise
EdgeList
containing the path edges between the start node and the end nodepublic static EdgeList findLongPath(Graph graph)
EdgeList
containing the edges of an undirected simple path within the given graph.
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.
simple
.O(graph.N() + graph.E())
graph
 the given graph
EdgeList
containing the edges of an undirected simple pathpublic static void findLongestPaths(Graph graph, Node startNode, EdgeMap dist, NodeMap maxDist, EdgeMap predicate)
acyclic
.graph
 a directed acyclic graphstartNode
 the node for which the distances are calculateddist
 the EdgeMap
that returns the distance (i.e. weight) of type double for each edgemaxDist
 the NodeMap
that will be filled during the execution and holds the maximum distance between
the given node and all other nodespredicate
 the EdgeMap
that returns a boolean value indicating whether or not an edge should be
considered during the path searchpublic static EdgeList findLongestPath(Graph graph)
acyclic
.graph
 a directed acyclic graph
EdgeList
containing the edges of the longest directed pathpublic static EdgeList findLongestPath(Graph graph, DataProvider edgeLength)
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.
acyclic
.edgeLength.getInt(e) >= 0
for all edges e
of the graphgraph
 a directed acyclic graphedgeLength
 the DataProvider
that returns the nonnegative integer length of each edge
EdgeList
containing the edges of the longest directed pathpublic static NodeList constructNodePath(EdgeList path)
path of nodes
from a given path of edges
.
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.
path
 the given path of edges
path of nodes
from the given path of edges
public static boolean findPath(Graph graph, NodeList topSort, Node startNode, Node endNode, EdgeMap predicate)
acyclic
.graph
 an acyclic graph which contains the two nodestopSort
 a list
of nodes sorted in topological orderpredicate
 the EdgeMap
that returns a boolean value indicating whether or not an edge should be
considered during the path search
true
if a directed path from a start node to another node exists, false
otherwisepublic static final void findAllPaths(Graph graph, Node startNode, Node endNode, EdgeMap pathEdges)
start
node to an end
node.
O(graph.N() + graph.E())
graph
 the input graphstartNode
 the given start nodeendNode
 the given end nodepathEdges
 the EdgeMap
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 nodespublic static EdgeList[] findAllChains(Graph graph, boolean directed)
A chain is a path of maximum length in which each internal node has degree 2
.
The internal nodes on directed chains all have indegree 1
and outdegree 1
.
constructNodePath(EdgeList)
can be used for converting an edge path to a node path.O(graph.N() + graph.E())
graph
 the input graphdirected
 true
if the chain should be considered as directed, false
otherwise
EdgeList
s each of which contains the edges (at least two) that make up a chainconstructNodePath(EdgeList)
public static EdgeList[] findAllPaths(Graph graph, Node startNode, Node endNode, boolean directed)
start
node with an end
node.
findAllPathsCursor(Graph, Node, Node, boolean)
instead.start
node and end
node must not be null
.O(2^ (graph.N() + graph.E()))
graph
 the input graphstartNode
 the given start nodeendNode
 the given end nodedirected
 true
if the path should be considered as directed, false
otherwise
EdgeList
s each of which represents a path between the start and end nodepublic static YCursor findAllPathsCursor(Graph graph, Node startNode, Node endNode, boolean directed)
findAllPaths(Graph, Node, Node, boolean)
,
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.
The returned cursor only supports the operation YCursor.ok()
,
YCursor.current()
, YCursor.size()
and YCursor.next()
.
start
node and end
node must not be null
.O(2^ (graph.N() + graph.E()))
graph
 the input graphstartNode
 the given start nodeendNode
 the given end nodedirected
 true
if the path should be considered as directed, false
otherwise
YCursor
that calculates the next path in the sequencepublic static EdgeList[] findAllPaths(Graph graph, Node startNode, Node endNode, boolean directed, Filter filter)
findAllPaths(Graph, Node, Node, boolean)
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.
start
node and end
node must not be null
.O(2^ (graph.N() + graph.E()))
graph
 the input graphstartNode
 the given start nodeendNode
 the given end nodedirected
 true
if the path should be considered as directed, false
otherwisefilter
 a Filter
instance that accepts or rejects a found EdgeList
and adds it to the result
EdgeList
s each of which represents a path between the start and end node.

© Copyright 20002022, yWorks GmbH. All rights reserved. 

PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 