CODEWITHSUNDEEP
algorithmgraph-algorithm
Sachin
Sachin

Reputation: 375

How to process nodes of strongly connected components in a directed graph?

I am a beginner in area of graph algorithms programming. I am struggling with an interesting problem regarding strongly connected components and any help regarding that is highly appreciated.

In my application, the goal is to execute tasks on multiple threads as far as possible. These tasks are denoted as nodes in the directed graph and tasks may have cyclic dependencies. Cyclic dependencies are broken by finding the strongly connected components and then enforcing a predefined rule to delete an edge. This way, all tasks in a strongly connected component will end up executing serially.

Now consider an example where tasks 1,2,...8 have the following dependency pattern. {1 -> 2, 2 -> 3, 3 -> 1, 3 -> 4, 4 -> 5, 5 -> 6, 6 -> 4, 7 -> 8}. Using the Strongly connected components and predefined rule to break cyclic dependencies, we get three sets of nodes i.e. A={1 -> 2 -> 3}, B={4 -> 5 -> 6}, and C={7 -> 8}, but since A and B are connected by an edge they can not execute in parallel.

I would like to know if there is any algorithm or set of algorithms which I can use to get sets of nodes such that I can put A and B in sequential execution whereas C can be executed in parallel to A or B. As per my understanding topographical sort could be helpful, but it is only used for acyclic graphs. Any suggestion or help is highly appreciated. Thank you.

Upvotes: 0

Views: 249

Answers (1)

Ulrich Schwarz
Ulrich Schwarz

Reputation: 7727

The quotient graph that you describe with nodes A, B, C etc. is always acyclic: if it had a cycle, for example involving A and B, all tasks in A are reachable from all tasks in B and vice versa, so A and B are the same SCC. So yes, you can toposort that graph.

Upvotes: 2

Related Questions