[Xotcl] representing graphs in xotcl...

[Gustaf Neumann]

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