Wednesday, June 01, 2005

GraphTalk and the metalogy


GraphTalk was designed several years ago to do easy the CASE tool building.

However GraphTalk is more generally a modeling environment.

To illustrate GraphTalk, I choose a short example on metalogy (i.e. something about meta).

Hypergraph:


The main concept in GraphTalk is the concept of hypergraph:

A hypergraph H can be defined as a pair (V, E), where V is a set of vertices, and E is a set of hyperedges between the vertices. Each hyperedge is a set of vertices: E = {{u, v, ...} ∈ 2V}. (Hyperedges are undirected.)

To clarify with a graph:
A graph G can be defined as a pair (V,E), where V is a set of vertices, and E is a set of edges between the vertices E = {(u,v) | u, v ∈ V}. If the graph is undirected, the adjacency relation defined by the edges is symmetric, or E = {{u,v} | u, v ∈ V} (sets of vertices rather than ordered pairs).


GraphTalk:

A GraphTalk program (or GraphTalk metamodel) is a hypergraph itself. The metamodel of GraphTalk is a Graphtalk program too... But let start with easy things.

Entity (always abstract) is a metaclass with hyper, graph, node and link as sub-class (abstract or not; an abstract class cannot be instantiated).
What a surprise, a graph is a set of nodes and links.

A node can be Unique or not (a Unique node share Public properties for all copies of the node in the hypergraph. Private properties are local to each copy of the node).
We can consider a link between two nodes as a Private property of each node.

Hypergraph is the container for the coherency of all elements according to the modeling rules:

  • A GraphTalk metamodel respects the programming rules of the meta of GraphTalk.
  • A hypergraph instance respects the rules defined in the relevant GraphTalk metamodel.

The original goal of the GraphTalk project was to avoid as possible all procedural programming. So a lot of constraint exists in the GraphTalk environment.
For example, for rules around links:

  • Oriented or not
  • Cardinality
  • Implication
  • Exclusion

A property of a class (hyper, graph, node, link) can have a simple or a multiple value.

The set of property is various:

  • String, boolean, float, number, date, binary, subset, etc..
  • SubNode
  • SubGraph
  • Structured text (according a BNF)
  • Association
  • Record of properties (allows to have built type)
  • Method

To customize or to increase the capacity of a hypergraph editor generated with GraphTalk, each metanode (hyper, graph, node, link, property, actions, etc..) has the capacity to have an extended behavior with triggers according a specific semantic.

The original goal of GraphTalk was to generate graphs editors for CASE tool, so the display part is important.
It is possible for a node, a link or a graph to define, with a shape editor, the layout of the node, link, graph, without any specific code.
To manage the interaction between GraphTalk and the user, it is possible to define (graphically) all the GUI stuff (items menus, pop-up menus, etc ...).

Context of the GraphTalk example:

The example is about metalogy.

The purpose is to talk about the meta world, the technologies, the companies involved in this world, the connections between ideas and people.

We want classify metalogy in three axes:

  • the Actor axis:
    • 3 kinds of Actor:
      • R&D Lab
      • Software Editor
      • Software House
    • Relationship between Actors (Subsidiary, etc..)
    • Employee assignment to an Actor
  • the Project axis
    • What is the Actor at the origin of the meta thing
    • What reference to a Meta thing or to a Technology is announced by people at the origin of a Meta thing
  • the Technology axis
    • Meta
      • implemented with what kind of Development environment
      • Because the same Meta thing was in some case implemented with several Development environment (for example GraphTalk with C/C++, with InterLisp-D or with CLOS), to indicate the concerned version. We can see, the version property is a property of the link (Meta, Development environment)
    • Modeling
    • CASE tool
      • implemented with what kind of Meta and related to what kind of Modeling techniques
    • Development environment

  • For all concept, what is the birth date, the death date and a short description.

GraphTalk metamodel for the metalogy example:

A GraphTalk program is organized by abstraction level: semantic (Classes and Rules), properties of Classes, layout of Classes and Widgets layout.


Implementation of the semantic with GraphTalk:

It's easy to read and to understand this graph, as a Niam binary data model or a Sowa conceptual graph, but because for you perhaps it is the first time you look at a GraphTalk materials, I can explain this graph:

  • One abstract class of Entity "Super" (with an ellipse shape).

  • 3 abstract classes of Graph "Abstract" (with a diagram icon), Node "Abstract"(with an ellipse shape) and Link "Abtract" (with an large arrow shape).
  • Between these 3 classes and the Entity, 2 inheritance links (with a double-arrow).

  • An inheritance tree of classes of Links sub-classes of the Link "Abstract". The sub-classes are "Related to", "Subsidiary of", "At the origin of", "Implemented with", "Employee of" and "Reference to".

  • An inheritance tree of classes of Nodes sub-classes of the Node "Abstract". The sub-classes are "Actor", "Technology" and "Employee".

  • Each metanode (hyper, graph, node, link, property, actions, etc..) has a lot of slots and belongs inspectors to give value to these slots (for example to give the value "Yes" to the slot "Abstract".

  • The class of Graph "Actor" is composed (simple link with an arrow) of the classes of Node "Employee" and "Actor" and of the classes of Links "Employee of" and "Subsidiary"

  • An inheritance tree of classes of Nodes sub-classes of the Node "Actor". The sub-classes are "Research Lab", "Software Editor" and "Software House".

Example of inspectors on class of Node in a GraphTalk program:

  • The class of Graph "Technology" is composed(simple link with an arrow) of the class of Node "Technology" and of the classes of Links "Related to" and "Reference to" and "Implemented with".

  • An inheritance tree of classes of Nodes sub-classes of the abstract Node "Technology". The sub-classes are "Meta", "Modeling" and "Development Environment" and "CASE Tool".
  • The class of Graph "Project" is composed (simple link with an arrow) of the classes of Node "Meta" and "Actor"and of the class of Links "At the Origin of".

  • The class of Hyper is composed (simple link with an arrow) of the classes of Graph "Technology", "Project" and "Actor".

The Rules are defined like this:

Explanations for the Rules are:

  • An instance of the class of Node "Actor" can be connected from 0 to N instances of the class of Node "Meta" by one instance of the class of Link "At the Origin of".

  • An instance of the class of Node "Meta" can be connected from 0 to 1 instance of the class of Node "Actor" by one instance of the class of Link "At the Origin of".

  • An instance of the class of Node "Actor" can be connected from 0 to N instances of the class of Node "Actor" by one instance of the class of Link "Subsidiary of".

  • An instance of the class of Node "Meta" can be connected from 0 to N instances of the class of Node "Technology" by one instance of the class of Link "Reference to".

  • An instance of the class of Node "Technology" can be connected from 0 to N instances of the class of Node "Meta" by one instance of the class of Link "Reference to".

  • An instance of the class of Node "Actor" can be connected from 0 to N instances of the class of Node "Employee" by one instance of the class of Link "Employee of".

  • An instance of the class of Node "Employee" can be connected from 0 to 1 instance of the class of Node "Actor" by one instance of the class of Link "Employee of".

  • An instance of the class of Node "Meta" can be connected from 0 to N instances of the class of Node "Development environment" by one instance of the class of Link "Implemented with".

  • An instance of the class of Node "Development environment" can be connected from 0 to N instances of the class of Node "Meta" by one instance of the class of Link "Implemented with".

  • An instance of the class of Node "Meta" can be connected from 0 to N instances of the class of Node "CASE Tool" by one instance of the class of Link "Implemented with".

  • An instance of the class of Node "CASE Tool" can be connected from 0 to N instances of the class of Node "Meta" by one instance of the class of Link "Implemented with".

  • An instance of the class of Node "CASE Tool" can be connected from 0 to N instances of the class of Node "Modeling" by one instance of the class of Link "Related to".

  • An instance of the class of Node "Modeling" can be connected from 0 to N instances of the class of Node "CASE Tool" by one instance of the class of Link "Related to".

For the properties, the GraphTalk code is the following:

The abstract class of Entity "Super" has the properties "Creation" (with the type Date), "Update" (with the type Date) and "Description" (with the type String).

Each instance of sub-classes of this class of Entity belongs the same properties thru inheritance (multiple inheritance is supported natively in GraphTalk).

Instances of the class of Link "Implemented with" have the property "Version" (with the type String).

Instances of the class of Node "Meta" have the public properties "Birth" and "Death" (with the type Date). They have the public property "Author" (with the type Association) and the allowed values of this properties are instances of class of Nodes "Actor" and "Employee".


In this simple example, I didn't take time to invest in the Widget aspect. We'll use the default GraphTalk's Widget behavior.

However, we 'll take few minutes on the layout of Nodes and Links to have a more usable generated hypergraph editor.

For the Layout of Nodes and Links:

More precisely for a Node:

I draw an ellipse with the shape editor and I specify the display of the properties "Label" and "Class" for the Class of Node "Actor".

And for the links :

For the class of Link "Abstract", and for all the sub-classes by inheritance, I specify the display of the property "Role" in the middle of the drawing of the link.


What about the generated hypergraph editor?

We have an hypergraph editor with 3 graphs editors ("Technology", "Actor" and "Project"), sharing several class of Nodes and with some associations between nodes in graphs instances of several class:

The "Project" graph editor:


The "Actor" graph editor:

The "Technology" graph editor:


A general Search allows to access easily to the contents of an hypergraph, metamodel or model:

If we want to refine the Search, a good solution is to use GQL (GraphTalk Query Language).

GQL code example:

  • Goal: to find all nodes instances of Meta and in which graph (Name and Class) we can find them.
    • Code: SELECT DISTINCT N.Label Meta, G.Name Graph,G.Class Editor FROM Hyper.Nodes N,N.Graph G WHERE N.Class='Meta' ORDER BY 3,2,1
  • Goal: to find all nodes linked with instances of Meta and in which class of link.
    • Code: SELECT DISTINCT D.Label Linked, D.Class Kind,L.Class Link,N.Label Meta FROM Hyper.Graphs G,G.Nodes N,N.--L--D WHERE N.Class='Meta' ORDER BY 3, 2,1,4

  • Goal: to find the company where are employed author of Meta referenced by another Meta
    • Code: SELECT DISTINCT N.Label Meta,D.Label Reference, A.Label Author,C.Label Company FROM Hyper.Nodes N,N.->-L->D,D.Author A, A.->-E->-C
      WHERE L.Class='Reference to' ORDER BY 1,2,3,4


For this blog, statistics are:
  • 2 hours to imagine the contents of the blog and the example with several iterations.
  • 1 hour to use GraphTalk to program the example and to instantiate it
  • 3 hours to use the Google products like blogger and Hello (used to publish images inside the blog).