y.algo
Class Paths

java.lang.Object
  |
  +--y.algo.Paths

public class Paths

extends Object

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

Constructor Summary

Paths()

Method Summary

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

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 - whether to search for a directed or undirected path

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.

Precondition:

GraphChecker.isSimple(graph);

Complexity:

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

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

Precondition:

GraphCheckers.isAcyclic(g)

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.

findLongestPath

public static EdgeList findLongestPath(Graph g)

Returns the longest directed path within the given acyclic graph.

Precondition:

GraphChecker.isAcyclic(g)

Parameters:

g - a directed acyclic graph

Returns:

an edgelist representing the longest directed path within the given graph

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 assiociated 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:

GraphChecker.isAcyclic(g)

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

Parameters:

g - a directed acyclic graph

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

Returns:

an edgelist representing the longest directed path within the given graph

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

Precondition:

GraphChecker.isAcyclic(g)

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.

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.

Complexity:

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

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.