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

[B Bruen]

On Sun, 6 Jul 2014 16:48:47 +0200
Tobias Boege <taboege at ...626...> wrote:

> On Sun, 06 Jul 2014, B Bruen wrote:
> > 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.
> > 
> 
> That's what I was going to do. The Graph constructor will take an Optional
> Directed As Boolean. The implementation will need to worry about what this
> property effects.
Indeed, my thoughts exactly.
> 
> > 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.
> 
> That's interesting! Can you put your definition mathematically? Or suggest a
> book which develops graph theory this way? I fear otherwise I won't get the
> idea.
It comes from the hypergraph ideas.  See http://en.wikipedia.org/wiki/Hypergraph especially the second and third paragraphs.
> 
> What I call a graph is a pair of sets (V, E) where V are the vertices and E
> is a subset of V times V. So in fact, an edge has exactly one end. It cannot
> have zero ends nor two (like your edges could). (How many beginnings do your
> edges support anyway?)
Bit unsure of what you mean here?  I was using "end" to mean both the origin association(s) and the destination association(s). So to me an edge can only have >= 2 ends.  However, any "end" could be "unfilled" i.e. there is no vertice on it.
> 
> Vertices and edges are well distinguished in the above definition. Could you
> give me a pointer on where one needs to have vertices and edges to be
> interchangeable? At this point, interpreting a vertex as an edge doesn't
> make any sense to me (whereas an edge as a vertex seems ok).
Some information at http://en.wikipedia.org/wiki/Edge_graph

> 
> Wikipedia calls an extension of a graph where edges can connect any number
> of vertices (apparently any *positive* number) a "hypergraph" and I would
> personally stick to that naming, i.e. implement a graph like I defined above
> as the class Graph and later a Hypergraph class for those who want to work
> with those.
Ah! OK, I was thinking of the hypergraph as the basic structure and devolving (normal) graphs from that as a specialisation.

> 
> I don't think it would be a good idea to only implement Hypergraph and
> reduce Graph from it, be it just for performance reasons (to keep a single
> end point or a set of end points are two very different things when it comes
> to the implementation).
Again, OK.

> 
> > 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.
> > 
> 
> Actually, the numbers were intended to be the human understandable
> identities :-) But OK, we could also drop the numbers entirely (no
> need to have two different but equivalent and equivalently powerful
> indexing schemes, right?) and identify vertices by strings.
> 
> > 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".
> 
> Wait, wait, wait.
> 
> Basing on my definition of a graph above, I call a "path" a k-tuple of edges
> (e_1, e_2, ..., e_k) where the end point of e_i is the beginning of e_{i+1}
> for i=1,...,k-1.
> 
> Do you say that in your graph, my paths can also be your edges? Because
> A-B-C would be a path and you treat it like it would be a single g-node.
No I think a path is different from an edge. Perhaps nodes "A","B","C" connected by edges "ab" and "bc" could give rise to a path "A-B-C" (or "ab,bc" perhaps, in your k-tuple sense). 
> 
> My question "Shall 3 become the new 2" was actually meant a lot more
> low-level: if we identify vertices with numbers, what happens if one of
> those numbers is deleted? The options would be: it acts like an array, i.e.
> the greater numbers are shifted down, so that the vertex which was addressed
> by 3 before the removal will now be addressed as 2. Or it acts like a
> Collection, i.e. once an ID is chosen for a vertex, it will never change
> (unless explicitly requested by an operation on that particular vertex).
> 
> > > 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?
> > 
> 
> 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.
 
> 
> A major practical problem in your above snippet is that you rely on Array.
> We want to avoid any use of arrays because they need all the objects pre-
> allocated. I explained (hopefully understandable?) how this can waste lots
> of memory if your graph is defined implicitly by other data.
It was meant as pseudo-code, sorry I should have made that obvious. 
> 
> Very curious regards,
> Tobi
> 
Again, all these are just thoughts. I am not trying to urge adoption.

regards
Bruce

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