Class AcyclicLP
 Object

 edu.princeton.cs.algs4.AcyclicLP

public class AcyclicLP extends Object
TheAcyclicLP
class represents a data type for solving the singlesource longest paths problem in edgeweighted directed acyclic graphs (DAGs). The edge weights can be positive, negative, or zero.This implementation uses a topologicalsort 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 edgeweighted digraph).
This correctly computes longest paths if all arithmetic performed is without floatingpoint rounding error or arithmetic overflow. This is the case if all edge weights are integers and if none of the intermediate results exceeds 2^{52}. 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 froms
to every other vertex in the directed acyclic graphG
.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description double
distTo(int v)
Returns the length of a longest path from the source vertexs
to vertexv
.boolean
hasPathTo(int v)
Is there a path from the source vertexs
to vertexv
?static void
main(String[] args)
Unit tests theAcyclicLP
data type.Iterable<DirectedEdge>
pathTo(int v)
Returns a longest path from the source vertexs
to vertexv
.



Constructor Detail

AcyclicLP
public AcyclicLP(EdgeWeightedDigraph G, int s)
Computes a longest paths tree froms
to every other vertex in the directed acyclic graphG
. Parameters:
G
 the acyclic digraphs
 the source vertex Throws:
IllegalArgumentException
 if the digraph is not acyclicIllegalArgumentException
 unless0 <= s < V


Method Detail

distTo
public double distTo(int v)
Returns the length of a longest path from the source vertexs
to vertexv
. Parameters:
v
 the destination vertex Returns:
 the length of a longest path from the source vertex
s
to vertexv
;Double.NEGATIVE_INFINITY
if no such path  Throws:
IllegalArgumentException
 unless0 <= v < V

hasPathTo
public boolean hasPathTo(int v)
Is there a path from the source vertexs
to vertexv
? Parameters:
v
 the destination vertex Returns:
true
if there is a path from the source vertexs
to vertexv
, andfalse
otherwise Throws:
IllegalArgumentException
 unless0 <= v < V

pathTo
public Iterable<DirectedEdge> pathTo(int v)
Returns a longest path from the source vertexs
to vertexv
. Parameters:
v
 the destination vertex Returns:
 a longest path from the source vertex
s
to vertexv
as an iterable of edges, andnull
if no such path  Throws:
IllegalArgumentException
 unless0 <= v < V

main
public static void main(String[] args)
Unit tests theAcyclicLP
data type. Parameters:
args
 the commandline arguments

