[SciPy-User] Graph connect components and sparse matrices

Robert Cimrman cimrman3@ntc.zcu...
Wed Nov 18 08:24:37 CST 2009


Gael Varoquaux wrote:
> 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.

OK, I will give it a shot (soon), unless someone jumps in with a better solution.

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

I see. BTW. putting a code into scipy somewhat alleviates the maintenance burden ;)

cheers,
r.



More information about the SciPy-User mailing list