Sign in to follow this  
johnnyk

Detecting strongly connected components

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
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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this