multithreaded algo for cycle detection in a directed graph

Question

I am looking for a concurrent algorithm which would help me in detecting cycles in a directed graph.

I know that the sequential algorithm uses a dfs with colouring, however I think that it will fail in a multi threaded environment. One example of a directed graph to illustrate it:

A->(B, C), B-> (D), D-> (E), C-> (E), E-> (F)

                         A
                        / \
                       B   C
                       |   |
                       D   |
                        \ /
                         E
                         |
                         F

(I hope the above makes it clear. The edges in the graph are all top to botton)

For the above directed graph, the following execution is possible during concurrent execution.

(the colouring scheme I assumed is white - unvisited, grey - execution of dfs not finished and black - finished execution and visit)

Dfs(B) by thread 1, which eventually colour E as grey and does a dfs(E) (leading to F). Before this is finished, thread 2 executes dfs(C). It realises that E is grey and reports a cycle which is obviously not the case.

I checked that Tarjan's algo could also be used for cycle detection, but again I do not think its execution will be correct in a multi threaded environment.

Could somebody please help me out on this?

Thanks.

Answer 1

As Ira states let each thread use its own colour.

But, If you have a fixed number of threads use a bit map for each of the colours. As, long as you processor supports an atomic bit test and set (i.e. BTST on x86) you wont event need locking as each thread will be testing and setting a different bit.

If the bit is set then the item is coloured grey.

PS: If you need more colours then you can use more bits.

Answer 2

For multithreaded cycle detection, it's better to use a variant of the Kahn algorithm (for topological sort) instead of DFS. This uses the facts that:

1) If a directed graph is acyclic, then it has at least one vertex with no in-edges, and at least one vertex with no out-edges;

2) A vertex with no in-edges or no out-edges cannot participate in a cycle; so

3) If you remove a vertex with no in-edges or no out-edges, you're left with a smaller directed graph with the same cycles as the original.

So, to do a parallel cycle detection, you can:

1) First, use a parallel BFS to build a data structure that keeps track of the in-degree and out-degree of each vertex.

2) Then, in parallel, remove vertices with in-degree or out-degree 0. Note that removing a vertex will decrement the in-degrees or out-degrees of adjacent nodes.

3) When you're out of vertices to remove, you're left with all the vertices that are involved in cycles. If there aren't any, then the original graph was acyclic.

Both the parallel BFS (step 1) and parallel vertex removal (step 2) are easily accomplished with parallel work queues. In step 1, when you see a vertex for the first time, add a task to the queue that processes adjacent vertices. In step 2, when you decrement a vertex's in-degree or out-degree to 0, add a task to remove it from the graph.

Note that this algorithm works just as well if you remove only nodes with in-degree 0 or nodes with out-degree 0, but opportunities for parallelism are somewhat reduced.