Package edu.princeton.cs.algs4

Class AcyclicLP

Object

edu.princeton.cs.algs4.AcyclicLP

public class AcyclicLP
extends Object

The AcyclicLP class represents a data type for solving the single-source longest paths problem in edge-weighted directed acyclic graphs (DAGs). The edge weights can be positive, negative, or zero.

This implementation uses a topological-sort based algorithm. The constructor takes Θ(V + E) time in the worst case, where V is the number of vertices and E is the number of edges. Each instance method takes Θ(1) time. It uses Θ(V) extra space (not including the edge-weighted digraph).

This correctly computes longest paths if all arithmetic performed is without floating-point rounding error or arithmetic overflow. This is the case if all edge weights are integers and if none of the intermediate results exceeds 2⁵². Since all intermediate results are sums of edge weights, they are bounded by V C, where V is the number of vertices and C is the maximum absolute value of any edge weight.

For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

Author:

Robert Sedgewick, Kevin Wayne

Constructor Summary

Constructors

Constructor	Description
AcyclicLP(EdgeWeightedDigraph G, int s)	Computes a longest paths tree from s to every other vertex in the directed acyclic graph G.

Method Summary

Modifier and Type	Method	Description
double	distTo(int v)	Returns the length of a longest path from the source vertex s to vertex v.
boolean	hasPathTo(int v)	Is there a path from the source vertex s to vertex v?
static void	main(String[] args)	Unit tests the AcyclicLP data type.
Iterable<DirectedEdge>	pathTo(int v)	Returns a longest path from the source vertex s to vertex v.

Methods inherited from class java.lang.Object

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

Constructor Detail

AcyclicLP

public AcyclicLP(EdgeWeightedDigraph G,
                 int s)

Computes a longest paths tree from s to every other vertex in the directed acyclic graph G.

Parameters:

G - the acyclic digraph

s - the source vertex

Throws:

IllegalArgumentException - if the digraph is not acyclic

IllegalArgumentException - unless 0 <= s < V

Method Detail

distTo

public double distTo(int v)

Returns the length of a longest path from the source vertex s to vertex v.

Parameters:

v - the destination vertex

Returns:

the length of a longest path from the source vertex s to vertex v; Double.NEGATIVE_INFINITY if no such path

Throws:

IllegalArgumentException - unless 0 <= v < V

hasPathTo

public boolean hasPathTo(int v)

Is there a path from the source vertex s to vertex v?

Parameters:

v - the destination vertex

Returns:

true if there is a path from the source vertex s to vertex v, and false otherwise

Throws:

IllegalArgumentException - unless 0 <= v < V

pathTo

public Iterable<DirectedEdge> pathTo(int v)

Returns a longest path from the source vertex s to vertex v.

Parameters:

v - the destination vertex

Returns:

a longest path from the source vertex s to vertex v as an iterable of edges, and null if no such path

Throws:

IllegalArgumentException - unless 0 <= v < V

main

public static void main(String[] args)

Unit tests the AcyclicLP data type.

Parameters:

args - the command-line arguments