| AcyclicLP Class |
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 time proportional to V + E, where V is the number of vertices and E is the number of edges. Afterwards, the DistTo() and HasPathTo() methods take constant time and the PathTo() method takes time proportional to the number of edges in the longest path returned.
Inheritance HierarchyNamespace: Algs4Net
Assembly: Algs4Net (in Algs4Net.dll) Version: 1.0.0.0 (1.0.0.0)
Syntaxpublic class AcyclicLP
The AcyclicLP type exposes the following members.
Constructors| Name | Description | |
|---|---|---|
 | AcyclicLP |
Computes a longest paths tree from s to every other vertex in
the directed acyclic graph G. |
Methods| Name | Description | |
|---|---|---|
| DistTo |
Returns the length of a longest path from the source vertex s to vertex v. |
| HasPathTo |
Is there a path from the source vertex s to vertex v? |
 | MainTest |
Demo test the AcyclicLP data type. |
| PathTo |
Returns a longest path from the source vertex s to vertex v. |
RemarksFor additional documentation, see Section 4.4 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
This class is a C# port from the original Java class AcyclicLP implementation by the respective authors.
See Also