EngiGrapherLibrary

This section will start a series on grapher libraries, programs to visualize graphs composed of nodes and arcs. As an example of the application of a grapher library, I'd like to show you a browser which visually displays the class hierarchy tree. I want you study the basic of diagram drawing such as state transition diagrams or entity relation diagrams though this series. I refer you to a Japanese book whose title is 'Data structures and algorithms' (published by Iwanami) written by Dr. Kiyoshi Ishibatake. This is a very good book, but unfortunately it has not been translated into English. I wish someone would! Anyway, the algorithms I use to trace the nodes and arcs by depth first or breadth first search are from that book.

The classes I introduce in this series are marked '*':
-----------------------------------------------------------
        Object
        . EngiGeometric                        *
        . . EngiBranch                         *
        . . . EngiBranchWithArrow              *
        . . . EngiClassBranch                  *
        . . EngiGraph                          *
        . . . EngiDirectedGraph                *
        . . . . EngiClassGraph                 *
        . . . EngiUndirectedGraph              *
        . . EngiVertex                         *
        . . . EngiClassVertex                  *
-----------------------------------------------------------
        Object
        . Model
        . . EngiVariable
        . . . EngiDisplayModel
        . . . . EngiGraphModel                 *
        . . . . . EngiClassGraphModel          *
-----------------------------------------------------------
        Object
        . EngiGraphicsState                    *
-----------------------------------------------------------

First there is 'EngiGeometric', an abstract class. 'EngiVertex' is a subclass for nodes and 'EngiBranch' is a subclass for arcs. 'EngiGraph' is also a subclass of 'EngiGeometric'. It has two subclasses named 'EngiDirectedGraph' and 'EngiUndirectedGraph'.

The class hierarchy tree which is displayed by the inheritance browser as an example is supported by 'EngiClassGraph' which is composed of 'EngiClassVertex' to express classes and 'EngiClassBranch' to express the hierarchy relation between classes. Note that 'EngiClassGraph' is a 'EngiDirectedGraph' which is a 'EngiGraph' which is a 'EngiGeometric'. Also note that 'EngiClassVertex' is an 'EngiVertex' and 'EngiClassBranch' is an 'EngiBranch'. So both 'EngiVertex' and 'EngiBranch' are subclasses of 'EngiGeometric'.

'EngiGraphModel' stores an 'EngiGraph' as it's value and is a subclass of 'EngiDisplayModel', which has already been described. The User interface is attached to the model via the Model-View-Controller framework.

'EngiGraphicsState' stores information required to display 'EngiGeometric' on the screen.

Now, let's consider attributes of the classes.

----------------------------------------------------------------
Object ()
. EngiGeometric ('graphicsState' 'cachedBounds')
. . EngiBranch ('startVertex' 'endVertex' 'branchWeight')
. . . EngiBranchWithArrow ()
. . . EngiClassBranch ()
. . EngiGraph ('graphVertices' 'graphBranches'
               'graphQueue' 'arrangeFormat')
. . . EngiDirectedGraph ()
. . . . EngiClassGraph ()
. . . EngiUndirectedGraph ()
. . EngiVertex ('vertexPoint' 'vertexExtent' 'vertexState')
. . . EngiClassVertex ('className' 'classIcon')
----------------------------------------------------------------
Object ()
. Model ('dependents')
. . EngiVariable ('value')
. . . EngiDisplayModel ('displayBounds' 'displayOrigin' 'windowLabel')
. . . . EngiGraphModel ('graphSelections')
. . . . . EngiClassGraphModel ()
----------------------------------------------------------------
Object ()
. EngiGraphicsState ('strokeColor' 'fillColor' 'lineWidth')
----------------------------------------------------------------

'EngiGeometric' has two instance variables named 'graphicsState' and 'cachedBounds'. An instance of 'EngiGraphicsState' is stored in 'graphicsState' and 'cachedBounds' stores a rectangle (an instance of 'Rectangle') in which to display the 'EngiGeometric'.

'EngiBranch' (an arc) has three instance variables. 'startVertex' stores the start node, 'endVertex' stores the end node, and 'branchWeight' stores the weight of the arc.

An instance variable 'vertexPoint' of 'EngiVertex' (a node) stores the coordinates of the node, 'vertexExtent' stores the size of the node, 'vertexState' has symbols (#unvisited, #entered, #visited) to scan the node. 'EngiClassVertex' is a specialized class node which also has 'className' and 'classIcon'.

'EngiGraph' has four instance variables. 'graphVertices' stores nodes, 'graphBranches' stores arcs, 'graphQueue' is used temporarily in doing a breadth first search, 'arrangeFormat' stores layout parameters. 'EngiGraphModel' stores an instance of 'EngiGraph' in an inherited instance variable 'value', and uses 'graphSelections' to store any selected nodes and arcs. 'EngiGraphicsState' is composed of 'strokeColor', 'fillColor', used for line- and fill-color, and 'lineWidth', which is used for, you guessed it, the line width. The next few sections will cover the grapher classes one by one.