Determining if graph is acyclic for Toplogical Sort

Question

I have successfully implemented a topological sorting algorithm, but I'm having trouble figuring out when to throw an exception when the inputted graph is not acyclic. Within the algorithm is there a way to check for this using the in-degree? Or something else for that matter?

public static List<String> topologicalSort(Graph graph) {

    if(graph.getDirected() == false)
        throw new UnsupportedOperationException();

    Queue<Vertex> queue = new LinkedList<Vertex>();

    HashMap<String, Vertex> tempMap = graph.getVertices();
    for(Vertex vertex : tempMap.values()) {
        if(vertex.getInDegree() == 0)
            queue.add(vertex);
    }

    if(queue.isEmpty())
        throw new UnsupportedOperationException();

    ArrayList<String> returnList = new ArrayList<String>();
    while(!queue.isEmpty()) {
        Vertex tempVert = queue.poll();
        returnList.add(tempVert.getName());
        tempVert.setVisited(true);
        for(Edge edge : tempVert.getEdges()) {

           if(edge.getOtherVertex().getVisited() == true)
                throw new UnsupportedOperationException();
           edge.getOtherVertex().setVisited(true);
           edge.getOtherVertex().decInDegree();

           if(edge.getOtherVertex().getInDegree() == 0)
               queue.add(edge.getOtherVertex());
        }

    }

    return returnList;
}

Answer 1

If the input is a graph with a a cycle, then you'll reach the point in the algorithm where you haven't added all the Nodes to the output, but haven't any further elements in the queue either (you can't add any node in the cycle to the queue because of the cyclic relationship).

I.e. check returnList.size() == graph.nodeCount() after the while loop (true means acyclic input, false means input had a cycle).

graph.nodeCount() should be the number of nodes in the graph at the beginning of the method.