[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:
 >
 >
 http://dip.sun.ac.za/~stefan/code/lulu.git/?p=stefan/lulu.git;a=blob;f=lulu/ccomp.pyx;h=6bbb73bc22f0865a09e4808d121baaacc3d81404;hb=HEAD

 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.


More information about the Scipy-tickets mailing list