Search this API

## y.algo Class Paths

```java.lang.Object
y.algo.Paths
```

`public class Pathsextends 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 `EdgeList`s each of which contains the edges (at least two) that make up a chain
`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 `EdgeList`s 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 `EdgeList`s each of which represents a path between the start and end node.