Re: [igraph] Computing SCC on large graph

[Tamas Nepusz]

Hi,

Thanks for the feedback -- I have updated the implementation of
igraph_clusters_strong to use an adjacency list representation, and indeed it
is way faster now (on my machine, it now processes a BA random graph with
1 million nodes and 20 million edges in ~3 seconds).

All the best,
T.

On 05/11, Santiago Videla wrote:
> Hi,
> 
> FYI, I came back to this using both igraph for R and graph-tool [1], over
> the same graph and they took ~2s to compute SCC. So, I guess something is
> not working as expected in the python interface :) Please, let me know if I
> can help somehow to debug this.
> 
> Regards,
> 
> [1] http://graph-tool.skewed.de/
> 
> 
> On Tue, Apr 28, 2015 at 3:15 PM, Santiago Videla <address@hidden>
> wrote:
> 
> > Hi,
> >
> > Thanks for the reply. Just to let you know, it ended a few hours after I
> > sent my email, so I guess it was just hard to compute :)
> >
> > Regards,
> >
> > On Mon, Apr 27, 2015 at 9:31 PM, Gábor Csárdi <address@hidden>
> > wrote:
> >
> >> Hi, SCC is linear, so it should not take too long. I would try a smaller
> >> graph first, then a bit bigger one, etc. to see how it scales.
> >>
> >> But it is suspicious that something went wrong.
> >>
> >> G.
> >>
> >> On Mon, Apr 27, 2015 at 4:12 PM, Santiago Videla <
> >> address@hidden> wrote:
> >>
> >>> Hi all,
> >>>
> >>> I recently started to use igraph (from python) and after playing a bit
> >>> with it I loaded a directed graph with ~1.5 millions nodes and ~100
> >>> millions edges. I know there are cycles and I'd like to identify them all
> >>> (I believe that most of them are of the form A <-> B). I'm trying to
> >>> compute the SCC of the graph. I guess there are plenty of things that in
> >>> practice could have an impact on how the algorithm performs. But, does
> >>> anyone have experience computing SCC on a graph of similar scale? How long
> >>> (aprox) could it take? I ask because it has been running for 75 hours by
> >>> now, and the memory seems quite stable around 3.5GB (Intel Core i5 2.67GHz
> >>> - 16GB RAM).
> >>>
> >>> Do you think this is normal/expected? Should I just keep waiting?
> >>>
> >>> Regards,
> >>>
> >>> --
> >>> Santiago Videla
> >>> http://www.linkedin.com/in/svidela
> >>>
> >>> _______________________________________________
> >>> igraph-help mailing list
> >>> address@hidden
> >>> https://lists.nongnu.org/mailman/listinfo/igraph-help
> >>>
> >>>
> >>
> >> _______________________________________________
> >> igraph-help mailing list
> >> address@hidden
> >> https://lists.nongnu.org/mailman/listinfo/igraph-help
> >>
> >>
> >
> >
> > --
> > Santiago Videla
> > http://www.linkedin.com/in/svidela
> >
> 
> 
> 
> -- 
> Santiago Videla
> http://www.linkedin.com/in/svidela

> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help


-- 
T.