Untitled Document

Graph, CG and Ontology Drawing

Adil KABBAJ

In previous versions of Synergy, Khalid Rouane and the author developed and implemented a CG drawing editor (the first implementation was in C++ by Khalid in 1995 and the second was in Java by Adil in 1998).

In Amine, we are interested by a generic Graph Drawing Editor, that can be specialized in a CG Drawing Editor and in an Ontology Drawing Editor. Our previous CG Drawing editor was specific to CG and was a "quick" prototype.

Since version 4.0, Amine provides graph drawing possibilities: CG drawing editor, automatic CG drawing, ontology drawing editor and automatic drawing ontology.

This document describes the result of our work on the development and implementation of a generic Graph Drawing Editor and its specialization in CG and Ontology Drawing editors.

The basic principle behind the development of our generic graph drawing editor is to adopt the Model-View approach and to separate the model (the Graph as a logical structure) from the view that is used to draw the graph. Graphical information and graphic methods should not be included in the model (except for minimal graphic information that should be stored and loaded). Thus beside the Graph model, we should develop a graphical/visual view, called VisualGraph. We should develop also a Generic Graph Drawing Application (GGDA) with its GraphDrawFrame and GraphDrawPanel where the VisualGraph will be displayed and manipulated. The main frame of the GGDA is the GraphDrawFrame and the panel of this latter is the GraphDrawPanel where VisualGraph is to be drawn. A VisualGraph is associated to a Graph Structure; it constitutes a view of the Graph. Figure 1 presents the architecture of this generic application.

Of course the Generic Graph Model should not correspond to a specific graph; it should rather provides a generic specification of a graph (and VisualGraph should be defined on this generic specification of a Graph). In Java, the notion of interface provides exactly this possibility: the Graph model should be defined in term of interface(s) and each specific graph (for instance CG and Ontology) has to implement Graph interface(s).

Let us consider now this solution in more detail and let us start with the sp

ecification of a Graph. A new package (aminePlatform.util.graph) has been added to Amine for that purpose. This package contains three main interfaces: Node interface which provides a specification of graph nodes, Edge interface which specifies graph edges and Graph interface which specifies graph structure. Int_DisplayFrame is an interface for complex nodes (a node that contains a complex description which should be displayed in a separate frame). RelaxGraph is the class responsible for automatic graph drawing (it is introduced in Automatic Graph Drawing).

public interface Graph extends Serializable{
public Node newNode(String contenu, Lexicon lexicon) throws Exception;
public boolean isEmpty();
public Enumeration getNodes();
public Enumeration getEdges();
public int getSize();
public void clear();
public void makeEmpty();
public void addEdge(Edge edge);
public void addNode(Node node);
public void removeNode(Node node);
public void removeEdge(Edge edge);
}

public interface Node extends Serializable{
public void addOutcomeEdge(Edge edge);
public void addIncomeEdge(Edge edge);
public Enumeration getOutcomeEdges();
public Enumeration getIncomeEdges();
public Enumeration getEdges();
public void setOutcomeEdges(ArrayList edges);
public void setIncomeEdges(ArrayList edges);
public boolean hasContentToDisplay();
public String toDisplayString(Lexicon currentLexicon) throws ToStringException;
public void setLeftTopPoint(Point point);
public Point getLeftTopPoint();
public void setRectangle(Rectangle rectangle);
public Node copyNode();
public ArrayList getAdjacentNodes();
}

public interface Edge extends Serializable{
public String getName(Lexicon lexicon);
public void setName(String name, Lexicon lexicon) throws Exception;
public ArrayList getArraySegmentPoints(Lexicon lexicon);
public boolean setSegmentPoints(ArrayList points);
public ArrayList createArraySegmentPoints(Object g, Lexicon lexicon);
public Point createPosRelNameOnSegments(Object g, Lexicon lexicon);
public Object getSourceNode();
public void setSourceNode(Node node);
public Object getTargetNode();
public void setTargetNode(Node node);
public Point getPosRelNameOnSegments(Lexicon lexicon) ;
public void setPosRelNameOnSegments(Point pos);
public Edge copyEdge();
}

The cg package, and especially the classes CG, Concept and Relation have been updated in order to implement the above interfaces: CG implements Graph, Concept implements Node and Relation implements Edge. Also, the ontology package, and especially Ontology, CS and Link have been updated in the same way: Ontology implements Graph, CS implements Node and Link implements Edge. Reader can consult the source code for the detail of these implementations. Note that the class Link was not present in the previous version; it is added to the package Ontology for the purpose of Ontology drawing. Indeed and unlike CG where links between nodes (concepts) are explicitely represented by objects Relation(s), in our implementation of Ontology, links between CSs are not explicitely represented. Link has been added to allow this explicit representation but this use of Link is still secondary: it is not used in the internal representation of the ontology but just for the purpose of ontology drawing.

Now we can provide more detail on the VisualGraph view. Recall that it

corresponds to a (drawing) view for the graph model (expressed in Java in terms of the three interfaces: Graph, Node and Edge). Thus, VisualGraph view is defined on these interfaces and not on a specific graph (implementation), like CG or Ontology. VisualGraph view is implemented in Java in terms of three classes: class VisualGraph which is associated to the interface Graph (VisualGraph is a kind of Wrapper for Graph), class VisualNode which is associated to the interface Node (a Wrapper for Node) and a class VisualEdge which is associated to the interface Edge (a Wrapper for Edge).

Figure 2 presents UML diagrams for these three classes (to get the list of their methods). Note the attributes of each class:

private Graph graph = null; // The interface Graph associated to the VisualGraph
private ArrayList vnodes = new ArrayList(); // a list of VisualNode
private ArrayList vedges = new ArrayList(); // a list of VisualEdge

private Node node = null; // The interface Node associated to the VisualNode
private Rectangle rectangle = null; // Graphical information: rectangle around the node
private ArrayList incomeVEdges = new ArrayList(4); // a list of VisualEdge
private ArrayList outcomeVEdges = new ArrayList(4); // a list of VisualEdge
private Int_DisplayFrame displayFrame = null; // non null for complex VisualNode

private Edge edge; // The interface Edge associated to the VisualEdge
private VisualNode source;
private VisualNode target;
public ArrayList arrow = new ArrayList(3); // Graphical information

The class GraphDrawPanel constitutes the core of the Graph Drawing Editor (Figure 3): most of drawing operations are defined in this class. GraphDrawPanel is a re-engineering of CG Draw Panel, developed in our early CG graphic editor. Usual graph drawing editor facilities are provided: selection (selection of a node, of an edge, of a part of a graph or of all the graph), creation and placement of nodes and edges, move of nodes, edges or sub-graphs, edition of the content of a node or of an edge, remove of a node, of an edge, or of a part of a graph or the whole graph, etc. Please note that GraphDrawPanel treats VisualGraph view only (VisualGraph, VisualNode and VisualEdge classes), it does not treat Graph model (Graph, Node and Edge interfaces). Methods of VisualGraph, VisualNode and VisualEdge are concerned however by the Graph model. For instance, a treatment on a VisualNode initiates (in general) a corresponding treatment in Node. Thus, GraphDrawPanel can initiate the creation (or a deplacement) of a new VisualNode and this creation, as a method of VisualNode, will initiate the creation (or change in node location) of the corresponding node.

GraphDrawPanel can be used as a Panel for GraphDrawFrame which is implemented as a JInternalFrame. If a specific graph drawing editor requires the edition of composed graphs (graphs inside nodes, like compound CG), then we will have several GraphDrawFrames, all of them will be inserted in the desktop of the main frame. To make the main frame itself generic (and allowing its integration in different contexts and applications), it is specified as an interface:

public interface MainFrame {
public GraphDrawFrame getCurrentGraphDrawFrame();
public void setCurrentGraphDrawFrame(GraphDrawFrame graphDrawFrame);
public void updateMenuItems();
public void updateMenuItems1And2(boolean mode);
public void closeFrame(GraphDrawFrame graphDrawFrame, boolean andDescendant);
public ArrayList getChildrenOf(GraphDrawFrame graphDrawFrame);
public void addChild(GraphDrawFrame frame, GraphDrawFrame newChild);
public void repaintMainFrame();
public void File_Save();
public JDesktopPane getDeskTop();
public GraphDrawPanel getNewGraphDrawPanel(GraphDrawFrame frame, Lexicon lexicon);
public void onCut();
public void onCopy();
public void onPaste();
public void onEditNode();
public void onEditEdge();
}

As it is, the Generic Graph Drawing Application presented in this section, with its architecture, can not be used directly for graphical edition of graphs. Why ? because it is generic ! The architecture is built upon the graph package of interfaces (Graph, Node and Edge). These interfaces should be implemented by specific graphs to get specific graphical editors. In Amine, the above generic architecture is specialized in two specific applications: CG Drawing editor and Ontology Drawing editor.

CG Drawing is based on the implementation of graph interfaces package by cg (classes) package. Little changes and extensions are made to get CG Drawing Editor: cgDrawing package is composed of two classes: CGDrawPanel which is a simple extension of GraphDrawPanel (the extension concerns basically visualization of concept state) and HierarchyWndCG which treats the hierarchy of frames associated to embedded CGs.

CG Drawing editor is integrated to a separate GUI for CG Drawing (CG Drawing GUI, see Figure 4). It is integrated also in other GUIs (CGNotations GUI, Ontology GUI, CGOperations GUI, etc.). Indeed, it is integrated to several GUIs where CG can be described in Linear form, in CGIF, or in Graphical form (Figure 5). The three notations are three views of a CG, any change in a view has an impact in the other views. See CG Graphic Editors for more detail.

As noted above, Amine provides usual graph drawing editor facilities: selection (selection of a node, of an edge, of a part of a graph or of all the graph), creation and placement of nodes and edges, move of nodes, edges or sub-graphs, edition of the content of a node or of an edge, remove of a node, of an edge, or of a part of a graph or the whole graph, etc. To select part of a graph, the user has to draw a rectangle that enclose the subgraph (start for instance with the left-top point, with a left-button click, and then drag the mouse to the right-bottom point of the rectangle). The selected subgraph can be moved (by dragging the mouse with the right-button pressed), copied or removed (cut).

Note also the treatment of the edition mode: once a node/concept has been created/edited, the editor will remain in the node/concept mode; the cursor has the text form and the user can create another node. Also, once an edge/relation has been created/edited, the editor will remain in the edge/relation mode; the user can create another edge. To desactivate the current mode, the user has to perform a right-button click. he/she returns to the command mode.

Figure 6 illustrates the case of several frames when the graph is a composed graph, like compound CG.

Like CG Drawing, Ontology Drawing is based on the implementation of graph interfaces package by ontology (classes) package. Again like CG, Ontology Drawing Editor is integrated to a separate GUI for Ontology Drawing (OntologyDrawing GUI). It is integrated also in LexiconsOntology GUI. See this GUI for more detail.

We need automatic drawing of CG when a user enters his/her CG in Linear form (or in CGIF) and asks for the graphical view of the CG or when a user requires the result of a CG operation in a graphical view. We need also automatic drawing of an Ontology to follow for instance the execution of dynamic integration process and to see how the ontology is explored and updated. Salvo Jesus developed a Java Open Source project (OpenJGraph) for Graph Drawing in order to perform automatic Graph drawing. He provides several classes that implement various algorithms for tree and graph drawing, according to the type of the tree and of the graph. Currently, we used one class (with some modifications); ForceDirectedLayout which implements an algorithm proposed by Tollis I. G. and al. in their book : Graph Drawing: Algorithms for the Visualization of Graphs, Prentice-Hall, 1998.

For automatic drawing of ontology, we use currently the Sugayama algorithm. See LexiconsOntology GUI for more detail.

Figure 8 highlights classes and packages of Amine that are concerned by Graph Drawing.