Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
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
up vote 15 down vote accepted

Here is one way:

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

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

Your Answer


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.