home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
BURKS 2
/
BURKS_AUG97.ISO
/
BURKS
/
LANGUAGE
/
SMALTALK
/
TEXTBOOK
/
AP27.ST
(
.txt
)
< prev
next >
Wrap
Text File
|
1997-04-22
|
15KB
|
531 lines
'Smalltalk Textbook Appendix 27'!
EngiGeometric subclass: #EngiGraph
instanceVariableNames: 'graphVertices graphBranches graphQueue arrangeFormat '
classVariableNames: ''
poolDictionaries: ''
category: 'Engi-Graph'!
EngiGraph comment:
'
Engi 0.07 (24 March 1994)
Copyright (C) 1994 by Atsushi Aoki
'!
!EngiGraph methodsFor: 'initialize-release'!
initialize
super initialize.
graphVertices := OrderedCollection new.
graphBranches := OrderedCollection new.
^self! !
!EngiGraph methodsFor: 'testing'!
isDirectedGraph
^false!
isUndirectedGraph
^false! !
!EngiGraph methodsFor: 'bounds accessing'!
computeBounds
| bounds |
bounds := nil.
self doVertices: [:vertex | bounds isNil
ifTrue: [bounds := vertex bounds]
ifFalse: [bounds := bounds merge: vertex bounds]].
self doBranches: [:branch | bounds isNil
ifTrue: [bounds := branch bounds]
ifFalse: [bounds := bounds merge: branch bounds]].
bounds isNil ifTrue: [bounds := Point zero corner: Point zero].
bounds := bounds rounded.
^bounds! !
!EngiGraph methodsFor: 'vertex accessing'!
addVertex: aVertex
(self includesVertex: aVertex)
ifFalse:
[graphVertices addLast: aVertex.
self flushBounds.
^aVertex].
^nil!
atVertex: anInteger
^graphVertices at: anInteger!
connectedVertices: aVertex
^(self connectedBranches: aVertex)
collect: [:aBranch | aBranch endVertex]!
doVertices: aBlock
graphVertices do: [:vertex | aBlock value: vertex]!
doVerticesBreadthFirst: aBlock
self visitBreadthFirstVertexDo: [:vertex | aBlock value: vertex]
branchDo: [:branch | ]!
doVerticesDepthFirst: aBlock
self visitDepthFirstVertexDo: [:vertex | aBlock value: vertex]
branchDo: [:branch | ]!
includesVertex: aVertex
self doVertices: [:vertex | vertex = aVertex ifTrue: [^true]].
^false!
removeVertex: aVertex
| vertex |
(self includesVertex: aVertex)
ifTrue:
[vertex := graphVertices remove: aVertex.
self flushBounds.
^vertex].
^nil!
sizeOfVertices
^graphVertices size!
verticesBreadthFirst
| vertices |
vertices := OrderedCollection new.
self doVerticesBreadthFirst: [:vertex | vertices add: vertex].
^vertices!
verticesDepthFirst
| vertices |
vertices := OrderedCollection new.
self doVerticesDepthFirst: [:vertex | vertices add: vertex].
^vertices! !
!EngiGraph methodsFor: 'branch accessing'!
addBranch: aBranch
(self includesBranch: aBranch)
ifFalse:
[graphBranches addLast: aBranch.
self flushBounds.
^aBranch].
^nil!
atBranch: anInteger
^graphBranches at: anInteger!
branchesBreadthFirst
| branches |
branches := OrderedCollection new.
self doBranchesBreadthFirst: [:branch | branches add: branch].
^branches!
branchesDepthFirst
| branches |
branches := OrderedCollection new.
self doBranchesDepthFirst: [:branch | branches add: branch].
^branches!
connectedBranches: aVertex
| connectedBranches |
connectedBranches := OrderedCollection new.
self doBranches: [:aBranch | aBranch startVertex = aVertex ifTrue: [(connectedBranches includes: aBranch)
ifFalse: [connectedBranches add: aBranch]]].
^connectedBranches!
doBranches: aBlock
graphBranches do: [:branch | aBlock value: branch]!
doBranchesBreadthFirst: aBlock
self visitBreadthFirstVertexDo: [:vertex | ]
branchDo: [:branch | aBlock value: branch]!
doBranchesDepthFirst: aBlock
self visitDepthFirstVertexDo: [:vertex | ]
branchDo: [:branch | aBlock value: branch]!
includesBranch: aBranch
self doBranches: [:branch | (branch startVertex = aBranch startVertex and: [branch endVertex = aBranch endVertex])
ifTrue: [^true]].
^false!
removeBranch: aBranch
(self includesBranch: aBranch)
ifTrue: [graphBranches reverse do: [:branch | (branch startVertex = aBranch startVertex and: [branch endVertex = aBranch endVertex])
ifTrue:
[graphBranches remove: branch.
self flushBounds.
^branch]]].
^nil!
sizeOfBranches
^graphBranches size! !
!EngiGraph methodsFor: 'transforming'!
rotatedBy: angleDegree
self doVertices: [:vertex | vertex rotatedBy: angleDegree].
self doBranches: [:branch | branch rotatedBy: angleDegree].
self flushBounds!
scaledBy: scalePoint
self doVertices: [:vertex | vertex scaledBy: scalePoint].
self doBranches: [:branch | branch scaledBy: scalePoint].
self flushBounds!
translatedBy: amountPoint
self doVertices: [:vertex | vertex translatedBy: amountPoint].
self doBranches: [:branch | branch translatedBy: amountPoint].
self flushBounds! !
!EngiGraph methodsFor: 'displaying'!
displayFilledOn: graphicsContext at: aPoint
^self!
displayStrokedOn: graphicsContext at: aPoint
self doBranches: [:branch | branch displayOn: graphicsContext at: aPoint].
self doVertices: [:vertex | vertex displayOn: graphicsContext at: aPoint]! !
!EngiGraph methodsFor: 'connecting'!
connect: startVertex with: endVertex
^self subclassResponsibility!
disconnect: startVertex with: endVertex
^self subclassResponsibility! !
!EngiGraph methodsFor: 'visiting'!
visitBreadthFirst: aVertex vertexDo: vertexBlock branchDo: branchBlock
| theVertex endVertex |
aVertex vertexState: #entered.
graphQueue add: aVertex.
[graphQueue isEmpty]
whileFalse:
[theVertex := graphQueue removeFirst.
theVertex vertexState = #visited ifFalse: [vertexBlock value: theVertex].
theVertex vertexState: #visited.
(self connectedBranches: theVertex)
do:
[:aBranch |
endVertex := aBranch endVertex.
branchBlock value: aBranch.
endVertex vertexState = #unvisited
ifTrue:
[graphQueue add: endVertex.
aVertex vertexState: #entered]]]!
visitBreadthFirstInitialize
graphQueue := OrderedCollection new.
self doVertices: [:vertex | vertex vertexState: #unvisited]!
visitBreadthFirstVertexDo: vertexBlock branchDo: branchBlock
self visitBreadthFirstInitialize.
self doVertices: [:vertex | vertex vertexState = #unvisited ifTrue: [self
visitBreadthFirst: vertex
vertexDo: vertexBlock
branchDo: branchBlock]]!
visitDepthFirst: aVertex vertexDo: vertexBlock branchDo: branchBlock
| endVertex |
aVertex vertexState = #visited ifFalse: [vertexBlock value: aVertex].
aVertex vertexState: #visited.
(self connectedBranches: aVertex)
do:
[:aBranch |
endVertex := aBranch endVertex.
branchBlock value: aBranch.
endVertex vertexState = #unvisited ifTrue: [self
visitDepthFirst: endVertex
vertexDo: vertexBlock
branchDo: branchBlock]]!
visitDepthFirstInitialize
self doVertices: [:vertex | vertex vertexState: #unvisited]!
visitDepthFirstVertexDo: vertexBlock branchDo: branchBlock
self visitDepthFirstInitialize.
self doVertices: [:vertex | vertex vertexState = #unvisited ifTrue: [self
visitDepthFirst: vertex
vertexDo: vertexBlock
branchDo: branchBlock]]! !
!EngiGraph methodsFor: 'arranging'!
arrangeBalance
^self arrangeFormat at: 4!
arrangeBalance: aSymbol
(#(#balance #unbalance ) includes: aSymbol)
ifTrue: [self arrangeFormat at: 4 put: aSymbol]!
arrangeDirection
^self arrangeFormat at: 1!
arrangeDirection: aSymbol
(#(#left #top ) includes: aSymbol)
ifTrue: [self arrangeFormat at: 1 put: aSymbol]!
arrangeFormat
arrangeFormat isNil ifTrue: [arrangeFormat := self defaultArrangeFormat].
^arrangeFormat!
arrangeInterval
^self arrangeFormat at: 2!
arrangeInterval: anInteger
self arrangeFormat at: 2 put: anInteger!
arrangeMargin
^self arrangeFormat at: 3!
arrangeMargin: anInteger
self arrangeFormat at: 3 put: anInteger!
arrangeRoots
| exceptions roots |
exceptions := OrderedCollection new.
self doBranches: [:branch | exceptions add: branch endVertex].
roots := OrderedCollection new.
self doVertices: [:vertex | (exceptions includes: vertex)
ifFalse: [roots add: vertex]].
(roots isEmpty and: [self sizeOfVertices > 0])
ifTrue: [roots add: (self atVertex: 1)].
^roots!
arrangeScan
| origin delata |
origin := Point zero.
self doVertices: [:vertex | vertex vertexState: #unvisited].
self arrangeRoots
do:
[:vertex |
origin := self arrangeScan: vertex xy: origin.
self arrangeDirection = #left ifTrue: [origin := origin + (0 @ self arrangeMargin)].
self arrangeDirection = #top ifTrue: [origin := origi