[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] decompose time

From: Tamás Nepusz
Subject: Re: [igraph] decompose time
Date: Fri, 20 Apr 2012 00:27:19 +0200

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 

cl = graph.clusters()

Then you can get the membership vector as follows:


or extract the giant cluster:


or any other cluster by its index:



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,
> 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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]