[SciPy-Dev] scipy.sparse.csgraph merged

[Zachary Pincus]

On May 7, 2012, at 2:47 PM, Stéfan van der Walt wrote:
> On Mon, May 7, 2012 at 9:03 AM, Ralf Gommers
> <ralf.gommers at googlemail.com> wrote:
>> I finally merged https://github.com/scipy/scipy/pull/119, the sparse graph
>> algorithms module written by Jake Vanderplas. This will certainly by one of
>> the highlights of the 0.11 release (which shouldn't be too far off). Thanks
>> again to Jake for all the work he put in.
> 
> What a great pull request discussion and resulting changeset!  Kudos
> to Jake, Ralf, Dan and Pauli for seeing it through.
> 
> I'm curious to see how this compares to the N-d minimum cost path code
> in scikits-image:
> 
> https://github.com/scikits-image/scikits-image/blob/master/skimage/graph/_mcp.pyx

Oh great, that's phenomenal to see in scipy! Fantastic stuff.

The stuff in skimage is (essentially) Dijkstra's algorithm (on top of a binary heap, if I recall), for dense arrays and with some image-specific niceties (the graph connectivity is determined from a set of offsets that can be applied to any position in the array to find the "successor" nodes, and the edge weights can be determined in ways that make geodesic sense -- e.g. taking into account that diagonal "steps" are longer than axial ones).

So the algorithms in skimage make most sense for dense matrices with some sort of spatial ordering, though they need not be "images" per se.

Zach