y.algo
Class Paths

java.lang.Object
  y.algo.Paths

public class Paths
extends java.lang.Object

This class provides methods for finding paths within a graph that have certain properties.

Definitions

• A path of length 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 (vi-1, vi) in E, for each i = 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.

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

findPath

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

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.

Precondition:

startNode != endNode

Complexity:

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

Parameters:

graph - the input graph

startNode - the first node of the path

endNode - the last node of the path

directed - true if the path should be directed, false otherwise

Returns:

an EdgeList containing the path edges between the start node and the end node

findLongPath

public static EdgeList findLongPath(Graph graph)

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

Precondition:

The graph must be simple.

Complexity:

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

Parameters:

graph - the given graph

Returns:

an EdgeList containing the edges of an undirected simple path

findLongestPaths

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

Precondition:

The graph must be acyclic.

Parameters:

graph - a directed acyclic graph

startNode - the node for which the distances are calculated

dist - the EdgeMap that returns the distance (i.e. weight) of type double for each edge

maxDist - the NodeMap that will be filled during the execution and holds the maximum distance between the given node and all other nodes

predicate - the EdgeMap that returns a boolean value indicating whether or not an edge should be considered during the path search

findLongestPath

public static EdgeList findLongestPath(Graph graph)

Returns the longest directed path in the given acyclic graph.

Precondition:

The graph must be acyclic.

Parameters:

graph - a directed acyclic graph

Returns:

an EdgeList containing the edges of the longest directed path

findLongestPath

public static EdgeList findLongestPath(Graph graph,
                                       DataProvider edgeLength)

Returns the longest directed path in 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.

Preconditions:

The graph must be acyclic.

edgeLength.getInt(e) >= 0 for all edges e of the graph

Parameters:

graph - a directed acyclic graph

edgeLength - the DataProvider that returns the non-negative integer length of each edge

Returns:

an EdgeList containing the edges of the longest directed path

constructNodePath

public static NodeList constructNodePath(EdgeList path)

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

Parameters:

path - the given path of edges

Returns:

a path of nodes from the given path of edges

findPath

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

Precondition:

The graph must be acyclic.

Parameters:

graph - an acyclic graph which contains the two nodes

topSort - a list of nodes sorted in topological order

predicate - the EdgeMap that returns a boolean value indicating whether or not an edge should be considered during the path search

Returns:

true if a directed path from a start node to another node exists, false otherwise

findAllPaths

public static final 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.

Complexity:

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

Parameters:

graph - the input graph

startNode - the given start node

endNode - the given end node

pathEdges - 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 nodes

findAllChains

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

Returns all chains present in the given graph.

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.

Method constructNodePath(EdgeList) can be used for converting an edge path to a node path.

Complexity:

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

Parameters:

graph - the input graph

directed - true if the chain should be considered as directed, false otherwise

Returns:

an array of EdgeLists each of which contains the edges (at least two) that make up a chain

See Also:

constructNodePath(EdgeList)

findAllPaths

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

The number of different paths connecting two nodes can be exponential to the 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.

Precondition:

Input graph, start node and end node must not be null.

Complexity:

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

Parameters:

graph - the input graph

startNode - the given start node

endNode - the given end node

directed - true if the path should be considered as directed, false otherwise

Returns:

an array of EdgeLists each of which represents a path between the start and end node

findAllPathsCursor

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

The returned cursor only supports the operation YCursor.ok(), YCursor.current(), YCursor.size() and YCursor.next().

Precondition:

Input graph, start node and end node must not be null.

Complexity:

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

Parameters:

graph - the input graph

startNode - the given start node

endNode - the given end node

directed - true if the path should be considered as directed, false otherwise

Returns:

a YCursor that calculates the next path in the sequence

findAllPaths

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

Precondition:

Input graph, start node and end node must not be null.

Complexity:

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

Parameters:

graph - the input graph

startNode - the given start node

endNode - the given end node

directed - true if the path should be considered as directed, false otherwise

filter - a Filter instance that accepts or rejects a found EdgeList and adds it to the result

Returns:

an array of EdgeLists each of which represents a path between the start and end node.