Understanding jKSImapper

NOTE: The latest (not fully-tested) jKSImapper source code can be downloaded here. Last updated sometime in 1999.

• What is a Concept Map
• What is jKSImapper
• How is jKSImapper programmed to support Concept maps?
• How are Behavioural and Visual classes organized?
•     Behavioural classes
•     Visual classes
•     The Cell class
•     The LocationCell class
•     The ResetHandlesLocationVisitor class
• References
• What is a Concept Map?
Concept maps are specialized kind of diagrams composed of nodes and arcs. An example of a concept map is shown on Figure 1 below. This figure shows a simple but expressive graph consisting of two nodes and one arc, where the node labeled as "Earth" has a link directed toward the node labeled "Planet". This diagram expresses the notion that "Earth is a Planet". The directed arc in this graph is known as an "IS A" arc due to the relationship represented between the concepts "Earth" and "Planet".

 Figure 1. Diagram expressing the notion "Earth is a Planet".

What is jKSImapper?
jKSImapper is a computer program that supports the drawing of concept maps by allowing the manipulation of node and arc objects. Figure 2 shows an instance of a jKSImapper program containing a concept map constructed after Sowa's linguistic formalism called Conceptual Graphs. This figure shows rectangular shaped nodes (such as the ones labeled as "TEACHER:x", "WRITE" and "BOOK"),  ellipse shaped nodes ("AGNT" and "OBJ"), several directed and one non-directed arc, and a special kind of "hollow" node to encompass other nodes and arcs. This special type of node is called Context box (which is labeled "NOT" in this example).

 Figure 2. jKSImapper with a formal diagram expressing the sentence "No student reads the book written by the teacher".
How is jKSImapper programmed to support Concept maps?
The mechanism underlying jKSImapper can be described as a collection of "logical" graphs each supporting a "visual" element. This framework, which is depicted on Figure 3, is the core mechanism of jKSImapper. Logical graphs are better known as BehaviouralGraphs. These graphs process requests made by users within the context of a multi-graph environment called jCMap. BehaviouralGraphs are non-displayable by nature. As a result, they rely on a VisualGraph instance for visual representation. This architecture allows logical graphs to exist independently of a particular visual representation, therefore decoupling the runtime manipulation of visual elements from their logical parents.

 Figure 3. jKSImapper core architecture .

How are Behavioural and Visual classes organized?
Figure 4 below shows the class hierarchy conforming the visual and non-visual objects on jKSImapper. The super-parent of all graphs is an interface named AbstractGraph. This interface extends from other interfaces, which are explained below.
• Drawable (Interface): Defines methods to paint a graph.
• Selectable (Interface):  Defines methods to select a graph.
• Shadowable (Interface): Defines methods to manipulate the shadowing of a graph.
• Positionable (Interface): Defines methods to modify the (x,y) position  of a graph.
• Resizable (Interface): Defines methods to modify the dimensions (i.e., width and height) of a graph.
• Containable (Interface): Defines methods to query if a graph contains a point or if it is fully contained by an area.
• Attachable (Interface): Defines methods to get a graph's anchor point based on an oncoming position from where the graph is to be anchored by an arc.
• MouseHitable (Interface): Defines methods to query information from a graph based on the position of the mouse pointer.
• Parseable (Interface): Defines methods to read/write a graph's data in linear form to a stream.

 Figure 4. jKSImapper's Graphs class hierarchy.
AbstractGraph is the direct parent of the VisualParent and VisualChild interfaces. For objects, being a sub-type of VisualParent indicates that they own a visually-displayable graph (i.e., an instance of VisualChild) and that they define methods to set/get this visual graph. Accordingly, the interface VisualChild indicates objects that are owned by a VisualParent instance. The VisualChild interface defines methods to get/set a visual graph's  parent.

Behavioural classes
The BehaviouralGraph abstract class is the sole descendant of the VisualParent interface. This class implements the common behaviour for all non-visible graphs. In addition to be the parent (i.e., owner) of a visible graph, BehaviouralGraph inherits methods from Java's Observable class (through the BehaviouralObservable abstract class) and  also implements several interfaces. This class and the interfaces from where BehaviouralGraph descends are briefly described as follows.
• BehaviouralObservable (Abstract Class): Allows a behavioural graph to be "observed" by other graphs. This is usually the case of nodes, which can have arcs attached to them. In such cases, nodes (i.e., observables) notify arcs (i.e., observers) of any changes on the node that may affect them (e.g., arcs attached to a node adjust their rendering to a new position when the node notifies them after a size or location change).
• MouseEventHandler (Interface): Defines methods to handle mouse events such as movement, dragging, and clicking, among others.
• PopupProvider (Interface): Defines methods for providing a default popup menu, if one is not externally provided.
• IDHolder (Interface): Defines methods for graphs with an ID. Graphs featuring an ID are eligible to receive commands that execute an action.
• TargetQuerable (Interface): Defines methods to query a graph for its ID.
jCMapGraph is an abstract class sub-classed from BehaviouralGraph. This class acts as a required super-parent class for objects that are added to the jCMap graph pool. jCMapGraph implements the ZPositionable interface, which defines methods to manipulate their ordering under the Z-axis (i.e., to control the overlapping ordering of jCMapGraphs on a third dimension). jCMapGraph has the following three descendant classes: Node, Link and ContextBox.
• Node (Class): This class defines the behaviour of a node. Node objects support visual instances from sub-classes of the abstract class VisualShape.
• ContextBox (Class): This class defines the behaviour of context boxes. Since context boxes display similar responses as nodes, they are implemented as a node specialization.
• Link (Class): This class defines the behaviour of arcs, which are composed of handles (or "elbows"). Although the Link class  is defined as a VisualParent descendant it does not own (at least not directly) any displayable element. Instead, its visual representation depends on a Handle Composite structure it references (Note: Handles and Links are covered in detail under the "Understanding Links and Handles" section below). Besides from the behaviour it inherits from BehaviouralGraph, Link also implements methods defined in the HandleInterface interface, which specifies methods common to Handle and Link classes.
Handle is an special sub-class of BehaviouralGraph. Instances of Handle are used to construct a hierarchical tree structure referenced by Link objects. As shown in Figure 4 above, Handle is a descendant of VisualChild (since it is parented by a Link object), but it is also a VisualParent since it owns a VisualHandle object that performs as its visual element. In addition to descend from BehaviouralGraph and VisualChild, this class also implements the following interfaces.
• Visitable (Interface): Defines methods to allow Visitor objects to traverse a tree structure of Handle objects.
• BehaviouralObserver (Interface): Defines methods to add and remove a dependency with a BehaviouralObservable object.
• HandleInterface (Interface): Defines methods common to the Link and Handle classes.
• IntermediateHandle (Interface): Define methods to manipulate a line that is "bent" to create a new "elbow" (i.e., handle).
• BranchHandle (Interface): Define methods to manipulate a new line branching from a handle.
Visual classes
Visual classes are classes descendant from the VisualGraph abstract class (which in turn descends from the VisualChild interface). VisualGraph has two descendants, VisualHandle and VisualShape.
• VisualHandle (Class): This class implements the mechanisms required to display a link handle and its corresponding line. This class implements the IntermediateHandle and BranchHandle interface, which support the creation of a new handle and a new line, respectively. Instances of this class have objects of type Handle as their parents.
• VisualShape (Abstract class): This abstract class implements methods common to visual shape elements. This class have four descendant classes: VisualRectangle, VisualRoundedRectangle, VisualEllipse and VisualContextBox. From these classes, the first three are visual elements for Node objects and the latter is the visual element for ContextBox instances.

Links are implemented as a Composite structure of Handle objects, which are arranged as a multi-level tree hierarchy (for a detailed description of the Composite design pattern, refer to Gamma, et. al, 1994). Figure 5 shows a Link object as it would be shown by jKSImapper. This Link is composed of four handles that are labeled A, B, C and D, respectively. It is worth noticing that it is not possible to devise how this link is structured internally without an apriori knowledge of how it was constructed. This is, the underlying hierarchy for the link shown could be any of the four structures illustrated in Figure 5.

 Figure 5. Example of a hierarchy of Handles based on their graphical rendering.

Handles can be Terminal or Non-Terminal. For example, handles A, B and D are Terminal; C is Non-Terminal. Terminal handles can be Attached or Non-Attached. Handles B and D are Terminal Non-Attached handles; A is a Terminal Attached handle (handles are generally attached to nodes, as in this case). Non-Terminal handles can be Fixed or Free. While Fixed handles have their own position, Free handles have a position that is calculated as the geometrical center of its surrounding siblings. Siblings are those handles that have a direct connection with a handle (e.g., the siblings of C are A, B and D; C is the only sibling of A).

Links are created by selecting an initial and a terminal handle location. This process, as shown in Figure 6, involves invoking a popup menu, selecting the "Link" option (this action specifies the initial handle location), dragging the mouse up to the location where the terminal handle will be located, and ending by clicking with the mouse left button. As shown, a gray line (a.k.a."shadow") is drawn from the location of the initial handle to the position of the cursor. The shadowing line is dismissed after the user clicks the mouse to indicate the location of the terminal handle and the termination of the creation command. Shadowing is a convenient technique to give users feedback on how the final line will be drawn.

 Figure 6. Creating a Link object on jKSImapper.
The manipulation operation for Handle objects are as follows.
• Adding a non-terminal handle: Addition of non-terminal handles can be done by direct manipulation (i.e., by clicking and dragging a point from a line segment) or by using a popup menu option. With the latter option, a new handle is added to a line without breaking it. These actions are exemplified in Figure 7 below. This figure also shows the resulting handle hierarchy as it is modified to accommodate the new handle.

•
 Figure 7. Example of the creation of a non-terminal handle using direct manipulation (top) and a popup menu option (bottom).

• Adding a terminal handle: Addition of terminal handles (i.e., branching lines)  is done using a popup menu option, as illustrated in Figure 8. This figure also shows the resulting handle hierarchy as it adapts to accommodate the new handle.

•  Figure 8. Example of the creation of a terminal handle.

• Deleting: Handle deletion is performed using a popup menu selection invoked over the handle to delete, as shown in Figure 9. This figure also shows the hierarchy for the exemplified link before and after the deletion occurs. The following conditions have to be fulfilled to allow the deletion of a handle: a) the handle must have 2 siblings at the most (i.e., a parent and one children), and b) the link to which the targeted handle belongs to must have 3 or more handles in total before deletion (since a link cannot be made of a single handle).

•  Figure 9. Example of a handle deletion using a popup menu..

• Moving: Changes on handle location are achieved by direct manipulation. This action is done by mouse clicking and dragging a handle to a new location. This action is shown in Figure 10.

•  Figure 10. Example of moving a handle to a new location using direct manipulation.

Shadowing is a graphical human-computer interaction mechanism to give users feedback on the results to be produced by a graphical action. In the case of jKSImapper, shadowing is accomplished before committing to a direct manipulation action, such as in the case of the examples presented in figures 6, 7, 8 and 10 (depicting link and handle creation -- terminal and non-terminal -- and handle movement, respectively). One of the characteristics of a shadowing mechanism is that of consistency: it has to reflect the exact outcome that will be obtained by an operation.

jKSImapper provides 2 algorithms to automatically and correctly arrange a link's handles: one algorithm arranges handles to a "balanced visual state" when shadowing, and a second one balances handles after an action is executed. The need for maintaining a link "balanced" is not obvious from the examples presented up to now, therefore Figure 11 shows an example of the dynamics of "balancing" a link. This figure features four different snap-shots of the shadowing mechanism when a handle is moved. This handle has as its only sibling a handle attached to a node. As it can be noticed, the shadow of the "anchored" handle (the one attached to the node) changes its location to a different point on the perimeter of the node according to whether that point is the closest point to the external handle been moved.

 Figure 11. Example of the dynamics of shadowing when moving a handle whose sibling handle is attached to a node.
Beside attached handles, there is a second type of handle that also needs dynamic positioning based on the location of the other handles in a node, and that is the case of non-terminal free handles. Free handles automatically adjust to a central position based on its surrounding fixed siblings. In the case of a free handle that has another free handle as sibling the resulting calculation takes in consideration the sibling's fixed sibling handles (resulting on recursive sibling calculations until a location can be obtained based exclusively on non-free handles). Figure 12 shows an example of shadowing with a non-terminal free handle (the central handle in this case).
 Figure 12. Example of the dynamics of shadowing when moving a handle part of a link containing a free handle (center handle).
The question that raises at this point is Why to use 2 algorithms, one for shadowing and one for the operation itself, if the shadowing algorithm has already calculated the final positions of a "balanced" link? Why aren't the new shadowing locations just adopted as the current locations? The main reason is that of coupling. jKSImapper current mechanisms translate an action (such a direct manipulation action featuring shadowing) into a command that may be sent to a filtering mechanism for validation or to other users if participating on a multi-user session. Therefore it is possible that a request may fail (e.g., if a filtering mechanism does not approve it) or that it can be preceded by other users' commands targeting the same object if in a multi-user environment (thus creating inconsistencies between the data resulting from the shadowing algorithm and the commands generated by other users).

The fundamentals of these algorithms are based on the Visitor design pattern (Gamma et. al, 1994), on which an object is allowed to traverse the hierarchy of handles to obtain information about them. The gathered information is organized as a repository of Cell objects, each storing a dynamic reference and other information related to a handle. Cell's sub-classes LocationCell and ShadowLocationCell are used by the ResetHandlesLocationVisitor and ResetHandlesShadowLocationVisitor classes, respectively. The former class balances a link after it has been modified, while the latter balances a link when shadowing is requested.

The Cell class
Figure 13 lists the Cell abstract class, which is sub-classed by the LocationCell and ShadowLocationCell classes. Instances of this class are initialized by receiving a Handle object from where a reference to it and its sibling handles is obtained. This class declares two abstract methods: locationHasChanged (to learn if the original position of a handle has been modified) and updateLocation (which copies the location stored in this class to the handle referenced).

 public abstract class Cell  {    protected Handle    handle;    protected Container siblings;    protected Cell(Handle handle) {      this.handle     = handle;      this.siblings   = handle.getSurroundingHandles();    }    public abstract boolean locationHasChanged();    public abstract void    updateLocation();  } Figure 13. The Cell class.
The LocationCell class
This class, which is a sub-class of Cell, stores information needed for balancing a link based on its handles' locations. This class, shown in Figure 14, stores the location (original and current) of each handle, as well as if it is attached or free. If a handle is attached to a graph, the central location of that graph is obtained and used for calculations. The abstract methods inherited from Cell are implemented to reflect their desired behaviour.
 public class LocationCell extends Cell  {    private Point   original;    public  Point   location;    public  boolean attached,                    free;    public LocationCell(Handle handle) {      super( handle );          free     = handle.isFree();          attached = handle.isAttached();      if (attached) location = handle.getGraphAttached().getLocation();      else          location = handle.getLocation();          original = new Point( location );    }    public boolean locationHasChanged() {      return !location.equals( original );    }    public void updateLocation() {      handle.setLocation( location );    }  } Figure 14. The LocationCell class.
This class, which is listed in Figure 15, stores information needed to balance a link based on its handles' shadow locations. This class obtains the shadow location (original and current) of a handle, if it is attached or free, its branching and intermediate locations (just one of them could logically be enabled!), and the handle's parent. As with the previously concrete class, this class implements the methods inherited from Cell, one to query if the current location is different from the original, and the other one to save that location as the shadow location of the handle referenced.
The ResetHandlesLocationVisitor class
This class, which is listed in Figure 16, implements the mechanism to balance a link based on its handles' current locations. The order on which this class' methods are execute is as follows. First the constructor initializes a Hashtable object that will store LocationCell instances, one for each Handle object part of the link. The second method to be accessed is the execute method. This method is called as many times as handles exist on the link. When invoked, it receives a Handle object as a parameter. This object is used to initialize a LocationCell instance that is then added to the hashtable. Note that the hashtable has handles' references as its key values and cells as its content values. After the visiting process has concluded (Note: this traversing process is implemented by the Handle class) the resetAllLocations method is invoked. This method checks firstly all attached handles and sets their new position of attachment; then it checks all free handles and calculates their new positions; and finally, it checks all handles and updates those whose location has changed.

This class implements four private methods, which are described below.

The private method setAttachedLocation obtains a new attachment point for an attached handle based on an external reference point. This point is calculated using the calculateReference method. This method receives a handle reference and calculates a central point based on all fixed points surrounding the targeted handle. These fixed points are obtained by invoking the getAllStablePoints method. This method traverses all the handle's siblings until all branches return fixed points of reference. This same process (invoking the calculateReference and getAllStablePoints methods) is used by the setFreeLocation method to calculate the location of  a free handle.

 public class ResetHandlesLocationVisitor  {    private Hashtable handles;    public ResetHandlesLocationVisitor() {      handles = new Hashtable();    }    public void resetAllLocations() {      Enumeration  e;      LocationCell cell;      for (e=handles.elements(); e.hasMoreElements(); ) {             cell = (LocationCell) e.nextElement();        if ( cell.attached )             setAttachedLocation( cell );      }      for (e=handles.elements(); e.hasMoreElements(); ) {             cell = (LocationCell) e.nextElement();        if ( cell.free )             setFreeLocation( cell );      }      for (e=handles.elements(); e.hasMoreElements(); ) {             cell = (LocationCell) e.nextElement();        if ( cell.locationHasChanged())             cell.updateLocation();      }    }    private void setAttachedLocation(LocationCell cell) {      Point reference     = getReferencePoint( cell );            cell.location = cell.handle.getAttachment( reference );    }    private void setFreeLocation(LocationCell cell) {      Point reference     = getReferencePoint( cell );            cell.location = reference;    }    private Point getReferencePoint(LocationCell cell) {      Sequence points    = getAllStablePoints( cell, new SList(), new SList());      Point    reference = new Point();      for (Enumeration e=points.elements(); e.hasMoreElements(); ) {         Point point        = (Point) e.nextElement();               reference.x += point.x;               reference.y += point.y;      }      int totalPoints  = points.size();          reference.x /= totalPoints;          reference.y /= totalPoints;      return reference;    }    private Sequence getAllStablePoints(LocationCell cell,                                        Sequence     visited,                                        Sequence     points) {      for (Enumeration e=cell.siblings.elements(); e.hasMoreElements(); ) {         Handle       handle = (Handle) e.nextElement();         if (visited.contains( handle ))             continue;         LocationCell sibling = (LocationCell) handles.get( handle );         if (sibling.free) {             visited.add       ( handle );             getAllStablePoints( sibling, visited, points );             visited.remove    ( handle );         }         else             points.add( sibling.location );      }      return points;    }    /**     * Visitor interface     */    public void execute(Visitable visitable) {      handles.put( visitable, new LocationCell((Handle) visitable));    }  } Figure 16. The ResetHandlesLocationVisitor class.