[SciPy-User] Graph connect components and sparse matrices

Gael Varoquaux gael.varoquaux@normalesup....
Wed Nov 18 07:46:13 CST 2009


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.

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.

Gaël


More information about the SciPy-User mailing list