Re: [igraph] decompose time

[Tamás Nepusz]

Hi Bernie, 

It's not finding the weakly connected components that takes a lot of time but 
the part which generates the subgraphs. Earlier igraph versions generated the 
subgraphs by copying the entire graph and removing the unneeded vertices -- 
which of course takes a lot of time if your graph is large and you only need a 
small chunk of it.

I'd advise you to try running clusters() on your graph first -- this gives you 
a VertexClustering whose membership vector identifies the weakly connected 
components:

cl = graph.clusters()

Then you can get the membership vector as follows:

cl.membership

or extract the giant cluster:

cl.giant()

or any other cluster by its index:

cl.subgraph(cluster_index) 

-- 
T.


On Friday, 20 April 2012 at 00:03, Bernie Hogan wrote:

> Hi all, 
> 
> It seems that decompose() is taking a devastatingly long time (i.e. ~20 
> minutes) on a network of around 150k nodes and 150k edges. Why shouldn't this 
> run in near linear or n log n time, where n is number of edges. Do I have to 
> do something to the data structure first? 
> 
> I realize that's not actually THAT long a time to wait for a result, but I 
> would have assumed that I can envision finding weakly connected components as 
> a relatively straightforward greedy algorithm walking along a path. 
> 
> iGraph 0.5.3, 32-bit python 2.6, Mac 10.7.3. 
> 
> Take care,
> BERNiE 
> 
> Dr Bernie Hogan
> Research Fellow, Oxford Internet Institute
> University of Oxford
> http://www.oii.ox.ac.uk/people/hogan/
> 
> 
> 
> _______________________________________________
> igraph-help mailing list
> address@hidden (mailto:address@hidden)
> https://lists.nongnu.org/mailman/listinfo/igraph-help