D graph library

[Craig Dillabaugh]

> Then for nodes/vertices you'd want to define a number of 
> properties:
>
>        neighbours   /* OK, OK, neighbors.  Purely in order to 
> save keystroke
>                        time for programmers.  Returns a 
> RandomAccessRange to
>                        the collection of nodes that the given 
> node links to.
>                        For directed graphs you might want to 
> add a template
>                        qualifier of "out" (default) or "in" to 
> allow getting
>                        neighbours that this node points to, or 
> neighbours that
>                        point to this node.  Should be O(1) [but 
> maybe needs to
>                        be O(d)?] */
>
>        edges        /* Returns RandomAccessRange of edges that 
> connect to this
>                        node.  For a directed graph you might 
> want again a
>                        template qualifier of "out" (default), 
> "in" or "all".
>                        Should be O(1) [but maybe needs to be 
> O(d)?] */
>

According to The Queen, it is neighbours :o) I am Canadian, so
which spelling I use depends on how I am feeling on a particular
day.

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.

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.

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

Craig