Package edu.princeton.cs.algs4

Class 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 252. 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 Detail

      • AcyclicLP

        public AcyclicLP​(EdgeWeightedDigraph digraph,
                 int s)
        Computes a longest paths tree from s to every other vertex in the directed acyclic graph digraph.
        Parameters:
        digraph - 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