[Numpy-discussion] Graphs in numarray?

[Perry Greenfield]

Hi Magnus,

On Behalf Of Magnus Lie Hetland

> 
> I'm looking at various ways of implementing graphs in Python (beyond
> simple dict-based stuff -- more performance is needed). kjbuckets
> looks like a nice alternative, as does the Boost Graph Library (not
> sure how easy it is to use with Boost.Python) but if numarray is to
> become a part of the standard library, it could be beneficial to use
> that...
> 
> For dense graphs, it makes sense to use an adjacency matrix directly
> in numarray, I should think. (I haven't implemented many graph
> algorithms with ufuncs yet, but it seems doable...) For sparse graphs
> I guess some sort of sparse array implementation would be useful,
> although the archives indicate that creating such a thing isn't a core
> part of the numarray project.
> 
First of all, it may make sense, but I should say a few words about
what scale sizes make sense. Currently numarray is implemented mostly
in Python (excepting the very low level, very simple C functions
that do the computational and indexing loops. This means it currently
has a pretty sizable overhead to set up an array operation (I'm
guessing an order of magnitude slower than Numeric). Once set up,
it generally is pretty fast. So it is pretty good for very large
data sets. Very lousy for very small ones. We haven't measured
efficiency lately (we are deferring optimization until we have all
the major functionality present first), but I wouldn't be at all
surprised to find that the set up time can be equal to the time
to actually process ~10,000-20,000 elements (i.e., the time spent per
element for a 10K array is roughly half that for much larger arrays.

So if you are working with much smaller arrays than 10K, you won't
see total execution time decrease much (it was already spending 
half its time in setup, which doesn't change). We would like
to reduce this size threshhold in the future, either by optimizing the
Python code, or moving some of it into C. This optimization wouldn't
be for at least a couple more months; we have more urgent features
to deal with. I doubt that we will ever surpass the current Numeric
in its performance on small arrays (though who knows, perhaps we 
can come close).

> What do you think -- is it reasonable to use numarray for graph
> algorithms? Perhaps an additional module with standard graph
> algorithms would be interesting? (I'm sure I could contribute some if
> there is any interest...)
> 
Before I go further, I need to find out if the preceeding has made
you gasp in horror or if the timescale is too slow for you to
accept. (This particular issue also makes me wonder if numarray would
ever be a suitable substitute for the existing array module).
What size graphs are you most concerned about as far as speed goes?

> And -- is there any chance of getting sparse matrices in numarray?
> 
Since talk is cheap, yes :-). But I doubt it would be in the "core"
and some thought would have to be given to how best to represent them.
In one sense, since the underlying storage is different than numarray
assumes for all its arrays, sparse arrays don't really share the
same underlying C machinery very well. While it certainly would be
possible to devise a class with the same interface as numarray objects,
the implementation may have to be completely different. 

On the other hand, since numarray has much better support for index
arrays, i.e., an array of indices that may be used to index another
array of values,  index array(s), value array pair may itself serve
as a storage model for sparse arrays. One still needs to implement
ufuncs and other functions (including simple things like indexing)
using different machinery. It is something that would be nice to have,
but I can't say when we would get around to it and don't want to
raise hopes about how quickly it would appear.

Perry