Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

Suppose I have some edges:

edges = {1 -> 2, 2 -> 3, 3 -> 1, 4 -> 5, 3 -> 6, 7 -> 8, 8 -> 9, 8 -> 10};

And I make a graph:

g = Graph[edges, VertexLabels -> "Name", ImagePadding -> 10]

graph with 3 connected groups

After seeing the graph, you realize that there are three separate sub-graphs or families in it, and I want to see them separately. This is what I have done:

families = {Subgraph[g, {1, 2, 3, 6}], Subgraph[g, {4, 5}], Subgraph[g, {7, 8, 9, 10}]};
nMax = 3;
Manipulate[families[[n]], {n, 1, nMax, 1}]

manipulate generated graph viewer

I would like to know how to calculate nMax and families automatically. My real problem has thousands of edges and it is not viable to do it visually.

share|improve this question
1  
Have a look at Kosaraju's algorithm I had to implement this for Coursera's algorithms class and it worked great even on huge graphs (5 million edges) –  Ivo Flipse Apr 15 '12 at 8:46
    
@IvoFlipse Thank you for the link. Computing Leonid's answer for my 3.3 million edges took less than 4 seconds on my laptop. –  Gustavo Delfino Apr 15 '12 at 14:47
add comment

1 Answer

up vote 15 down vote accepted

Here is one way:

Subgraph[g, #, VertexLabels -> "Name", ImagePadding -> 10] & /@ 
    ConnectedComponents[UndirectedGraph[g]]

enter image description here

The proper terminology for what you asked, as hinted by the code, is connected components of a graph. I had to convert a graph to undirected one, since connectivity in a directed graph is a stronger condition, and not what you were after here.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.