# [Scipy-tickets] [SciPy] #1057: sparse matrix graph algorithms

SciPy Trac scipy-tickets@scipy....
Sun Jul 4 03:35:21 CDT 2010

```#1057: sparse matrix graph algorithms
--------------------------+-------------------------------------------------
Reporter:  rc            |       Owner:  wnbell
Type:  enhancement   |      Status:  needs_review
Priority:  normal        |   Milestone:  Unscheduled
Component:  scipy.sparse  |     Version:  devel
Keywords:                |
--------------------------+-------------------------------------------------

Comment(by GaelVaroquaux):

> Sure, I can do one better!  Here is some code with references in the
docstring:
>
>

Looks very cool. But I wonder if it solves the problem we are trying to
solve. I have the feeling that it works to label the connected regions of
a 2D array considered as an image. The algorithm that this ticket is about
tries to find connected subgraphs of an arbitrary graph, given by its
adjacency matrix. As an example, the following matrix:

{{{
a = np.array([[1, 0, 0, 1],
[0, 1, 0, 0],
[0, 0, 1, 0],
[1, 0, 0, 1]])
}}}

Has three connect components, comprising nodes ([0, 3], [1], [2])

I have the feeling that your algorithm is a replacement for
ndimage.labels, in the 2D case.

Maybe it would be worth special-casing ndimage.labels to use it in 2D. I
would actually be interested in a 3D version of it :)

--
Ticket URL: <http://projects.scipy.org/scipy/ticket/1057#comment:10>
SciPy <http://www.scipy.org>
SciPy is open-source software for mathematics, science, and engineering.
```