EngiDirectedGraph & EngiUndirectedGraph

This section develops 'EngiDirectedGraph' and 'EngiUndirectedGraph' from 'EngiGraph', introduced in the previous section. The source is in Appendix 28.

Class definitions are:

Program-44-1: (EngiDirectedGraph, EngiUndirectedGraph)
-----------------------------------------------------------------
EngiGraph subclass: #EngiDirectedGraph
        instanceVariableNames: ''
        classVariableNames: ''
        poolDictionaries: ''
        category: 'Engi-Graph'!
-----------------------------------------------------------------
EngiGraph subclass: #EngiUndirectedGraph
        instanceVariableNames: ''
        classVariableNames: ''
        poolDictionaries: ''
        category: 'Engi-Graph'!
-----------------------------------------------------------------

Messages to determine whether a graph is directed are in the 'testing' message category.

-----------------------------------------------------------------
!EngiDirectedGraph methodsFor: 'testing'!

isDirectedGraph
        ^true! !
-----------------------------------------------------------------
!EngiUndirectedGraph methodsFor: 'testing'!

isUndirectedGraph
        ^true! !
-----------------------------------------------------------------

Default arc and node classes are defined in the 'defaults' message category. 'EngiBranchWithArrow' and 'EngiVertex ' are defined for the directed graph. And 'EngiBranch' and 'EngiVertex' are defined for the undirected graph.

-----------------------------------------------------------------
!EngiDirectedGraph methodsFor: 'defaults'!

defaultBranchClass
        ^EngiBranchWithArrow!

defaultVertexClass
        ^EngiVertex! !
-----------------------------------------------------------------
!EngiUndirectedGraph methodsFor: 'defaults'!

defaultBranchClass
        ^EngiBranch!

defaultVertexClass
        ^EngiVertex! !
-----------------------------------------------------------------

Messages to link and unlink nodes are defined in the 'connecting' message category.

Program-44-2: (EngiDirectedGraph; connect:with:, disconnect:with:)
------------------------------------------------------------------
!EngiDirectedGraph methodsFor: 'connecting'!

connect: startVertex with: endVertex
        | aBranch |
        aBranch := self defaultBranch.
        aBranch startVertex: startVertex.
        aBranch endVertex: endVertex.
        (self includesBranch: aBranch)
                ifFalse: [self addBranch: aBranch].
        (self includesVertex: startVertex)
                ifFalse: [self addVertex: startVertex].
        (self includesVertex: endVertex)
                ifFalse: [self addVertex: endVertex]!

disconnect: startVertex with: endVertex
        | aBranch |
        aBranch := self defaultBranch.
        aBranch startVertex: startVertex.
        aBranch endVertex: endVertex.
        (self includesBranch: aBranch)
                ifTrue: [self removeBranch: aBranch]! !
-----------------------------------------------------------------

'connect:with:' creates a default arc, adds the two vertices to it and then tries to add the branch to the graph. 'disconnect:with:' creates an arc linking two nodes and if one like it already exists, it removes the one in the graph. So disconnecting is not done via names or keys, but rather with example branches themselves.

Program-44-3: (EngiUndirectedGraph; connect:with:, disconnect:with:)
-----------------------------------------------------------------
!EngiUndirectedGraph methodsFor: 'connecting'!

connect: startVertex with: endVertex
        | aBranch |
        aBranch := self defaultBranch.
        aBranch startVertex: startVertex.
        aBranch endVertex: endVertex.
        (self includesBranch: aBranch)
                ifFalse:
                        [self addBranch: aBranch.
                        self addVertex: startVertex.
                        self addVertex: endVertex].
        aBranch := self defaultBranch.
        aBranch startVertex: endVertex.
        aBranch endVertex: startVertex.
        (self includesBranch: aBranch)
                ifFalse:
                        [self addBranch: aBranch.
                        self addVertex: startVertex.
                        self addVertex: endVertex]!

disconnect: startVertex with: endVertex
        | aBranch |
        aBranch := self defaultBranch.
        aBranch startVertex: startVertex.
        aBranch endVertex: endVertex.
        (self includesBranch: aBranch)
                ifTrue: [self removeBranch: aBranch].
        aBranch := self defaultBranch.
        aBranch startVertex: endVertex.
        aBranch endVertex: startVertex.
        (self includesBranch: aBranch)
                ifTrue: [self removeBranch: aBranch]! !
-----------------------------------------------------------------

For undirected links, 'connect:with: creates an arc for each direction and adds both of them to the graph. To delete a link, it creates two example arcs to check for their existence.

File in Appendix 28 and find examples for 'EngiDirectedGraph' and 'EngiUndirectedGraph'.

• Example 1 displays a graph and lets the user drag one node around, updating the arcs as the node is moved.
• Example 2 traces nodes and arcs from the root node in depth first order.
• Example 3 traces nodes and arcs from the root node in breadth first order.
• Example 4 traces nodes and arcs from the end node in depth first order. You can trace from the end node to the root node for undirected graphs, but not for directed graph because directed arcs only support traversal in one direction.
• Example 5 traces nodes and arcs from the end node in breadth first order. You can trace from the end node to the root node for undirected graphs, and just as described in Example 4, not for directed graph because directed arcs only support traversal in one direction.
• Example 6 lines up the example graph.

Now that we know how to handle the details of node and arc construction by sending messages to the model, the next section will create an interface for graph manipulation.