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.

$\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
    Apr 15 '12 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$ Apr 15 '12 at 14:47
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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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