# Topological Sort
Given a digraph, put the vertices in order such that all its directed edges point from a vertex earlier in the order to a vertex later in the order (or report that doing so is not possible).
```java
/******************************************************************************
* Compilation: javac Topological.java
* Execution: java Topological filename.txt delimiter
* Dependencies: Digraph.java DepthFirstOrder.java DirectedCycle.java
* EdgeWeightedDigraph.java EdgeWeightedDirectedCycle.java
* SymbolDigraph.java
* Data files: https://algs4.cs.princeton.edu/42digraph/jobs.txt
*
* Compute topological ordering of a DAG or edge-weighted DAG.
* Runs in O(E + V) time.
*
* % java Topological jobs.txt "/"
* Calculus
* Linear Algebra
* Introduction to CS
* Advanced Programming
* Algorithms
* Theoretical CS
* Artificial Intelligence
* Robotics
* Machine Learning
* Neural Networks
* Databases
* Scientific Computing
* Computational Biology
*
******************************************************************************/
/**
* The {@code Topological} 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 depth-first search.
* 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 {@link DirectedCycle}, {@link DirectedCycleX}, and
* {@link EdgeWeightedDirectedCycle} for computing a directed cycle
* if the digraph is not a DAG.
* See {@link TopologicalX} for a nonrecursive queue-based algorithm
* for computing a topological order of a DAG.
*
* For additional documentation,
* see Section 4.2 of
* Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class Topological {
private Iterable order; // topological order
private int[] rank; // rank[v] = rank of vertex v in order
/**
* Determines whether the digraph {@code G} has a topological order and, if so,
* finds such a topological order.
* @param G the digraph
*/
public Topological(Digraph G) {
DirectedCycle finder = new DirectedCycle(G);
if (!finder.hasCycle()) {
DepthFirstOrder dfs = new DepthFirstOrder(G);
order = dfs.reversePost();
rank = new int[G.V()];
int i = 0;
for (int v : order)
rank[v] = i++;
}
}
/**
* Returns a topological order if the digraph has a topologial order,
* and {@code null} otherwise.
* @return a topological order of the vertices (as an interable) if the
* digraph has a topological order (or equivalently, if the digraph is a DAG),
* and {@code null} otherwise
*/
public Iterable order() {
return order;
}
/**
* Does the digraph have a topological order?
* @return {@code true} if the digraph has a topological order (or equivalently,
* if the digraph is a DAG), and {@code false} otherwise
*/
public boolean hasOrder() {
return order != null;
}
/**
* Does the digraph have a topological order?
* @return {@code true} if the digraph has a topological order (or equivalently,
* if the digraph is a DAG), and {@code false} otherwise
* @deprecated Replaced by {@link #hasOrder()}.
*/
@Deprecated
public boolean isDAG() {
return hasOrder();
}
/**
* The the rank of vertex {@code v} in the topological order;
* -1 if the digraph is not a DAG
*
* @param v the vertex
* @return the position of vertex {@code v} in a topological order
* of the digraph; -1 if the digraph is not a DAG
* @throws IllegalArgumentException unless {@code 0 <= v < V}
*/
public int rank(int v) {
validateVertex(v);
if (hasOrder()) return rank[v];
else return -1;
}
// throw an IllegalArgumentException unless {@code 0 <= v < V}
private void validateVertex(int v) {
int V = rank.length;
if (v < 0 || v >= V)
throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1));
}
/**
* Unit tests the {@code Topological} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
String filename = args[0];
String delimiter = args[1];
SymbolDigraph sg = new SymbolDigraph(filename, delimiter);
Topological topological = new Topological(sg.digraph());
for (int v : topological.order()) {
StdOut.println(sg.nameOf(v));
}
}
}
```
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://blog.sunilgudivada.dev/notebook/data-structures-and-algorithms/topics/graphs/topological-sort.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.