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;
}

Just mark every node that you iterate over as "visited" and check every new node you deal with if it was already "visited" and if so - throw an exception. — Nir Alfasi, Jul 02 '14 at 02:56
Yes, but if I iterate, and can not longer continue since no vertices have an indegree of 0, this will not throw an exception, it will simply print a list shorter than the expected return. — user3743340, Jul 02 '14 at 03:05
@user3743340 that's your answer in your own comment "a list shorter than ..."; shorter than the list of vertices; see answer by user fabian below which is the correct simple answer you are looking for. — necromancer, Jul 02 '14 at 03:17

score 3 · Accepted Answer · answered Jul 02 '14 at 03:14

3

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.

answered Jul 02 '14 at 03:14

fabian

80,457
12
86
114

This seems to be better than mine :) should be correct. – Pham Trung Jul 02 '14 at 03:17
Perfect. Simple and just what I was looking for. – user3743340 Jul 02 '14 at 03:25

Pham Trung · Answer 2 · 2014-07-02T03:09:14.113

1

You can use Tarjan SCC to find all the strongly connected component in the directed graph, if there is a component has size > 1 (more than one node in that component), so there is a cycle in that component.

You can stop as soon as the algorithm found a strongly connected component with size greater than 1.

edited Jul 02 '14 at 03:09

answered Jul 02 '14 at 03:02

Pham Trung

11,204
2
24
43

While I understand this would work, efficiency is important. Is there no other way, in the current set up of my code, that would allow for a simple check? – user3743340 Jul 02 '14 at 03:14
@user3743340 take a look at [this](http://stackoverflow.com/questions/583876/how-do-i-check-if-a-directed-graph-is-acyclic) – Pham Trung Jul 02 '14 at 03:15

Determining if graph is acyclic for Toplogical Sort

2 Answers2