Hi, I have a need to represent a directed graph in XoTcl.
'-childof' functionality seems to work well to represent trees. Unless I misunderstand, it seems this will force an class-object to belong to a single parent (1-to-many relationship). Is there a way to represent multiple parents (many-to-many relationship) without making multiple copies of nodes along the way?
Any help is appreciated.
thanks, -shishir
Hello!
Using nested objects to represent graphs could be good solution if you do not plan to move objects (change graph connection after creating). Consider that the "rename" method create new objects by copy (see some old messages in this mailing group)
The standard approach is using association as reference. The biggest problem is synchronizing references (but there are also standard solution for this problem from another languages)
Class Node Node n1 Node n2 Node n2 n2 set parent n1 # use list to store N side of association n3 set children [list n1 n2]
You can design same helper methods, parameters or even slots to manage it.
# using nested objects
Class Node Node parent Node parent::child_for_ever
Using nested objects is good because of simply object lifetime management. I prefer nested objects when I want to have some control about destroying groups of objects.
parent destroy # all children were destroyed too
Artur
Hi, I have a need to represent a directed graph in XoTcl.
'-childof' functionality seems to work well to represent trees. Unless I misunderstand, it seems this will force an class-object to belong to a single parent (1-to-many relationship). Is there a way to represent multiple parents (many-to-many relationship) without making multiple copies of nodes along the way?
Any help is appreciated.
thanks,
-shishir
Xotcl mailing list Xotcl@alice.wu-wien.ac.at http://alice.wu-wien.ac.at/mailman/listinfo/xotcl
Shishir Ramam schrieb:
Hi, I have a need to represent a directed graph in XoTcl.
Here are two small examples for representing graphs
In version one, edges are lists of references to nodes stored as attributes of nodes. By specifying "-multivalued true", it is possible to "add" or "delete" elements from the list. By using "-type Node" the code ensures, that only instances of Node may be added to the list, otherwise an error is thrown.
Class Node -slots { Attribute connects_to -multivalued true -type Node }
Node n1 Node n2 Node n3
n1 connects_to add n2 n1 connects_to add n3
puts [n1 connects_to]
A "destroy" of a nodes automatically destroys the edges as well, by refining the destroy method, one could as well destroy the referenced edges (similar to aggregation (nesting objects), but one has to be care about cyclical edges.
Another approach is to define Edges as objects which makes it possible to provide methods for Edges and to store attributes in it.
Class Edge -slots { Attribute from -type Node Attribute to -type Node }
Edge e1 -from n1 -to n2 Edge e2 -from n1 -to n3
Simarly as above, when a dynamic graph is to be maintained, the destroy method of Node should care about deleting references in Edges to ensure referencial integrity. The easiest way is to check in the destroy method of Node all Edges with [Edge info instances], if their "form" or "to" attributes contain the node. One could as well build an index to make this operation faster for large graph via a constructor of Edge, which maintains e.g. a list of referenced edges per node (e.g. via multivalued attribute "references", similar to approach 1)
-gustaf neumann
Thanks Gustaf and Artur!
Not sure if this should be considered expected behaviour - but does the type have to be defined before declaration? This simple script illustrates the issue - see the last couple of attempts.
Class Base -slots { Attribute connects_to -multivalued true -type Base } Class DerivedA -superclass Base -slots { Attribute connects_to -multivalued true -type DerivedB } Class DerivedB -superclass Base -slots { Attribute connects_to -multivalued true -type DerivedA }
Base b DerivedA da DerivedB db
b connects_to add da b connects_to add db
db connects_to add b
can't set "connects_to": b is not of type DerivedA << This should be
expected. all A-ok.
db connects_to add da da connects_to add b
can't set "connects_to": bad class "DerivedB": must be alnum, alpha,
ascii, control, boolean, digit, double, false, grap h, integer, lower, print, punct, space, true, upper, wordchar, or xdigit
da connects_to add db
can't set "connects_to": bad class "DerivedB": must be alnum, alpha,
ascii, control, boolean, digit, double, false, grap h, integer, lower, print, punct, space, true, upper, wordchar, or xdigit
On Nov 7, 2007 12:06 AM, Gustaf Neumann neumann@wu-wien.ac.at wrote:
Shishir Ramam schrieb:
Hi, I have a need to represent a directed graph in XoTcl.
Here are two small examples for representing graphs
In version one, edges are lists of references to nodes stored as attributes of nodes. By specifying "-multivalued true", it is possible to "add" or "delete" elements from the list. By using "-type Node" the code ensures, that only instances of Node may be added to the list, otherwise an error is thrown.
Class Node -slots { Attribute connects_to -multivalued true -type Node }
Node n1 Node n2 Node n3
n1 connects_to add n2 n1 connects_to add n3
puts [n1 connects_to]
A "destroy" of a nodes automatically destroys the edges as well, by refining the destroy method, one could as well destroy the referenced edges (similar to aggregation (nesting objects), but one has to be care about cyclical edges.
Another approach is to define Edges as objects which makes it possible to provide methods for Edges and to store attributes in it.
Class Edge -slots { Attribute from -type Node Attribute to -type Node }
Edge e1 -from n1 -to n2 Edge e2 -from n1 -to n3
Simarly as above, when a dynamic graph is to be maintained, the destroy method of Node should care about deleting references in Edges to ensure referencial integrity. The easiest way is to check in the destroy method of Node all Edges with [Edge info instances], if their "form" or "to" attributes contain the node. One could as well build an index to make this operation faster for large graph via a constructor of Edge, which maintains e.g. a list of referenced edges per node (e.g. via multivalued attribute "references", similar to approach 1)
-gustaf neumann
Shishir Ramam schrieb:
Not sure if this should be considered expected behaviour - but does the type have to be defined before declaration?
yes, the checking predicate is determined currently at definition time; if the specified "type" is not an existing class, the checker uses the "string is ..." as test method, therefore the error message.
All checking is in tcl, so it can be redefined, if you want (see method check_single_value of ::xotcl::Attribute in predefined.xotcl).
However, you can define also the slots after the class is defined:
Class DerivedA -superclass Base Class DerivedB -superclass Base
DerivedA slots { Attribute connects_to -multivalued true -type DerivedB } DerivedB slots { Attribute connects_to -multivalued true -type DerivedA }
This will work out of the box....
best regards
-gustaf neumann
-
Artur Trzewik -
Gustaf Neumann -
Shishir Ramam