[Gambas-user] RFC: How to identify vertices and edges in a Graph class?

[Tobias Boege]

Hi list,

I'm currently (well, I'll try to continue with it tomorrow) implementing an
abstract Graph class in gb.data. And by "abstract", I mean that I will just
specify the interface of Graph classes, so that concrete implementations, of
which there are plenty possibilities, are varible behind that consistent
interface. (Of course, after the interface is there, you get at least two
concrete implementations delivered for free along with gb.data.) This should
encourage you to model your problems as your own customised Graph classes
and maybe you can then already solve them with a standard algorithm, like
Dijkstra.

To this end, and for performance reasons, we cannot/don't want to have real
Vertex or Edge classes but use virtual objects instead.[*]

I'm struggling with the way we would address vertices and edges here. The
easiest way would be to have some integer ID (I think we all agree on this).
But what shall happen when you have vertices 1,2,3 and remove vertex 2?
Shall 3 become the new 2? Shall 2 be taken up by the next inserted vertex?
Shall it remain unused forever?

Try to put yourselves in my situation, too: if the graph above would be
implemented as a 3*3 adjacency matrix, if row and column 2 (counting from 1)
are deleted, actually 3 would become the new 2. This is very easy for me as
a programmer but may be bad for you as the user because the way you address
things changes behind your back.

What I could do, OTOH, is to have an internal translation array so that you
can keep using the vertex ID 3 which is mapped to index 2 (still counting
from 1) of the adjacency matrix. This would mean an additional indirection
every time...

I will leave quite some aspects of the Graph class "implementation defined"
like the ability to delete vertices or create edges, etc. but this is a
point that I *have* to specify.

As for the edges, would you prefer an edge ID similar to the vertex ones or
that edges are identified by the source and destination vertex IDs they
connect? The first possibility would be the most generic but difficult to
implement. The second way would require that we have that translation array
for vertex IDs.

I would like to hear your opinions (and alternatives) on this matter; if you
have any application in mind that would need it one or the other way.

Regards,
Tobi

[*] Imagine that you have a huge data structure which you just want to
    *interpret* as a Graph, i.e. your Graph is defined implicitly by some
    other data. It could potentially *waste* tremendous amounts of memory
    if you were required to create real Vertex and Edges objects instead of
    just forward requests from the Graph interface to your backing data.

-- 
"There's an old saying: Don't change anything... ever!" -- Mr. Monk