🚀 go-pugleaf

Grapher is a Smalltalk tool to display data structures.  The
distribution consists of two parts: PART 1 contains the files README
and Grapher-2.st, PART 2 has only the file Grapher-1.st.  See
the README file for further information.

------------------------------ README ------------------------------

Introduction

Grapher is a tool which attempts to provide a general yet simple mechanism
for viewing and interacting with Smalltalk data structures.  It is especially
well suited for directed acyclic graphs.  It should be able to handle cyclic
graphs but this has not been extensively tested and the resultant lay out of
the graph would probably be non-optimal.  Grapher is a generic name which
includes these classes: GraphNode, EmptyGraphNode, GraphHolder,
GraphHolderView, and GraphHolderController.

Interaction occurs via the mouse.  An element (node) of the graph may be
selected with the mouse, and sent messages chosen from a menu of options
recognized by the elements of the graph.

Graphs consist of labeled nodes (which correspond to Smalltalk objects; the
objects are referred to as elements) and unlabeled arcs.  The arcs are drawn
as straight lines without arrowheads.  The label of the node may be an
instance of either Text or Form.  An instance of GraphHolder contains a
collection of GraphNodes.  There is one GraphNode for every node in the graph.

It is, perhaps, a bit presumptuous to call this tool Grapher.  The original
Grapher is supplied with Xerox Lisp machines.  It has several features not
available in this implementation.  The two most noticeable extra features are
the ability to interactively edit graphs and the ability to lay out more
general kinds of graphs.

Grapher is known to work with the Tektronix 4400 series machines.  It
probably will not work with Version 1 Smalltalk-80 images (e.g. Apple
Macintosh Smalltalk: class ActionMenu needs to be defined).  No claims 
are made as to whether it will work with any other Smalltalk images.


Use

First, the simple cases, applicable for DAGs.  A Graph of a forest of DAGs
can be easily created by sending GraphHolder class the message
'createForestWithRoots:' with an argument which a Collection of elements that
are the roots of the DAGs.  This will create a GraphNode for each element of
the graph and return a properly initialized instance of GraphHolder.
A special case for creating a graph of a tree is available via
'createTreeWithRoot:'.  The GraphHolder returned by either is suitable
for use as a model in a GraphHolderView.

To create a scrollable, resizable view of a DAG send GraphHolderView class the
message 'openOn: roots label: string'.  This creates a forest, as above, lays
out the graph in horizontal format, and opens a new window on it. There are
other, similar messages which allow the specification of graph format, menu,
etc.  The elements in roots and all their subnodes must respond to messages
requesting their children, and their label.  The default message selectors
are 'children' and 'graphLabel'.  'children' must return a Collection of child
nodes, or an empty collection if none.  'graphLabel' must return a Text 
or Form to be used as the label of the node in the Graph.  These message
selectors may be changed by including the desired selector as an argument to
'openOn: roots label: labelString format: formatSymbols menu: actionMenu
childrenMsg: children labelMsg: graphLabel'.

That last message selector included a couple other parameters of interest.
'formatSymbols' is an Array of Symbols which control the format of the graph.
Currently recognized symbols are:

		#horizontal		the default, left to right
		#vertical		top to bottom
		#reverse		right to left, or bottom to top

Note that #horizontal and #vertical are mutually exclusive, but both can be
combined with #reverse.  A 'formatSymbols' of #( vertical reverse ) results
in a Graph which looks like a true tree: the root is at the bottom.

The other parameter is 'actionMenu'.  If 'actionMenu' is non-nil the window
becomes sensitive to mouse clicks.  The red button can be used to select an
element of the graph, then the yellow button will activate 'actionMenu'.  The
menu selection message will be sent to the object which the node of the tree
represents.  Note that there will be two different menus:  if no selection
has been made the default window menu will be present on the yellow button,
but if a selection has been made then the 'actionMenu' will be the menu
used by the yellow button.

To create a GraphHolder without tying it to a particular view send
GraphHolder class the message 'createForestWithRoots: roots' or
'createTreeWithRoot: root'.  These methods return a properly initialized
instance of GraphHolder which then may be used as a model for a
GraphHolderView.  The GraphHolder will need to be laid out by
sending it the message 'layout: formatSymbols' where 'formatSymbols'
is the same as for GraphHolderView.

It is not necessary to use the supplied routines for initializing a
GraphHolder. It is only required that the GraphHolder be given a
Collection of GraphNodes (via 'GraphHolder.graphNodes:').  Each GraphNode
must have its 'object' and 'to' fields initialized.  The 'object'
field is a pointer to the object represented by the GraphNode.  The
'to' field points to the objects (not the GraphNodes) which are
the children of the node.  These fields are initialized by the
'GraphNode.to: toObjects object: myObject' method.

Occasionally it is necessary to create a graph with no nodes in it. To
do so send GraphHolder class the message 'createEmpty'.  It returns a
GrapherHolder with one EmptyGraphNode in it.  The message 'isEmpty'
test a GraphHolder: it returns true if graph has one EmptyGraphNode in
it, false otherwise.  'GraphHolderView.erase' has an example of how
an empty graph may be used.


Default Menu

The default yellow (middle) button menu for a GraphHolderView window
contains two items.  `inspect' opens a model-view-controller
inspector on the GraphHolderView.  This option is provided mostly for
debugging Grapher, but can be used to get a handle on the objects
which make up the graph.  The other option is `file out' which
doesn't quite work yet.  It is intended to produce PostScript code,
and it does, which will cause the graph to be replicated on the
Laser Writer.  The PostScript is almost correct when I preview it on
a Magnolia but nothing comes out when I send it to the Laser Writer.
A rather long file of predefined PostScript code is required to make
this work; see me if you want a copy.  It also requires
'WriteStream.lf' to be defined.

Note that this menu is not available when an 'actionMenu' has been
specified and a node has been selected.


Installation

Grapher is distributed as a set of files (all of which have
lf's, not cr's, as line terminators): Grapher-1.st, Grapher-2.st,
and README.  The first two are Smalltalk source code files,
the third is this documentation file.  It should be possible to
simply file-in Grapher-1.st and Grapher-2.st to install Grapher.
GrapherHolder class has two examples. The examples each create a
GraphHolderView on a portion of the Smalltalk inheritance hierarchy.


Acknowledgements

Steve Messick wrote the first version of Smalltalk Grapher in March, 1986.
It was based on the Grapher LispUsers package in Interlisp-D (but with
much less functionallity).  Chris Jacobsen provided most of the extensions
and bug fixes which result in the current version.  In particular he
introduced empty and replaceable GraphHolders, and got Forms to work as
the label of a GraphNode. Thanks to Roxie Rochet and Brian Phillips
for helping to test the earlier version of Grapher.


Known Bugs

	o Scrolling is off-by-2.  The right and bottom edges may
	  have a 2 bit wide strip which does not get cleared if
	  the graph is scrolled to far left or far top.

	o Scrolling horizontally is not continuous on the 4400's,
	  but vertical scrolling is.

Problems, questions, and/or suggestions should be directed
to Steve Messick, CRL, Tek Labs (messick%tekcrl@tektronix.csnet),
or to Chris Jacobson (chrisj%tekcrl@tektronix.csnet). Of particular
interest are any extensions, bug fixes, or other modifications to
the code.

------------------------------ Grapher-2.st ------------------------------

DisplayObject subclass: #GraphHolder
	instanceVariableNames: 'nodes virtualNodes roots directed sides delta form offset boundingBox '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Grapher'!
GraphHolder comment:
'A GraphHolder provides the global organization required to present a structured, graphical display of a data structure.  GraphHolders may be created with the createTreeWithRoot: or createForestWithRoots: messages in GraphHolder metaclass, or by the openOn:label: message of GraphHolderView metaclass.  Also, it is possible, but not easy, to use routines external to GraphHolder to create a graph.  After a graph has been created it must have its elements positioned properly.  The message layout: does this.  I



ts argument is an Array of formatting symbols, which specify the various format options which are in effect for this GraphHolder.  The format symbols currently recognized are:

	#horizontal		The default.  GraphHolders have roots to the left,
					leaves to the right.
	#vertical		Roots at top, leaves at bottom.
	#reverse		Either right-left, or bottom-top.

My instance variables:

	nodes		<Dictionary from Object to GraphNode>
				The nodes which make up a GraphHolder.
	virtualNodes <Dictionary from Object to Sets of GraphNode>
				Nodes with multiple ''from'' fields are replicated here.
	roots		<Collection of Object>
				The distinguished nodes which are the roots of a DAG.
	directed	<Boolean>
				If true, I am a directed graph and links are fixed (e.g.
				from bottom of a label to top of a child label).
				If false, links may originate at whichever edge of
				the label is convenient (modulo the value of sides).
	sides		<Boolean>
				If true, links are drawn to the left or right of a node.
				If false, links are drawn to the top or bottom of a node.
	delta		<Point>
				The minimum distances between node labels. The x
				value specifies the distance between parent/child.  The
				y value, adjacent children.
	form		<Form or GraphHolder>
				The object to be displayed.  If the display fits on a form
				then a form is created and saved here.  Otherwise this
				is a pointer back to the GraphHolder.  Only used for display.
	offset		<Point>
				My display offset (in local view coordinates).
	boundingBox <Rectangle>
				A rectangle large enough to hold my entire graphical
				display, positioned in local view coordinates.

Currently, my sides and directed flags are unused.  They are provided for compatability with future versions of Grapher which may support more generalized layout options.

File out Grapher:

	| sourceStream |
	sourceStream _ Disk file: ''Grapher-1.st'' asFileName.
	#(XAxisScrollController GraphHolderController GraphHolderView) do:
		[ :className |
		(Smalltalk at: className) fileOutOn: sourceStream].
	sourceStream nextChunkPut:
''#(''''FourWay'''' ''''LeftCursor'''' ''''RightCursor'''' ''''XMarkerCursor'''') do:
	[ :var | Cursor addClassVarName: var].''; cr.
	#(fourWay left right xMarker initialize) do:
		[ :selector |
		Cursor class fileOutMessage: selector on: sourceStream moveSource: false toFile: 0].
	sourceStream nextChunkPut: ''Cursor initialize.''; cr.
	sourceStream close.

	| sourceStream |
	sourceStream _ Disk file: ''Grapher-2.st'' asFileName.
	#(GraphHolder GraphNode EmptyGraphNode) do:
		[ :className |
		(Smalltalk at: className) fileOutOn: sourceStream].
	Object fileOutCategory: ''grapher access'' asSymbol on: sourceStream moveSource: false toFile: 0.
	sourceStream close.
'!


!GraphHolder methodsFor: 'initialize-release'!

initialize

	sides _ true.
	directed _ true.
	offset _ 0@0!

release

	form _ nil! !


!GraphHolder methodsFor: 'accessing'!

directed
	^directed!

directed: aBool
	directed _ aBool!

form

	form == nil
		ifTrue: [self composeForm].
	^form!

nodes
	^nodes!

offset
	^offset!

offset: aPoint
	offset _ aPoint!

roots

	"Chris Jacobson 7-9-86"
	^roots!

selectNodeAt: selectionPoint

	| selection |
	selection _ nodes detect: [ :node | node containsPoint: selectionPoint]
					   ifNone: [nil].
	selection == nil & (virtualNodes ~= nil) ifTrue:
		[virtualNodes do:
			[ :group |
			selection _ group detect: [ :node | node containsPoint: selectionPoint]
							   ifNone: [nil].
			selection == nil
				ifFalse: [^selection]]].
	^selection!

sides
	^sides!

sides: aBool
	sides _ aBool! !


!GraphHolder methodsFor: 'testing'!

isEmpty

	^(nodes size = 1) and: [nodes keysDo: [:node | ^node class == EmptyGraphNode]]! !


!GraphHolder methodsFor: 'display box access'!

boundingBox

	boundingBox == nil
		ifTrue: [boundingBox _ self computeBoundingBox].
	^boundingBox!

computeBoundingBox

	self layout.
	^boundingBox! !


!GraphHolder methodsFor: 'displaying'!

displayOn: aDisplayMedium at: aDisplayPoint clippingBox: clipRectangle rule: ruleInteger mask: aForm

	| displayPoint blter |
	displayPoint _ aDisplayPoint + offset.
	blter _ BitBlt
		destForm: aDisplayMedium
		sourceForm: (Form extent: 1@1) black
		halftoneForm: aForm
		combinationRule: ruleInteger
		destOrigin: 0@0
		sourceOrigin: 0@0
		extent: 1@1
		clipRect: clipRectangle.
	nodes do:
		[ :node |
		node to do:
			[ :child |
			blter drawFrom: displayPoint + node fromPt
				  to: displayPoint + child toPt]].
	nodes do:
		[ :node |
		node
			displayOn: aDisplayMedium
			at: displayPoint
			clippingBox: clipRectangle
			rule: ruleInteger
			mask: aForm].
	virtualNodes == nil ifFalse:
		[virtualNodes do:
			[ :share | share do:
				[ :node |
				node			
					displayOn: aDisplayMedium
					at: displayPoint
					clippingBox: clipRectangle
					rule: ruleInteger
					mask: aForm]]]!

displayOn: aDisplayMedium transformation: aDisplayTransformation clippingBox: aRectangle rule: ruleInteger mask: aHalfTone

	self form
		displayOn: aDisplayMedium
		transformation: aDisplayTransformation
		clippingBox: aRectangle
		rule: ruleInteger
		mask: aHalfTone!

view

	self displayOn: self form at: 0@0.
	form openAs: 
		(roots size = 1
			ifTrue: ['Tree']
			ifFalse: ['Forest'])! !


!GraphHolder methodsFor: 'graph layout'!

layout
	"Default format."

	self layout: #( #horizontal )!

layout: format

	| messages realOffset extents max horizontal |
	delta == nil ifTrue: [delta _ 30@30].
	messages _ (nodes at: roots first) formatMessages: format.
	horizontal _ format includes: #horizontal.
	realOffset _ offset copy.
	extents _ OrderedCollection new: roots size.
	max _ 0.
	roots do:
		[ :root |
		extents addLast:
			((nodes at: root) extentOfGraph: self
							  withDelta: delta
							  formatMessages: (messages at: 1))].
	1 to: roots size do:
		[ :n |
		(nodes at: (roots at: n))
			setPosition: offset
			withDelta: delta
			forGraph: self
			formatMessages: (messages at: 2).
		horizontal
			ifTrue: [max _ max max: (extents at: n) x.
					offset y: offset y + (extents at: n) y + delta y]
			ifFalse: [max _ max max: (extents at: n) y.
					offset x: offset x + (extents at: n) x + delta x]].
	horizontal
		ifTrue: [boundingBox _ 0@0 extent: (max + delta x @ offset y).
				offset _ realOffset.
				offset x: offset x + (delta x // 2)]
		ifFalse: [boundingBox _ 0@0 extent: offset x @ (max + delta y).
				offset _ realOffset.
				offset y: offset y + (delta y // 2)]! !


!GraphHolder methodsFor: 'graph setup'!

addNode: newNode
	"Add a 'virtual' node to the graph.  Virtual nodes have no children;
	they serve as markers for nodes with multiple from nodes."

	virtualNodes == nil ifTrue: [virtualNodes _ IdentityDictionary new: 16].
	(virtualNodes at: newNode object
		   ifAbsent: [virtualNodes at: newNode object put: (OrderedCollection new: 5)])
		addLast: newNode!

forestFrom: rootObjs children: childrenMsg label: labelMsg

	| index |
	nodes _ IdentityDictionary new: 64.
	roots _ Array new: rootObjs size.
	index _ 1.
	rootObjs do:
		[ :root |
		roots at: index put: root.
		index _ index + 1.
		self newGraphNode: root
			fromNode: nil
			children: childrenMsg
			label: labelMsg]!

newGraphNode: nodeObj fromNode: fromNode children: childrenMsg label: labelMsg
	"Add another graphNode (for nodeObj) to the graph.  Its
	immediate parent is fromNode. 'Ware circularities!!"

	| graphNode toNodes children |
	graphNode _ nodes at: nodeObj ifAbsent:
		[graphNode _ GraphNode from: fromNode
								   object: nodeObj
								   label: (nodeObj perform: labelMsg).
		children _ nodeObj perform: childrenMsg.
		toNodes _ OrderedCollection new: children size.
		children do:
			[ :child |
			toNodes addLast: (self newGraphNode: child
									fromNode: graphNode
									children: childrenMsg
									label: labelMsg)].
		graphNode to: toNodes asArray.
		nodes at: nodeObj put: graphNode.
		^graphNode].
	graphNode addFromNode: fromNode.
	^graphNode! !


!GraphHolder methodsFor: 'graph hardcopy'!

psEpilogueOn: aStream

	aStream lf!

psLine: beginPt to: endPt on: aStream

	beginPt x printOn: aStream.
	aStream space.
	beginPt y printOn: aStream.
	aStream space.
	endPt x printOn: aStream.
	aStream space.
	endPt y printOn: aStream.
	aStream space; nextPutAll: 'Line'; lf!

psPrologueOn: aStream

	aStream lf.
	offset x negated printOn: aStream.
	aStream space.
	offset y negated printOn: aStream.
	aStream space.
	boundingBox extent x printOn: aStream.
	aStream space.
	boundingBox extent y printOn: aStream.
	aStream space; nextPutAll: 'SetPage'; lf!

psScriptOn: aStream

	nodes do:
		[ :node |
		node to do:
			[ :child |
			self psLine: node fromPt to: child toPt on: aStream ]].
	nodes do:
		[ :node |
		node psStoreOn: aStream ].
	virtualNodes == nil ifFalse:
		[virtualNodes do:
			[ :share |
			share do:
				[ :node |
				node boxYourself.		"workaround for a slight glitch"
				node psStoreOn: aStream ]]]!

psStoreOn: aStream
	"Store the PostScript code to reproduce me on aStream.  This set of
	methods requires some external PostScript definitions for SetPage,
	Box, Line, and Label."

	self psPrologueOn: aStream.
	self psScriptOn: aStream.
	self psEpilogueOn: aStream! !


!GraphHolder methodsFor: 'private'!

composeForm

	self boundingBox extent x +15 // 16
	* self boundingBox extent y > WordArray maxSize
		ifFalse: [form _ Form extent: self boundingBox extent.
				self displayOn: form at: 0@0.
				self changed: #form]
		ifTrue: [form _ self.
				self changed: #noform]! !

"-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "!

GraphHolder class
	instanceVariableNames: ''!


!GraphHolder class methodsFor: 'instance creation'!

createEmpty

	^self createTreeWithRoot: (EmptyGraphNode new)!

createForestWithRoots: objs

	^self createForestWithRoots: objs children: #children label: #graphLabel!

createForestWithRoots: objs children: childrenMsg label: labelMsg
	"Create a forest rooted at objs.  Use the message selector in
	childrenMsg to get the children of node.  Use the selector in
	labelMsg to get the label of a node."

	^self new forestFrom: objs children: childrenMsg label: labelMsg!

createTreeWithRoot: obj

	^self createForestWithRoots: (Array with: obj)!

new
	^super new initialize! !


!GraphHolder class methodsFor: 'examples'!

example1
	"If 'children' and 'graphLabel' have been defined in Object then
	display the inheritance heirarchy for Number."

	GraphHolderView openOn: (Array with: Number)
				label: 'Number'
				format: #( #vertical #reverse )

	"GraphHolder example1"

	"definition of children for Object"
"children
	^self subclasses"

	"definition of graphLabel for Object"
"graphLabel
	^self name asText"!

example2
	"If 'children' and 'graphLabel' have been defined in Object then
	display the inheritance heirarchies for View and Controller.
	This example is interesting because the space required to display
	the resulting forest is too large to fit into an instance of Form.
	(At least, it's too big for a 16-bit interpreter.)"

	GraphHolderView openOn: (Array with: View with: Controller)
				label: 'Windows'

	"GraphHolder example2"! !
DisplayText subclass: #GraphNode
	instanceVariableNames: 'object from to fromPt toPt boxed '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Grapher'!
GraphNode comment:
'My instance variables:

	object		<Object>
				Reference to the object which I am to display.
	from		<Array of Integer>
				A list of GraphNode id''s. A link fruns from each node
				in this list to me.
	to			<Array of Integer>
				A list of GraphNode id''s. A link fruns from me to each
				node in this list.
	fromPt		<Point>
				The location (wrt offset) on my form where my to
				links begin.
	toPt		<Point>
				The location (wrt offset) on my form where my from
				links end.
	boxed		<Boolean>
				If true, a box is to drawn around my form.  Only valid
				for ''real'' nodes (ie those GraphNodes in the nodes
				field of GraphHolder, not the virtualNodes field).
'!


!GraphNode methodsFor: 'initialize-release'!

initialize

	boxed _ false! !


!GraphNode methodsFor: 'accessing'!

from
	^from!

from: fromNodes
	from _ fromNodes!

fromPt
	^fromPt!

object
	^object!

to
	^to!

to: toNodes
	to _ toNodes!

toPt
	^toPt!

visited
	"Boxed is used as a temporary indicator: it is set to true
	during pass one, then false in pass two.  Shared nodes
	remain true."

	^toPt ~= nil and: [to size > 0]! !


!GraphNode methodsFor: 'testing'!

containsPoint: aPoint

	^(Rectangle origin: offset extent: form boundingBox extent)
		containsPoint: aPoint! !


!GraphNode methodsFor: 'editing'!

addFromNode: new

	from _ from copyWith: new!

addToNode: new

	to _ to copyWith: new!

boxYourself

	| newForm |
	boxed
		ifTrue: [^self].
	form border: form boundingBox width: 1.
	boxed _ true!

deleteFromNode: old

	from _ from copyWithout: old!

deleteToNode: old

	to _ to copyWithout: old! !


!GraphNode methodsFor: 'display box access'!

bottomCenter

	^self form boundingBox bottomCenter + offset!

boundingBox
	^self form boundingBox!

leftCenter

	^self form boundingBox leftCenter + offset!

origin

	^self form boundingBox origin + offset!

rightCenter

	^self form boundingBox rightCenter + offset!

topCenter

	^self form boundingBox topCenter + offset! !


!GraphNode methodsFor: 'graph layout'!

extentOfGraph: graph withDelta: delta formatMessages: msgs
	"Determine the extent of the rectangular area required
	to hold the subtree of which I am the root.  Save the extent
	temporarily in offset (till we get to setPosition:...)."

	| boundingBox labelBox updateMsg childExtent |
	labelBox _ self boundingBox.
	boxed ifTrue:
		[^self perform: (msgs at: 1) with: labelBox extent with: delta].
	to size = 0 ifTrue:
		[^offset _ self perform: (msgs at: 1) with: labelBox extent with: delta].
	boxed _ true.
	updateMsg _ msgs at: 2.
	to do:
		[ :child |
		childExtent _ child extentOfGraph: graph
							withDelta: delta
							formatMessages: msgs.
		self perform: updateMsg with: childExtent].
	self perform: (msgs at: 3) with: labelBox extent with: delta.
	^offset!

formatMessages: format

	(format includes: #vertical)
		ifTrue:
			[(format includes: #reverse)
				ifTrue: [^self reverseVerticalFormat]
				ifFalse: [^self verticalFormat]].
	(format includes: #horizontal)
		ifTrue:
			[(format includes: #reverse)
				ifTrue: [^self reverseHorizontalFormat]
				ifFalse: [^self horizontalFormat]].
	self error: 'Unknown graph format.'!

horizontalFormat

	^Array
		with:
			#(	#horizExtent:with:
				#horizAdjustOffset:
				#horizAddLabel:with: )
		with:
			#(	#leftCenter
				#horizWidth:with:
				#horizFixedSubOrigin:with:with:
				#horizVariableSubOrigin:
				#horizNewSubOrigin:with: )!

reverseHorizontalFormat

	^Array
		with:
			#(	#horizExtent:with:
				#horizAdjustOffset:
				#horizAddLabel:with: )
		with:
			#(	#rightCenter
				#horizWidth:with:
				#revHorizFixedSubOrigin:with:with:
				#horizVariableSubOrigin:
				#horizNewSubOrigin:with: )!

reverseVerticalFormat

	^Array
		with:
			#(	#vertExtent:with:
				#vertAdjustOffset:
				#vertAddLabel:with: )
		with:
			#(	#bottomCenter
				#vertWidth:with:
				#revVertFixedSubOrigin:with:with:
				#vertVariableSubOrigin:
				#vertNewSubOrigin:with: )!

setPosition: origin withDelta: delta forGraph: graph formatMessages: msgs
	"Allocate space for each of my children side-by-side and
	assign a value to offset which results in my form being appropriately
	centered in my display rectangle."

	| area labelBox x d w child |
	labelBox _ self boundingBox.
	area _ origin extent: offset.
	offset _ 0@0.
	boxed _ false.
	to size = 0 ifTrue:
		[self align: (labelBox perform: (msgs at: 1))
			  with: (area perform: (msgs at: 1)).
		toPt _ offset + (labelBox perform: (msgs at: 1)).
		^self perform: (msgs at: 2) with: labelBox extent with: delta].
	self align: (labelBox perform: (msgs at: 1))
		with: (area perform: (msgs at: 1)).
	toPt _ offset + (labelBox perform: (msgs at: 1)).
	fromPt _ offset + (labelBox perform: (self oppositeCenter: (msgs at: 1))).
	x _ self perform: (msgs at: 3)
			with: area
			with: labelBox extent
			with: delta.
	w _ 0.
	d _ self perform: (msgs at: 4) with: area origin.
	1 to: to size do:
		[ :n |
		child _ to at: n.
		child visited ifTrue:
			[child boxYourself.
			child _ child copy.
			child offset: child boundingBox extent + delta.
			child to: Array new.
			graph addNode: child.
			to at: n put: child].
		w _ w + (child setPosition: (self perform: (msgs at: 5)
										  with: x
										  with: d+w)
						withDelta: delta
						forGraph: graph
						formatMessages: msgs)].
	^w!

verticalFormat

	^Array
		with:
			#(	#vertExtent:with:
				#vertAdjustOffset:
				#vertAddLabel:with: )
		with:
			#(	#topCenter
				#vertWidth:with:
				#vertFixedSubOrigin:with:with:
				#vertVariableSubOrigin:
				#vertNewSubOrigin:with: )! !


!GraphNode methodsFor: 'graph formating'!

horizAddLabel: labelExtent with: delta
	"This message belongs in position 3 of extentOfGraph:"

	offset y: (offset y max: (labelExtent y + delta y)).
	offset x: offset x + labelExtent x + delta x!

horizAdjustOffset: subExtent
	"This message belongs in position 2 of extentOfGraph:"

	offset y: offset y + subExtent y.
	offset x: (offset x max: subExtent x)!

horizExtent: extent with: delta
	"This message belongs in position 1 for extentOfGraph:"

	^extent + (0 @ delta y)!

horizFixedSubOrigin: area with: extent with: delta
	"This message belongs in position 3 of extentOfGraph:"

	^area origin x + extent x + delta x!

horizNewSubOrigin: x with: y
	"This message belongs in position 5 of extentOfGraph:"

	^x @ y!

horizVariableSubOrigin: origin
	"This message belongs in position 4 of extentOfGraph:"

	^origin y!

horizWidth: extent with: delta
	"This message belongs in position 2 of setPosition:
	(Note that a message in Rectangle goes in position 1)"

	^extent y + delta y!

oppositeCenter: aSymbol

	aSymbol == #topCenter ifTrue: [^#bottomCenter].
	aSymbol == #leftCenter ifTrue: [^#rightCenter].
	aSymbol == #bottomCenter ifTrue: [^#topCenter].
	aSymbol == #rightCenter ifTrue: [^#leftCenter]!

revHorizFixedSubOrigin: area with: extent with: delta
	"This message belongs in position 3 of extentOfGraph:"

	^area origin x!

revVertFixedSubOrigin: area with: extent with: delta
	"This message belongs in position 3 of extentOfGraph:"

	^area origin y!

vertAddLabel: labelExtent with: delta
	"This message belongs in position 3 of extentOfGraph:"

	offset x: (offset x max: (labelExtent x + delta x)).
	offset y: offset y + labelExtent y + delta y!

vertAdjustOffset: subExtent
	"This message belongs in position 2 of extentOfGraph:"

	offset x: offset x + subExtent x.
	offset y: (offset y max: subExtent y)!

vertExtent: extent with: delta
	"This message belongs in position 1 for extentOfGraph:"

	^extent + (delta x @ 0)!

vertFixedSubOrigin: area with: extent with: delta
	"This message belongs in position 3 of extentOfGraph:"

	^area origin y + extent y + delta y!

vertNewSubOrigin: y with: x
	"This message belongs in position 5 of extentOfGraph:"

	^x @ y!

vertVariableSubOrigin: origin
	"This message belongs in position 4 of extentOfGraph:"

	^origin x!

vertWidth: extent with: delta
	"This message belongs in position 2 of setPosition:
	(Note that a message in Rectangle goes in position 1)"

	^extent x + delta x! !


!GraphNode methodsFor: 'graph hardcopy'!

psStoreOn: aStream

	| insetBox |
	insetBox _ (offset extent: self form boundingBox extent) insetBy: 2@2.
	boxed ifTrue:
		[offset x printOn: aStream.
		aStream space.
		offset y printOn: aStream.
		aStream space.
		insetBox corner x + 2 printOn: aStream.
		aStream space.
		insetBox corner y + 2 printOn: aStream.
		aStream space; nextPutAll: 'Box'; lf].
	insetBox origin x printOn: aStream.
	aStream space.
	insetBox origin y printOn: aStream.
	aStream space; nextPut: $(; nextPutAll: text string; nextPut: $);
		space; nextPutAll: 'Label'; lf.! !


!GraphNode methodsFor: 'private'!

composeForm

	| newForm |

	super composeForm.
	newForm _ Form extent: form boundingBox extent + (4@4).
	newForm white.
	form displayOn: newForm at: 2@2.
	form _ newForm!

from: fromNodes to: toNodes object: myObject label: label

	from _ fromNodes.
	to _ toNodes.
	object _ myObject.
	(label isKindOf: DisplayObject)
		ifTrue: [form _ label.
				offset _ 0@0]
		ifFalse: [self setText: label asText
				textStyle: DefaultTextStyle copy
				offset: 0@0]! !

"-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "!

GraphNode class
	instanceVariableNames: ''!


!GraphNode class methodsFor: 'instance creation'!

from: fromID object: obj

	^self from: (Array with: fromID) to: nil object: obj label: obj graphLabel!

from: fromID object: obj label: graphLabel

	^self from: (Array with: fromID) to: nil object: obj label: graphLabel!

from: fromIDs to: toIDs object: obj

	^self from: fromIDs to: toIDs object: obj label: obj graphLabel!

from: fromIDs to: toIDs object: obj label: label

	^self new from: fromIDs to: toIDs object: obj label: label!

new
	^super new initialize!

to: toID object: obj

	^self from: nil to: (Array with: toID) object: obj label: obj graphLabel! !
Object subclass: #EmptyGraphNode
	instanceVariableNames: 'graphLabel children '
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Grapher'!


!EmptyGraphNode methodsFor: 'accessing'!

children

	^children!

graphLabel

	^graphLabel! !


!EmptyGraphNode methodsFor: 'initialize'!

initialize

	graphLabel _ (Form dotOfSize: 0).
	children _ #()! !

"-- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- "!

EmptyGraphNode class
	instanceVariableNames: ''!


!EmptyGraphNode class methodsFor: 'instance creation'!

new

	^super new initialize! !


!Object methodsFor: 'grapher access'!

children
	^self subclasses!

graphLabel
	^self name asText! !