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
