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

SciPy Trac scipy-tickets@scipy....
Sun Jul 4 02:15:30 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 stefan):

 Replying to [comment:8 rc]:
 > Stefan, do you have reference for that O(n) algorithm?
 >
 > The code is based on a function that was laying on my disk for quite a
 time, so I am not sure about its order. A quick look suggests that it is
 proportional to the number of nonzeros, which is in my field (finite
 element simulations) O(n), but can be with a non-negligible constant. So
 maybe we can do better, if the algorithm can be adapted to CSR kind of
 storage. Anyway it is quick enough for me (493039x493039 with 12977875
 nonzeros in 0.2 s) :-} (bad argument, yeah).

 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

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


More information about the Scipy-tickets mailing list