[SciPy-User] Graph connect components and sparse matrices

Gael Varoquaux gael.varoquaux@normalesup....
Thu Nov 19 10:09:56 CST 2009


On Thu, Nov 19, 2009 at 11:01:19AM -0500, Nathan Bell wrote:
> I think we should definitely include more graph algorithms in
> scipy.sparse.  The cost of extracting the same info via eigenvectors
> is high and the results are less trustworthy.

> We've implemented several such algorithms (like connected_components
> [1]) in PyAMG.  

I thought you might have. By the way, that thing (pyAMG) is just
fantastic).

> Since the code is organized in similar fashion to scipy.sparse it would
> make sense to transfer some or all of the functionality in pyamg.graph
> into scipy.sparse.graph or some such namespace.  

I'd love to see all of it, actually.

> I'd also like to add some reordering methods like RCM and nested
> bisection.

I am really interested in all that. I don't have time to contribute in
the short term, but in the long run (one to two years), I have a big
interest there.

I think moving these features in scipy would enable code sharing between
a lot of other libraries (pyAMG, networkX, sfepy, and probably other PDE
solvers). Beside, the nipy project has some graph algorithms for machine
learning and computer vision that use custom structures, and should move
to common structures in the long run, and maybe in a comon project (we
are thinking of the scikit learn).

Very exciting talk!

Gaël


More information about the SciPy-User mailing list