On Fri, 4 Jul 2014 13:23:41 +0200
Tobias Boege <[email protected]> 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 <[email protected]>
------------------------------------------------------------------------------
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
[email protected]
https://lists.sourceforge.net/lists/listinfo/gambas-user
