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! :)

I suggest you look at the answers to an earlier question about [Finding all cycles in graph](http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph). In fact, i think i'm going to vote to close this question as a duplicate. — Tom Anderson, Oct 18 '11 at 08:54
Not exactly duplicate as he is definitely looking for presence of cycle — Konstantin Pribluda, Oct 18 '11 at 17:46

score 1 · Accepted Answer · answered Oct 21 '11 at 22:54

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|)

Konstantin Pribluda · Answer 2 · 2011-10-18T08:25:04.283

-1

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?

edited Oct 18 '11 at 08:25

answered Oct 17 '11 at 09:50

Konstantin Pribluda

12,329
1
30
35

(node - 1) edges: that is only true for a undirected graph isnt it? this is a directed one. – Stinis87 Oct 17 '11 at 10:12
Ok see the point. In case of directed graph this would indicate that there are some duplicate paths ( but not rule out cycles, they would violate this – Konstantin Pribluda Oct 17 '11 at 11:14
-1. I'm afraid that Stinis wants to know "the path of which circular dependency (cycle) exists", not just whether one exists. It's not obvious to me how your approach can find that. If you can explain how, i will happily turn my downvote into an upvote. – Tom Anderson Oct 18 '11 at 08:48
Which node is easy: If you see node for second time, it is on cicrular path. If you are interested on just first such nide, stop processing. Continue if you like to have all. Determining complete path would require some kind of node path storage – Konstantin Pribluda Oct 18 '11 at 12:02
I don't think so. Consider A->B, A->C, B->D, C->D. If you start walking at A, you will see D twice, but there is no cycle. – Tom Anderson Oct 19 '11 at 16:46
See the point. Breadth first is unsuitable. Depth first should do the trick though – Konstantin Pribluda Oct 19 '11 at 18:44

score -1 · Answer 3 · answered Oct 17 '11 at 10:46

-1

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.

answered Oct 17 '11 at 10:46

Per Alexandersson

2,443
1
22
28

-1. I'm afraid that Stinis wants to know "the path of which circular dependency (cycle) exists", not just whether one exists. If that information can be recovered from the matrix, please explain how, and i will happily turn my downvote into an upvote. – Tom Anderson Oct 18 '11 at 08:46

Figuring out the path of a circular dependency

3 Answers3