Package edu.princeton.cs.algs4

Class TopologicalX

  • public class TopologicalX
extends Object
    The TopologicalX class represents a data type for determining a topological order of a directed acyclic graph (DAG). A digraph has a topological order if and only if it is a DAG. The hasOrder operation determines whether the digraph has a topological order, and if so, the order operation returns one.

    This implementation uses a nonrecursive, queue-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 digraph).

    See DirectedCycle, DirectedCycleX, and EdgeWeightedDirectedCycle to compute a directed cycle if the digraph is not a DAG. See Topological for a recursive version that uses depth-first search.

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

    Author:
    Robert Sedgewick, Kevin Wayne

    • Constructor Detail

      • TopologicalX

        public TopologicalX​(Digraph digraph)
        Determines whether digraph has a topological order and, if so, finds such a topological order.
        Parameters:
        digraph - the digraph

      • TopologicalX

        public TopologicalX​(EdgeWeightedDigraph digraph)
        Determines whether the edge-weighted digraph has a topological order and, if so, finds such a topological order.
        Parameters:
        digraph - the digraph

    • Method Detail

      • order

        public Iterable<Integer> order()
        Returns a topological order if the digraph has a topological order, and null otherwise.
        Returns:
        a topological order of the vertices (as an iterable) if the digraph has a topological order (or equivalently, if the digraph is a DAG), and null otherwise

      • hasOrder

        public boolean hasOrder()
        Does the digraph have a topological order?
        Returns:
        true if the digraph has a topological order (or equivalently, if the digraph is a DAG), and false otherwise

      • rank

        public int rank​(int v)
        The rank of vertex v in the topological order; -1 if the digraph is not a DAG
        Parameters:
        v - vertex
        Returns:
        the position of vertex v in a topological order of the digraph; -1 if the digraph is not a DAG
        Throws:
        IllegalArgumentException - unless 0 <= v < V

      • main

        public static void main​(String[] args)
        Unit tests the TopologicalX data type.
        Parameters:
        args - the command-line arguments