[Numpy-discussion] Graphs in numarray?

Magnus Lie Hetland magnus at hetland.org
Thu Apr 18 07:55:19 CDT 2002


Perry Greenfield <perry at stsci.edu>:
[snip]
> First of all, it may make sense, but I should say a few words about
> what scale sizes make sense.
[snip]
> So if you are working with much smaller arrays than 10K, you won't
> see total execution time decrease much

In relation to what? Using dictionaries etc? Using the array module?
[snip]
> 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.

Hm. If you need 10000 elements before numarray pays off, I'm starting
to wonder if I can use it for anything at all. :I

> (This particular issue also makes me wonder if numarray would
> ever be a suitable substitute for the existing array module).

Indeed.

> What size graphs are you most concerned about as far as speed goes?

I'm not sure. A wide range, I should imagine. But with only 100 nodes,
I'll get 10000 entries in the adjacency matrix, so perhaps it's
worthwile anyway?

> > 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. 

Yes, I realise that.

> 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.

That's an interesting idea, although I don't quite see how it would
help in the case of adjacency matrices. (You'd still need at least one
n**2 size matrix for n nodes, wouldn't you -- i.e. the index array...
Right?)

> 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.

No - no problem.

Basically, I'm looking for a platform to implement graph algorithms
that doesn't necessitate too many installed packages etc. numarray
seemed promising since it's a candidate for inclusion in the standard
library. I guess I'll just have to do some timing experiments...

> Perry

--
Magnus Lie Hetland                                  The Anygui Project
http://hetland.org                                  http://anygui.org




More information about the Numpy-discussion mailing list