View this PageEdit this Page (locked)Attachments to this PageHistory of this PageHomeRecent ChangesSearch the SwikiHelp Guide
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.
	edgeList add: #('A','C',2).
	edgeList add: #('A','B',2).
	edgeList add: #('C','D',2).
	edgeList add: #('B','D',2).
	edgeList add: #('D','E',2).
	
If this were the case you would get a points adjacencies with the method I call 

getAdj: aPointName
	| 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:
		AddLines
		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.

	Add first Point to Queue
	While queue.size > 0 do
		add point to graph
		get point's adjacencies
		for each adj:
			add edge point-adj to graph
			add adj to queue
			
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:

	Add first Point to Queue
	While queue.size > 0 do
		add point to graph
		get point's adjacencies
		for each adj:
			if adj not already drawn
				add adj to queue
			add edge point-adj to graph
		
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!

--------------------------------------------------------------------------------
"Add first Point to Queue"
	tempPoint:= GraphPoint name:(edgeList at:1) point:(0@0)
	queue addLast: tempPoint.

	"While queue.size > 0 do"
	[queue size > 0] whileTrue:[
	
		"add point to graph"
		points add: tempPoint.
		
		"get point's adjacencies"
		tempAdj=(getAdj: aPointName) "code from earlier"
		
		"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"
		
		"for each adj:"
		tempAdj do:[:adj|.
		
			"if adj not already drawn"
			adj inPoints
				ifTrue:[
					tempPoint:=points get:adj.
				]."closes ifTrue"
			
				"add adj to queue" "also need to make a MapPoint object"
				ifFalse:[ 
					tempPoint:= GraphPoint name (adj at: 1) point:(x@parenty+5)
					points add: tempPoint.
					x:=x+5.
				]."closes ifFalse"
				
			"add edge point-adj to graph"
			edges add:(#((parentx@parenty),(tempPoint point)).					 
		]. "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
External Image


















Links to this Page