Re: Adjacency Matrix Library Project for Google Summer of Code

[Jordi Gutiérrez Hermoso]

On Sun, 2014-03-02 at 16:52 -0700, David Spies wrote:
> I just pulled Octave from the mercurial repository and I noticed the
> message about Google Summer of Code. I'm very interested in
> participating.

Having seen your involvement in the bug tracker for some time, I must
say I'm cautiously optimistic about your application.

> Particularly, I would really like to work on building a library of
> sparse matrix operations tailored towards graph operations on
> adjacency matrices (including directed, undirected, weighted, and
> unweighted graphs).

The thing is, I don't think Octave's sparse matrices are particularly
well-suited for graph theory work. They're ok, I guess, but
compressed-column sparse is intended for making sparse matrix
arithmetic fast, not so much for representing adjacency matrices. I
know that some graph-theoretical algorithms do rely on algebraic
properties of the adjacency matrix, like its spectrum, but for many
others (e.g. a simple breadth-first or depth-first search), the
adjacency matrix is clunky.

> I imagine the library itself would mostly be written in octave code,
> but I would still frequently need to work in C++ to add or improve
> support for the underlying sparse matrix operations the library
> would require.

For your GSoC application, I would like to see some significant
samples of C++ code very soon, since I expect you will be unable to
avoid C++ for this project.

> Would this be a suitable project?

Yes, it sounds like a meaty project that will help you getting
involved with Octave development.

- Jordi G. H.