EngiGraph

Now we come to 'EngiGraph' which manages a set of nodes and arcs, traverses them in depth- or breadth-first order, and arranges them in a tree. The program is in Appendix 27.

'EngiGraph' is an abstract class and the super class of 'EngiDirectedGraph' and 'EngiUndirectedGraph', which we'll cover in the next section.

Let us examine the class definition of 'EngiGraph'. I think it should be a subclass of 'EngiGeometric' like this:

-------------------------------------------------------
EngiGeometric subclass: #EngiGraph
        instanceVariableNames: '
                graphVertices
                graphBranches
                graphQueue
                arrangeFormat '
        classVariableNames: ''
        poolDictionaries: ''
        category: 'Engi-Graph'
-------------------------------------------------------

Instance variables for the class are 'graphVertices' for the set of nodes, 'graphBranches' for the set of arcs, 'graphQueue' as a temporary queue during graph traversal, and 'arrangeFormat' which stores formatting parameters.

-------------------------------------------------------
graphVertices   appearance order of nodes
graphBranches   appearance order of arcs
graphQueue      used for breadth first search
arrangeFormat    #(layout-direction spacing margin balance-switch)
-------------------------------------------------------

The following methods are expected to be implemented suitably for subclasses of 'EngiGeometric'.

-------------------------------------------------------
computeBounds
        ^self subclassResponsibility
-------------------------------------------------------
rotatedBy: angleDegree
        ^self subclassResponsibility
-------------------------------------------------------
scaledBy: scalePoint
        ^self subclassResponsibility
-------------------------------------------------------
translatedBy: amountPoint
        ^self subclassResponsibility
-------------------------------------------------------
displayFilledOn: graphicsContext at: aPoint
        ^self subclassResponsibility
-------------------------------------------------------
displayStrokedOn: graphicsContext at: aPoint
        ^self subclassResponsibility
-------------------------------------------------------

'computeBounds' can be implemented by merging the display areas (bounds) of all the nodes and arcs. Messages for affine conversions (rotatedBy:, scaledBy:, translatedBy:) and stroke displaying (displayStrokedOn:at:) can be delegated to nods and arcs. Nothing needs to be done for displayFilledOn:at:.

These messages to handle nodes.

-------------------------------------------------------
includesVertex: aVertex  < is a node in a graph ?>
addVertex: aVertex       < Add a node>
removeVertex: aVertex    < remove a node>
doVertices: aBlock       < for all vertices, do something >
doVerticesDepthFirst: aBlock   < process nodes depth first >
doVerticesBreadthFirst: aBlock < process nodes depth first >
-------------------------------------------------------

These messages to handle arcs.

-------------------------------------------------------
includesBranch: aBranch < is an arc in a graph ?>
addBranch: aBranch      < Add an arc>
removeBranch: aBranch   < Remove an arc>
doBranches: aBlock      < Trace arcs by appearance order>
doBranchesDepthFirst: aBlock   < process arcs depth first>
doBranchesBreadthFirst: aBlock < process arcs breadth first>
-------------------------------------------------------

Messages to process nodes and arcs depth- or breadth-first eventuall call:

-------------------------------------------------------
visitDepthFirstVertexDo:   vertexBlock branchDo: branchBlock
visitBreadthFirstVertexDo: vertexBlock branchDo: branchBlock
-------------------------------------------------------

The 'vertexBlock' argument is a block closure applicable to nodes; the 'branchBlock' is a block closure applicable to branches.

Experienced Smalltalkers will often use block closure as arguments. Becoming skillful at handling block closures is an indicator that you're becoming more proficient in Smalltalk. The reason is that control structures such as loops and conditional branches should ideally be objects themselves who know how to deal with the data-objects given to them. I don't think it is stretching to say that this is the reason for the existence of block closures. So experienced Smalltalkers create control objects which in turn handle other objects.

This message does the layout of nodes and arcs.

-------------------------------------------------------
arrangeScan
-------------------------------------------------------

It uses the data stored in the node and arc instance variables to calculates node and arc positions.

The followings are messages link and unlink nodes. You can say 'link node A to node B' or 'unlink node A from node B'.

-------------------------------------------------------
connect: startVertex with: endVertex
        ^self subclassResponsibility
-------------------------------------------------------
disconnect: startVertex with: endVertex
        ^self subclassResponsibility
-------------------------------------------------------

However, at this level you do not have information to actually make the links because that depends on node and arc types, for example whether the graph is directed. So, we just define the message interface here and leave the details to the link to sub classes which we will cover later.

File in Appendix 27 then do it Program 43-1.

Program-43-1: (EngiGraph, EngiVertex, EngiBranch, EngiDisplayModel;
vertexPoint:, startVertex:, endVertex:, addBranch:)
-------------------------------------------------------
| aGraph aVertex1 aVertex2 aVertex3 aBranch1 aBranch2 |
aGraph := EngiGraph new.
aVertex1 := EngiVertex new.
aVertex2 := EngiVertex new.
aVertex3 := EngiVertex new.
aBranch1 := EngiBranch new.
aBranch2 := EngiBranch new.
aVertex1 vertexPoint: 10 @ 50.
aVertex2 vertexPoint: 90 @ 10.
aVertex3 vertexPoint: 90 @ 90.
aBranch1 startVertex: aVertex1.
aBranch1 endVertex: aVertex2.
aBranch2 startVertex: aVertex1.
aBranch2 endVertex: aVertex3.
aGraph addVertex: aVertex1.
aGraph addVertex: aVertex2.
aGraph addVertex: aVertex3.
aGraph addBranch: aBranch1.
aGraph addBranch: aBranch2.
(EngiDisplayModel on: aGraph) open
-------------------------------------------------------

You'll see a window with three nodes and two arcs positioned as specified. Use the yellow-button to inspect the graph and check on the coordinates of the 5 graph objects.

Program 43-2 uses EngiVisualTransporter to let the user move the whole graph around via the mouse. (If EngiGraph were not a subclass of EngiGeometric, could EngiVisualTransporter move a graph around? What is required of an object in order for EngiVisualTransporter to be able to move it around?)

Program-43-2: (EngiGraph, EngiVertex, EngiBranch, EngiVisualTransporter;
follow:while:on:)
-------------------------------------------------------
| aGraph aVertex1 aVertex2 aVertex3 aBranch1 aBranch2 visualTransporter |
aGraph := EngiGraph new.
aVertex1 := EngiVertex new.
aVertex2 := EngiVertex new.
aVertex3 := EngiVertex new.
aBranch1 := EngiBranch new.
aBranch2 := EngiBranch new.
aVertex1 vertexPoint: 10 @ 50.
aVertex2 vertexPoint: 90 @ 10.
aVertex3 vertexPoint: 90 @ 90.
aBranch1 startVertex: aVertex1.
aBranch1 endVertex: aVertex2.
aBranch2 startVertex: aVertex1.
aBranch2 endVertex: aVertex3.
aGraph addVertex: aVertex1.
aGraph addVertex: aVertex2.
aGraph addVertex: aVertex3.
aGraph addBranch: aBranch1.
aGraph addBranch: aBranch2.
visualTransporter := EngiVisualTransporter load: aGraph.
visualTransporter
        follow: [aGraph class activeSensor cursorPoint]
        while: [aGraph class activeSensor noButtonPressed]
        on: aGraph class activeGraphicsContext
-------------------------------------------------------

Program 43-3 shows how to do graph layout. The program specifies layout parameters and then calls 'arrangeScan'. Use the inspector on the graph and try things like 'self arrangeDirection: #left' followed by 'self arrangeScan', then resize the window to cause the graph to redisplay. Also try 'self arrangeMargin: 10' etc.

Program-43-3: (EngiGraph, EngiVertex, EngiBranch, EngiVisualTransporter;
arrange, layout, arrangeDirection:, arrangeInterval:, arrangeMargin:, arrangeScan)
-------------------------------------------------------
| aGraph aVertex1 aVertex2 aVertex3 aBranch1 aBranch2 |
aGraph := EngiGraph new.
aVertex1 := EngiVertex new.
aVertex2 := EngiVertex new.
aVertex3 := EngiVertex new.
aBranch1 := EngiBranch new.
aBranch2 := EngiBranch new.
aVertex1 vertexPoint: 10 @ 50.
aVertex2 vertexPoint: 90 @ 10.
aVertex3 vertexPoint: 90 @ 90.
aBranch1 startVertex: aVertex1.
aBranch1 endVertex: aVertex2.
aBranch2 startVertex: aVertex1.
aBranch2 endVertex: aVertex3.
aGraph addVertex: aVertex1.
aGraph addVertex: aVertex2.
aGraph addVertex: aVertex3.
aGraph addBranch: aBranch1.
aGraph addBranch: aBranch2.
aGraph arrangeDirection: #top.
aGraph arrangeInterval: 50.
aGraph arrangeMargin: 100.
aGraph arrangeScan.
(EngiDisplayModel on: aGraph) open
-------------------------------------------------------

The next section describes 'EngiDirectedGraph' and 'EngiUndirectedGraph' whose super class is 'EngiGraph'.