[SciPy-User] Graph connect components and sparse matrices

[Gael Varoquaux]

On Wed, Nov 18, 2009 at 03:03:43PM +0100, Robert Cimrman wrote:
> Hi Gael,

> Gael Varoquaux wrote:
> > Hi there,

> > I would like to list the connect components of a graph (or a sparse
> > matrix, same thing). I know of course of the bread-first traversal, as
> > implemented eg in networkX, to find the connect components. However, I
> > have a feeling that sparse linear algebra must be performing such
> > searches, to decompose sparse matrices in blocks. I'd love to piggy back
> > on such implementations, rather than code and maintain a C or cython
> > version of breadth-first graph traversal.

> I have a function in C (as a part of sfepy), that does that. But as it
> might be useful for more people, what about putting it scipy
> sparsetools?

I think it would be very useful. I would actually include it in the
scipy.sparse namespace too.

> > Any idea how I could squeeze the information out of the sparse linear
> > algebra that we carry around with scipy? I thought about using arpack to
> > get the largest eigen vectors of the transition matrix, but that was a
> > stupid idea, as (AFAIK) it will not partition my graph in connect
> > components, but only tell me how many connect components I have.

> Getting eigenvectors is imho more costly that the graph search, no?

Well, getting the largest eigenvector of the transition matrix is in
o(n), using arpack, AFAIK. So the cost is similar, and on one side we
have optimized C code, and on the other side I only had Python code (or C
code that I don't want to maintain). In addition, as I am doing diffusion
maps, I needed to call arpack anyhow.

Cheers,

Gaël