[SciPy-User] Graph connect components and sparse matrices

Robert Cimrman cimrman3@ntc.zcu...
Wed Nov 18 08:03:43 CST 2009


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?

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

r.



More information about the SciPy-User mailing list