public class AcyclicLP extends Object
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 time proportional to V + E,
where V is the number of vertices and E is the number of edges.
Each call to distTo(int)
and hasPathTo(int)
takes constant time;
each call to pathTo(int)
takes time proportional to the number of
edges in the shortest path returned.
For additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
AcyclicLP(EdgeWeightedDigraph G,
int s)
Computes a longest paths tree from
s to every other vertex in
the directed acyclic graph G . |
Modifier and Type | Method and 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 . |
public AcyclicLP(EdgeWeightedDigraph G, int s)
s
to every other vertex in
the directed acyclic graph G
.G
- the acyclic digraphs
- the source vertexIllegalArgumentException
- if the digraph is not acyclicIllegalArgumentException
- unless 0 <= s < V
public double distTo(int v)
s
to vertex v
.v
- the destination vertexs
to vertex v
;
Double.NEGATIVE_INFINITY
if no such pathIllegalArgumentException
- unless 0 <= v < V
public boolean hasPathTo(int v)
s
to vertex v
?v
- the destination vertextrue
if there is a path from the source vertex
s
to vertex v
, and false
otherwiseIllegalArgumentException
- unless 0 <= v < V
public Iterable<DirectedEdge> pathTo(int v)
s
to vertex v
.v
- the destination vertexs
to vertex v
as an iterable of edges, and null
if no such pathIllegalArgumentException
- unless 0 <= v < V
public static void main(String[] args)
AcyclicLP
data type.args
- the command-line arguments