Jump to content
  • Advertisement
Sign in to follow this  
johnnyk

Detecting strongly connected components

This topic is 4621 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm attempting to take a graph and detect the strongly connected components of it but I'm having some difficulty understanding the descriptions of this algorithm I find online. It has been discussed before on these forums as well (here and here, mostly thanks to Ury :) So I have a directed graph, and I want to find the parts that are reliant on each other (for making a contact graph, but that shouldnt matter since its just a graph). Following the Tarjan algorithm (described here ) I should visit all the nodes of the graph in Depth First Order and record how many steps the search continues for each node. And I'm already lost, because where do I start? There is no "root" for this graph, its just a graph not a tree, and if I pick node randomly it could be a dead end, and I would miss all the other nodes. Also, the algorithm talks about each node's "root". What is a root when youre dealing with a graph? There could be multiple source nodes that have edges to a particular node. If anyone can give a brief description I would appreciate it, I'm not very familiar with graph theory and find the notation in the articles confusing, but the underlying idea seems simple if I can just get past how its explained (i'm hoping!) -John

Share this post


Link to post
Share on other sites
Advertisement
Quote:
Original post by johnnyk
I should visit all the nodes of the graph in Depth First Order and record how many steps the search continues for each node. And I'm already lost, because where do I start? There is no "root" for this graph, its just a graph not a tree, and if I pick node randomly it could be a dead end, and I would miss all the other nodes.

Also, the algorithm talks about each node's "root". What is a root when youre dealing with a graph? There could be multiple source nodes that have edges to a particular node.

If anyone can give a brief description I would appreciate it, I'm not very familiar with graph theory and find the notation in the articles confusing, but the underlying idea seems simple if I can just get past how its explained (i'm hoping!)

-John


First step of the algorithm is to create a new vertex x, and connect it to every other node in graph (v), by a directed connection (x, v).

Then, starting in x, you build a tree (as described in algorithm).

The algorithm then proceeds to search for nodes (roots) in this tree, for which the subtrees represent the strongly connected relation.

Note: I used this description (http://www.ics.uci.edu/~eppstein/161/960220.html#sca) of Tarjan's algorithm, so I hope I got the basics right.

Share this post


Link to post
Share on other sites
That description makes perfect sense, thank you! Couldn't say much for the 4 or 5 other descriptions I read, its all crystal clear after that one though.

Now that I know how it works, I think I'll just use the Boost graph library implementation :)

Thanks again
-John

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!