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

[Tobias Boege]

On Mon, 07 Jul 2014, B Bruen wrote:
> > As I said, this g-node thing is not quite kosher to me because we developed
> > graph theory differently; I haven't seen your way anywhere yet. Interesting
> > though!
> The g-node thing came from a conversation with a mathematician some years ago.  It was a long discussion that could possibly be summarised as given G = (V, E) or G = ( {vertices}, {edges} ) thus G = ( V1, ... Vn, E1,...En ). Thus from the point of view of implementing a graph structure it could be done (again pseudocode) as 
>   Dim G as Variant[] 
> or should we want a generalised graph object, (say to ensure it has both internal and external "identifier" properties)
>   Dim G as g-node[]
> The g-node would be virtual and each instance would be either a Vertice or an Edge.  It just gets away from having to delineate, in the graph class, between Vertices and Edges.
>  

The Wikipedia "Edge graph" article you gave me says there are algorithms to
transform an edge graph into at least the connected parts of the original
graph - if I understood it right. So we can convert (as far as we can expect
it to work) between the "normal" graph and the edge graph for applications
that need this perspective. Methinks most applications won't; and for the
stuff I've seen so far, the simple graph definition suffices.

This makes me want to defer this topic to a later point when we have at
least one Graph class ready and can talk specifically about what it needs to
do the conversion or implement "more arcane" graphs.

> Again, all these are just thoughts. I am not trying to urge adoption.
> 

It's fine. I wanted to know if I have overlooked any applications and there
apparently are for the things you put forward. But I see no (easy) way to
support them all in just a single Graph class (+ related classes).

We keep these generalisations and advanced topics in mind but for now, one
point I can and want readily apply is: in your opinion, it would be better
to address vertices by Strings, in a human-readable form, not just integers,
right? I'm still torn.

I will make the Graph act like a Collection, i.e. once you have associated a
value to an ID, that ID is not changed by other operations on the Graph. You
had a point there; everything else hardly bearable for the programmer.
However, I want to use Integers as IDs because they are easier to store and
sort and abstract enough for the job.

If you want to associate more human-readable names with your vertices, I
think you can easily achieve it by having a Collection asscoaite your names
with the numerical IDs. In fact that's what I'd do in the Graph internals if
I was to offer String IDs.

Regards,
Tobi

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