Figuring out the path of a circular dependency

Question

I am having trouble figuring out how I can print out the path of which circular dependency (cycle) exists. If the cycle exists that is. I am doing a topological sort on a graph (representing a project) that contains different vertices (tasks). Is there a easy way to do this or is another algorithm like depth-first search better for this?

Here is what i have so far:

public boolean canProjectBeCompleted() { 

    if(this.getProjectTasks() == null) {
        return false;
    }

    LinkedList<Task> queue = new LinkedList<Task>();
    Task task;
    int counter = 0;

    Iterator<Task> taskIterator = this.getProjectTasks().values().iterator();
    while(taskIterator.hasNext()) {
        Task t = taskIterator.next();
        if(t.getInEdgesPredecessors().size() == 0) {
            queue.add(t);
        }
    }

    while(!queue.isEmpty()) {
        task = queue.removeFirst();
        counter++;
        for(int i = 0; i < task.getOutEdgesSuccesors().size(); i++) {
            Task neighbour = task.getOutEdgesSuccesors().get(i);
            neighbour.setCopyNumberOfIncomingEdges(neighbour.getCopyNumberOfIncomingEdges()-1);
            if(neighbour.getCopyNumberOfIncomingEdges() == 0) {
                queue.add(neighbour);
            }
        }
    }
    if(counter < amountOfTasks) {
        return false; //Cycle found, The topological sort cannot complete
    }
    return true; //No cycle found
}

Thanks in advance! :)

Answer 1

How about this?

You know that vertices that are part of cycles must have both out-going edges and in-going edges. So begin like you would with topological sorting and "remove" (or simply mark) vertices with 0 in-going edges and remove their out-going edges. Go to it's neighbors and remove each one which now has 0 in-going edges, and continue. If you still have vertices left in the graph you know that there is a cycle somewhere in the remaining vertices, but not where, or how many cycles. So this is where you do a sort-of-reversed topological sort where you begin removing vertices with 0 out-going edges. This is because you know that a vertex with no out-going edges cannot be part of a cycle. Continue as you would with topological sort, i.e. remove the vertex's edges, and repeat with the neighbors. Those vertices that are left in your graph are part of one or more cycles. To find out the amount of cycles and the order the vertices appear in each cycle, you can perform a depth-first search amongst the remaining graph.

If I'm not mistaken I believe the complexity should be O(|V| + |E|)

Answer 2

The adjacency matrix A for your graph will have give you the information needed, see http://en.wikipedia.org/wiki/Adjacency_matrix

For example, if the entries are 0 on the diagonal for the matrix A to the power p, then there is no cycle of length p. So, if you have access to fast matrix multiplication, then this might be easiest to implement.

Answer 3

There is a simple test for presence of cycles in graph: Continuous tree ( graph without cycles) contains at exaclty (nodes - 1) eges

This will detect presence of cycles in undirected graph, and duplicate paths in directed.

To detect presence of cycles, walk graph breadth-first ( as you are already doing ) and store nodes in hash set as they occur. In case node is already contained in this set, there is a cycle and you can stop search immediately. Alternative to hash set would be a flag on node itself ( but this would render search procedure not thread safe, may require object modification, or attaching some aspect at runtime )

As I see in your code, you are modifying copyNumberOfIncomingEdges wuthout checking value first. Where do you set up this property?