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'.
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.