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

[Randall Morgan]

If I recall correctly:

A vertex can be thought of as a corner while an edge is a line segment
connecting to a vertex at both ends. Basically, a vertex is the point at
either end of an edge. Every edge should have two vertex and a vertex may
be shared by one or more edges.

Anyone know differently?




On Sun, Jul 6, 2014 at 8:48 AM, 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.
>
> > 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.
>
> 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?)
>
> 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).
>
> 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.
>
> 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).
>
> > 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.
>
> 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!
>
> 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.
>
> Very curious regards,
> Tobi
>
> --
> "There's an old saying: Don't change anything... ever!" -- Mr. Monk
>
>
> ------------------------------------------------------------------------------
> Open source business process management suite built on Java and Eclipse
> Turn processes into business applications with Bonita BPM Community Edition
> Quickly connect people, data, and systems into organized workflows
> Winner of BOSSIE, CODIE, OW2 and Gartner awards
> http://p.sf.net/sfu/Bonitasoft
> _______________________________________________
> Gambas-user mailing list
> Gambas-user at lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/gambas-user
>



-- 
If you ask me if it can be done. The answer is YES, it can always be done.
The correct questions however are... What will it cost, and how long will
it take?