How to detect Tasks in a cycle

Question

class Program
{
    private static Task[] tasks;

    static void Main(string[] args)
    {
        tasks = new Task[]
        {
            new Task(() => Task.WaitAll(tasks[1])),
            new Task(() => Task.WaitAll(tasks[2])),
            new Task(() => Task.WaitAll(tasks[0])),
        };

        tasks[0].Start();
        tasks[1].Start();
        tasks[2].Start();

        Console.WriteLine(Task.WaitAll(tasks, 5000));
        Console.ReadLine();
    }
}

In the code sample above, I have set up three tasks "a", "b", "c" where "a" waits on "b" waits on "c" waits on "a".

Clearly, the WaitAll then returns false, since it is impossible for all tasks to complete.

My question is - is there any way, using Task Parallel Library, to detect the situation where Tasks are waiting in a cycle and, preferably, disallow it?

(This is to allow us to detect cyclic regions through reusing existing tasks)

Answer 1

You need to look into directed graphs and strongly connected component.

You could build a graph of your Tasks as you instantiate them and then compute the strongly connected components. For that you could use Tarjan's algorithm, here is an implementation in C#.

Or you could use a library like Quickgraph which handle that.