y.algo
Class Paths

java.lang.Object
  y.algo.Paths

public class Paths
extends Object

Responsible for finding paths within a graph that have certain properties.

Constructor Summary

Paths()

Method Summary

static NodeList	constructNodePath(EdgeList path) Constructs a node path from a given edge path.
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 start with end node.
static EdgeList[]	findAllPaths(Graph graph, Node startNode, Node endNode, boolean directed, Filter filter) A variant of findAllPaths(Graph, Node, Node, boolean) that additionally allows to specify a filter for the paths to be returned.
static void	findAllPaths(Graph g, Node start, Node end, EdgeMap pathEdges) Marks all edges that belong to a directed path from start to end node.
static YCursor	findAllPathsCursor(Graph graph, Node startNode, Node endNode, boolean directed) A variant of findAllPaths(Graph, Node, Node, boolean) that returns its result not as a list but as a special cursor that calculates the next path in the sequence only when needed.
static EdgeList	findLongestPath(Graph g) Returns the longest directed path within the given acyclic graph.
static EdgeList	findLongestPath(Graph g, DataProvider edgeLength) Returns the longest directed path within a given acyclic weighted graph.
static void	findLongestPaths(Graph g, Node startNode, EdgeMap dist, NodeMap maxDist, EdgeMap predicate) Calculates the longest path from one vertex to all other vertices in a given acyclic graph
static EdgeList	findLongPath(Graph graph) Returns an edge list that contains the edges of a undirected simple path within the given graph.
static boolean	findPath(Graph g, NodeList topSort, Node startNode, Node endNode, EdgeMap predicate) Returns whether or not there is a directed path from one node to another node in an acyclic graph
static EdgeList	findPath(Graph graph, Node startNode, Node endNode, boolean directed) 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.

Methods inherited from class java.lang.Object

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

Constructor Detail

Paths

public Paths()

Method Detail

findPath

public static EdgeList findPath(Graph graph,
                                Node startNode,
                                Node endNode,
                                boolean directed)

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. 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.

Parameters:

graph - the input graph

startNode - the first node of the path

endNode - the last node of the path

directed - whether to search for a directed or undirected path

Complexity:

O(graph.N() + graph.E())

Precondition:

startNode != endNode

findLongPath

public static EdgeList findLongPath(Graph graph)

Returns 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);

findLongestPaths

public static void findLongestPaths(Graph g,
                                    Node startNode,
                                    EdgeMap dist,
                                    NodeMap maxDist,
                                    EdgeMap predicate)

Calculates the longest path from one vertex to all other vertices in a given acyclic graph

Parameters:

g - a directed acyclic graph.

startNode - the node, for which the distances are calculated.

dist - the distances for the edges.

maxDist - here the result will be stored.

predicate - only edges for which predicate is true are considered.

Precondition:

GraphCheckers.isAcyclic(g)

findLongestPath

public static EdgeList findLongestPath(Graph g)

Returns the longest directed path within the given acyclic graph.

Parameters:

g - a directed acyclic graph

Returns:

an edge list representing the longest directed path within the given graph

Precondition:

GraphChecker.isAcyclic(g)

findLongestPath

public static EdgeList findLongestPath(Graph g,
                                       DataProvider edgeLength)

Returns 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.

Parameters:

g - a directed acyclic graph

edgeLength - a data provider that must provide the length of each edge as an int value

Returns:

an edge list representing the longest directed path within the given graph

Preconditions:

GraphChecker.isAcyclic(g)

edgeLength.getInt(e) > 0 for all edges e of g

constructNodePath

public static NodeList constructNodePath(EdgeList path)

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.

findPath

public static boolean findPath(Graph g,
                               NodeList topSort,
                               Node startNode,
                               Node endNode,
                               EdgeMap predicate)

Returns whether or not there is a directed path from one node to another node in an acyclic graph

Parameters:

g - the acyclic graph which contains the two nodes.

topSort - a topological sorting of the nodes of the graph.

predicate - only edges for which predicate is true are considered.

Precondition:

GraphChecker.isAcyclic(g)

findAllPaths

public static final void findAllPaths(Graph g,
                                      Node start,
                                      Node end,
                                      EdgeMap pathEdges)

Marks all edges that belong to a directed path from start to end node.

Parameters:

g - the input graph

start - the start node

end - the end node

pathEdges - the result. For each edge a boolean value will indicate whether or not it belongs to a path connecting the two nodes.

Complexity:

O(g.N()+g.E())

findAllChains

public static EdgeList[] findAllChains(Graph graph,
                                       boolean directed)

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.

Parameters:

graph - the input graph

Returns:

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(EdgeList) can be used to convert an edge path to a node path.

Complexity:

O(g.N()+g.E())

findAllPaths

public static EdgeList[] findAllPaths(Graph graph,
                                      Node startNode,
                                      Node endNode,
                                      boolean directed)

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(Graph, Node, Node, boolean) instead.

Parameters:

graph - the input graph

startNode - the start node

endNode - the end node

directed - whether or not to consider the edges in the graph to be directed or not.

Returns:

an array of EdgeLists each representing a path between start and end node.

Complexity:

O(2^(g.N()+g.E()))

Precondition:

graph, startNode, and endNode may not be null.

findAllPathsCursor

public static YCursor findAllPathsCursor(Graph graph,
                                         Node startNode,
                                         Node endNode,
                                         boolean directed)

A variant of findAllPaths(Graph, Node, Node, boolean) 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 YCursor.ok(), YCursor.current(), YCursor.size() and YCursor.next().

findAllPaths

public static EdgeList[] findAllPaths(Graph graph,
                                      Node startNode,
                                      Node endNode,
                                      boolean directed,
                                      Filter filter)

A variant of findAllPaths(Graph, Node, Node, boolean) that additionally allows to specify a filter for the paths to be returned.

Parameters:

filter - a filter that tests for each found EdgeList if it should make it to the result list.