CODEWITHSUNDEEP
c++graphllvm
zneak
zneak

Reputation: 138251

How can I find strongly-connected components within larger strongly-connected components?

I have a program that needs to detect cycles (and nodes that are members of that cycle) in directed graphs. To do this, I use LLVM's strongly-connected components algorithm. It's pretty easy to use and it does pretty much what it should:

vector<vector<PreAstBasicBlock*>> stronglyConnectedComponents;
for (auto iter = scc_begin(&function); iter != scc_end(&function); ++iter)
{
    if (iter.hasLoop())
    {
        stronglyConnectedComponents.push_back(*iter);
    }
}

This correctly identifies simple SCCs like this simple one:

Strongly-connected component: node A goes to node B, node B goes to node C, node C goes to node B and D. Nodes B and C are part of a strongly-connected compoenent.

This is great, but I'd love to know when I have strongly-connected components within each larger strongly-connected components. For instance, this is identified as a single SCC:

Same graph as before, except that there is an edge from D to A.

That's absolutely correct, since every node in that graph is reachable starting from any other node. However, B⇄C has the additional property that it is independent of the D→A back-edge. It is an SCC by itself and it has a single entry node and a single exiting node: I could replace it with one single node and I wouldn't have edges poking in or out of its conceptual middle.

How can I find these smaller strongly-connected components in the strongly-connected components?

Upvotes: 1

Views: 418

Answers (1)

druckermanly
druckermanly

Reputation: 2741

So I was trying to craft a nice response / things you can do with more functions available to you, but was working on it offline and my computer crashed :(.

I've recreated the core of what I was trying to say, that only solves your immediate problem / example, in pseudo-code using a nonexistent GetConnectedComponents(...) helper function whose idealized behavior you can hopefully understand from context:

bool HasConnectedSubgraph(Graph& entire_graph) {
  for (const auto& connected_subgraph : GetConnectedComponents(entire_graph)
    for (const auto& connected_node : connected_subgraph) {
      local_copy = connected_subgraph;
      local_copy.erase(std::remove_if(local_copy.begin(), local_copy.end(), 
          [&](const Node& n) {return n == connected_node}) , local_copy.end());
      if (!GetConnectedComponents(local_copy).empty()) {
        return true;
      }
    }
  }
  return false;
}

This certainly isn't efficient or pretty, but should be enough to springboard your thoughts on the problem.

Upvotes: 2

Related Questions