15
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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) $\endgroup$
    – Ivo Flipse
    Commented Apr 15, 2012 at 8:46
  • $\begingroup$ @IvoFlipse Thank you for the link. Computing Leonid's answer for my 3.3 million edges took less than 4 seconds on my laptop. $\endgroup$
    – Gustavo Delfino
    Commented Apr 15, 2012 at 14:47

1 Answer 1

Reset to default
19
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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