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

[B Bruen]

On Fri, 4 Jul 2014 13:23:41 +0200
Tobias Boege <taboege at ...626...> wrote:

> 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.
> ...

Hi Tobi,
Some thoughts.

A directed graph is more fundamental than an undirected graph.  Consider the simplest directed graph, an ordered list of two Vertices and one Edge.  (I'll avoid integer idenitifcations for ease of explanation,) We have nodes "A" and "B" which are Vertices and node "ab" which is the edge. Node "ab" allows a traversal from "A" to "B", there is no traversal permissable from "B" to "A".  In an undirected graph, the "ab" edge would somehow have to permit both the A->B traversal and the B->A traversal.  However, this could be implemented as a graph type property where creating the "ab" edge also creates the reverse "ba" edge.

The second point is somewhat more interesting.  In the above I used the term "node" deliberately.  Some of the more arcane bits of graph theory suggest or even require that Vertices and Edges are interchangeable.  That is, any Vertice can be considered as an Edge and any Edge can be considered as a Vertice.  To allow this, I think that there needs to be a "fundamental particle" approach to building a library such as yours.  This is based on:
"A graph is a set of Vertices each of which is connected to some number of other Vertices by a set of Edges"
"A graph is a set of Edges, each of which is connected to some number of other Edges by a set of Vertices"
Note, generally we think of an edge as something with a maximum of two connections, i.e. ends. But in fact mathematically and Edge could have any number of ends. That's hard to visualise using the normal "ball and string" image, but if you consider the edge "abc" as a ball with three (unterminated) strings "A","B" and "C" then it starts to become easier to imagine.
So, I think that the ultimate interface requires some fundamental particle, lets call it a g-node.  Internally the identifier of any g-node could as you say be an integer.  But it also needs some human understandable "identity" such as I have used in these descriptions.

Where does this get us? Going back to your example of deleting a Vertice and also considering the similar action of deleting an Edge.  To delete a Vertice, we need to both remove all the edges originating at that Vertice and to delete or "de-terminate" all the edges that terminate at that Vertice.  Deleting an edge involves "de-terminating" every vertice that is associated with that edge.

> But what shall happen when you have vertices 1,2,3 and remove vertex 2?
I presume that the set of g-nodes is {"1","2","3","1-2","2-3"} i.e. three vertices and two edges.  "Remove" "2" involves deleting the second g-node and  de-terminating the associated edges, i.e. the resultant set is {"1","3","1-",-3"}
> Shall 3 become the new 2? 
>From {"1","3","1-",-3"} I presume you mean "If the B vertice in the graph A-B-C is removed  then because the traversal A-C is specified then the graph should become A-C. In that case the dangling edges "1-" and "-3" should be converted to a single "1-3" edge, i.e. the set becomes {"1","3","1-3"}.  This is a different action to that above, perhaps "Remove_with_snap".
> Shall 2 be taken up by the next inserted vertex?
>From {"1","3","1-",-3"} I presume you mean "If I then insert a new g-node ("4") then it should automatically pop into the graph where "2" used to be." I don't think so at all. 
> Shall it remain unused forever?
Given the above, yes. Or in fact it has just disappeared.

What about all those dangling edges? Well, given that mathematically an edge with only one end is feasible they can be left as is. If the particular application requires that edges must have (at least) two ends, then we need a method to "clean" the graph that would remove dangling edges.  

So ...

Class g-node                                                    ' attempts to generalise any Vertice or Edge in a directed graph
  Property Key,Identifier as String
  Property Type As String                                 ' validated "In ["V","E"]
  Property OriginatingAssociations As Array    ' holds the list of g-nodes where this g-node is the origin
  Property TerminatingAssociations As Array  ' holds the list of g-nodes where this g-node is the destination

Class graph
  Property Nodes as Array                              ' holds the set of nodes in the graph
  Function Remove(Key as String) As graph  ' remove a node and leave all associations dangling
  Function RemoveWithSnap(Key as String) as graph
  Function Clean() as graph
  etc

Is this type of thinking consistent with yours?

regards
Bruce
-- 
B Bruen <bbruen at ...2308...>