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.