Understanding jKSImapper

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

Table of Contents

  • 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
  • Understanding Links and Handles
  • Manipulating Links and Handles
  • Links and Shadowing
  •     The Cell class
  •     The LocationCell class
  •     The ShadowLocationCell class
  •     The ResetHandlesLocationVisitor class
  •     The ResetHandlesShadowLocationVisitor 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.
     
    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. 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. 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. 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.
    Understanding Links and Handles
    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).
     
    Manipulating Links and Handles
    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. Links and Shadowing
    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.
     
    The ShadowLocationCell 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.
    public class ShadowLocationCell extends Cell 
    { 
      public  Handle  parent; 
      public  Point   intermediate, 
                      branch, 
                      shadowLocation; 
      private Point   shadowOriginal; 
      private boolean shadowFree, 
                      shadowAttached; 

      public ShadowLocationCell(Handle handle) { 
        super( handle ); 

        if (handle.isTopHandle()) parent = null; 
        else                      parent = (Handle) handle.getParent(); 

        intermediate   = handle.getIntermediateLocation(); 
        branch         = handle.getBranchLocation(); 
        shadowLocation = handle.getShadowLocation(); 
        shadowOriginal = new Point( shadowLocation ); 
        shadowFree     = handle.isShadowFree(); 
        shadowAttached = handle.isShadowAttached(); 
      } 
      public boolean locationHasChanged() { 
        return !shadowLocation.equals( shadowOriginal ); 
      } 
      public void updateLocation() { 
        handle.setShadowLocation( shadowLocation.x, shadowLocation.y ); 
      } 
    }

    Figure 15. The ShadowLocationCell class.
     
    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.
     
    The ResetHandlesShadowLocationVisitor class
    This class, which is shown in Figure 17, implements the behaviour necessary to balance a link based on its handles' shadow locations. Similarly to the visitor class previously described above, the order on which this class' methods are executed is: constructor (initializes hashtable), execute (populates the hashtable with ShadowLocationCell objects) and resetAllLocations. This latter method checks for attached handles and updates their shadow attachment location; it checks for free handles and calculates their location; and at last it updates all shadow locations that have changed.

    This class also implements the same four private methods (setAttachedLocation, setFreeLocation, calculateReference and getAllStablePoints) as the ResetHandlesLocationVisitor class did, but they are applied to shadowing instead of current locations. From these methods, getAllStablePoints is the one that differs the most between these two classes regarding the mechanisms of implementation, since in this class this method checks for a branching new line (existing if a new terminal handle is been created) and for an intermediate handle (if a new non-terminal handle is been created).

    public class ResetHandlesShadowLocationVisitor 
    { 
      private Hashtable handles; 

      public ResetHandlesShadowLocationVisitor() { 
        handles = new Hashtable(); 
      } 

      public void resetAllShadowLocations() { 
        Enumeration        e; 
        ShadowLocationCell cell; 

        for (e=handles.elements(); e.hasMoreElements(); ) { 
               cell = (ShadowLocationCell) e.nextElement(); 
          if ( cell.shadowAttached ) 
               setAttachedLocation( cell ); 
        } 
        for (e=handles.elements(); e.hasMoreElements(); ) { 
               cell = (ShadowLocationCell) e.nextElement(); 
          if ( cell.shadowFree ) 
               setFreeLocation( cell ); 
        } 
        for (e=handles.elements(); e.hasMoreElements(); ) { 
               cell = (ShadowLocationCell) e.nextElement(); 
          if ( cell.locationHasChanged()) 
               cell.updateLocation(); 
        } 
      } 

      private void setAttachedLocation(ShadowLocationCell cell) { 
        Point reference           = getReferencePoint( cell ); 
              cell.shadowLocation = cell.handle.getShadowAttachment( reference ); 
      } 

      private void setFreeLocation(ShadowLocationCell cell) { 
        Point reference           = getReferencePoint( cell ); 
              cell.shadowLocation = reference; 
      } 

      private Point getReferencePoint(ShadowLocationCell 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(ShadowLocationCell cell, 
                                          Sequence           visited, 
                                          Sequence           points) { 
        if (cell.shadowFree && (cell.branch != null)) 
            points.add( cell.branch ); 

        for (Enumeration e=cell.siblings.elements(); e.hasMoreElements(); ) { 
           Handle             handle = (Handle) e.nextElement(); 

           if (visited.contains( handle )) 
               continue; 

           ShadowLocationCell sibling = (ShadowLocationCell) handles.get( handle ); 

           if ((sibling.intermediate != null) && (sibling.parent == cell.handle)) 
              points.add( sibling.intermediate ); 
           else 
              if ((cell.intermediate != null) && (cell.parent == sibling.handle)) 
                 points.add( cell.intermediate ); 
              else 
                 if (sibling.shadowFree) { 
                     visited.add       ( handle ); 
                     getAllStablePoints( sibling, visited, points ); 
                     visited.remove    ( handle ); 
                 } 
                 else 
                     points.add( sibling.shadowLocation ); 
        } 
        return points; 
      } 
      /** 
       * Visitor interface 
       */ 
      public void execute(Visitable visitable) { 
        handles.put( visitable, new ShadowLocationCell((Handle) visitable)); 
      } 
    }

    Figure 17. The ResetHandlesShadowLocationVisitor class.
     
    References
    Gamma, E., Helm, R., Johnson, R. and Vlissides, J. (1994) Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley.


    Last modified: July 27, 1998 by Roberto A. Flores