D graph library

[Joseph Rushton Wakeling]

On 05/08/2013 05:48 PM, Craig Dillabaugh wrote:
> I wonder if it is a good idea to try and guarantee specific times
> for operations like these in all case, or rather support multiple
> back-end representations that make specific operations more or
> less efficient. Then document the trade offs. Like linked-list
> vs. vector for storing a list.

Yes, in practice you'll probably want different backends which offer different
performance priorities.

> I don't really know what the state-of-the-art is for graph
> representations, but isn't in normally either an adjacency list
> or matrix used to represent the graph. Adjacency lists allow the
> O(d) neighbours() access you want, while the matrix
> representation is O(n). But if you want an isNeighbour(A,B)
> function, then the matrix rep. can do that in O(1), but only O(d)
> for your adjacency list.

Indeed, and there is also a tradeoff with respect to storage.

For one problem I worked on a few years back (it's the one described in my
"dregs" library on GitHub), I found the best representation was just an array of
link pairs.  It would have been very nasty from the point of view of a
neighbours() function, but I didn't need that functionality.

We'll probably also need to look into effective sparse matrix representations as
the adjacency matrix is usually extremely sparse for most actual graphs.

> Perhaps there is some hybrid representation out there that is
> pretty good at everything.

Well, when I said O(1) for some of those cases, I was thinking of something that
would return a lazily-evaluated range.  So, you do the calculation only when you
iterate across what has been returned, not when you return the value.

By contrast igraph_neighbors() is given as O(d), but I'm fairly sure that's less
to do with the underlying data structure than that (AFAICS) they actually
construct an array of length d and write values into it.

What you'd like to see in our case is that neighbors() would return a
RandomAccessRange which is O(1) to create, and for which opIndex(), popFront()
and popBack() are all O(1) to call.