        Hotspots: Admin Pages | Turn-in Site |
Current Links: Cases Final Project Summer 2007

## Drawing Graphs in smalltalk - Matthew Ruge

Written by Matthew Ruge 902084666 mruge3
```As a quick review for those of you who have not had any graph theory before, lets go over some basic graphing concepts.

Vertex - a point on a graph
Edge - an edge/line connecting 2 Vertices.
Weight - the weight or distance between two Vertices, usally stored with the edge.

In order to store a graph and be able to interprate it we need some whay to store the information.  There are many methods to do this, the 2 most popular are adjacency list and edge list.

Adjacecy list - for each vertex we keep a list of all other points that are next to it.  This method requires that we either have a vertex class or a 2d arraylist.  Both of these methods are very usefull in larger programs, and bigger applications. But for what im going to show you in smalltalk, this unnecessary and overkill.

Edge list - this is merely a list of edges, i.e. 2 vertices and a weight.  This can be done with a single Array (Ordered Collection).

So now that we have the basic concepts down we can begin talking about the process.  This tutorial will cover the following steps:

1] create a usable edge list for your graph
2] create a list of points and edges to chart
3] draw the now defined points and edges to the screen (using a view)

As you may have guessed steps 1 and 3 are trivial but 2 may require some work.

for the remainder of this tutorial we will use the following graph

C
/ \
/   \
A     D----E
\   /
\ /
B

This simple graph should demostrate most of the problems we will face.

***Step 1**********Creating the edge list is done manuelly so I will just show you what it would look like

_________________
|  A  |  C  |  2  |
|_____|_____|_____|
|  A  |  B  |  2  |
|_____|_____|_____|
|  C  |  D  |  2  |
|_____|_____|_____|
|  B  |  D  |  2  |
|_____|_____|_____|
|  D  |  E  |  4  |
|_____|_____|_____|

To store this graph for use, you have multiple choices you can have an Ordered Collection of Arrays.

edgeList := OrderedCollection new.

If this were the case you would get a points adjacencies with the method I call

| tempList |
tempList = OrderedCollection new.
edgeList do: [:edge| (edge at: 1)=aPointName
ifTrue:[tempList add: (#((edge at: 2),(edge at: 3)))]
ifFalse:[ (edge at: 2)=aPointName
ifTrue:[tempList add: (#((edge at: 1),(edge at: 3)))]
].
].
^tempList

So if you call getAdj: 'B'.
you will get and OrderedCollection containing #(('A',2),('D',2))
which as you can see are the adjacencies to B and the distance to them.

You could also store your edge list in other ways.  My favorite and the the choice I used for my Oregon Trail project, was a Database.  With this method you can get the same adjacencies result with a simple SQL query.  But that is a much different topic, so we will stick with the OrderedCollection Method.

Storing the edge list can keep what seems like a large peice of Information (A Graph) relativly small).  For example we can change our graph alot by just adding one linke to our list.

_________________
|  A  |  C  |  2  |
|_____|_____|_____|
|  A  |  B  |  2  |
|_____|_____|_____|
|  C  |  D  |  2  |
|_____|_____|_____|
|  B  |  D  |  2  |
|_____|_____|_____|
|  D  |  E  |  4  |
|_____|_____|_____|
|  E  |  C  |  9  |
|_____|_____|_____|

becomes

C-------
/ \      |
/   \     |
A     D----E
\   /
\ /
B

adding three characters Just added an entirly new path in our graph.

So now we have our Edge list.  We can take on the task of figuring out how to create the drawing lists to give to the gui it.***Step 2**********

As daughnting as this task may seem it is really just a matter of simple recursion.

Supplies we need:
A toDraw Queue - simple first in first out queue
GraphPoint Class - stores x-y coordinates of a point and the name
GraphView Class - used for both steps 2 and 3, contains the methods we need.
superclass: #{UI.View}
Variables:
Edges:=OrderedCollection new.
Points:=OrderedCollectin new.
toDraw:=OrderedCollection new.
Methods:
inPoints - boolean wether or not a point is in points
inEdges - boolean wether or not a edge is already drawn

Before I get into the SmallTalk code, let me talk go over the basic PsuedoCode.

While queue.size > 0 do

Seem simple? well there are a few problems that we need to fix to that.

1. we will get stuck in an infinite loop.
A will draw C which will draw A which will draw C ... see where this is going.
We will have to add a check for this:

So the new code would be:

While queue.size > 0 do

2. How do we know where to draw the first point(x,y) or where the adj are to draw
the edge?
This is why we needed the GraphPoint Class, to keep track of the x,y coordinates of these points.
How do we decide where to draw the next points?

This is a must more difficult question, and it requires a little more knowledge about your graph.
In this example and for most graphs we are just going to start at one spot and move in a linear direction, like a map (say of the Oregon Trail?)

3. How do you prevent adjacent locations from being on top of each other?
well since we are assuming a mostly linear graph we will just adjust either the x or y coordinate a little bit for each adjacency.  Ill say 5pix for now.

Lets turn that code into smalltalk!

--------------------------------------------------------------------------------
tempPoint:= GraphPoint name:(edgeList at:1) point:(0@0)

"While queue.size > 0 do"
[queue size > 0] whileTrue:[

"also need to get some numbers to draw width"
parentx:=tempPoint point x.
parenty:=tempPoint point y.
x:= (-5 *((tempAdj size)/2))+parentx. "integer division"

ifTrue:[
]."closes ifTrue"

ifFalse:[
tempPoint:= GraphPoint name (adj at: 1) point:(x@parenty+5)
x:=x+5.
]."closes ifFalse"

]. "closes foreach"
]. "closes while"
--------------------------------------------------------------------------------
***Step 3**********
So now we have 2 awesome lists.  One that tells use what points to draw, and one that tells use what edges(lines) to draw.
So as I promised, since we did the hard stuff in the last step, this will be trivial.

In MapView we need to make a method called displayOn: (this will override MapViews super class
This will be composed of 4 lines. (more lines if you want to draw labels and more pretty stuff)

-----------------------------------------------------------------------------------------
displayOn: aGraphicsContext
super displayOn: aGraphicsContext.
points do: [:p|(Rectangle origin:(p point) extent:2@2) displayFilledOn: aGraphicsContext].
lines do: [:l|aGraphicsContext displayPolyline: l].
------------------------------------------------------------------------------------------

See easy, now just add the view to your AppModel and you are good to go!
```

And here a the graph I got from this code for Oregon Trail 