From VisualWorks® NonCommercial, 7.4.1 of May 30, 2006 on January 31, 2007 at 4:34:29 am Graph Smalltalk false private Smalltalk.* SmallGraph SmallGraph Stack Graph Core.Object false none stack SmallGraph SmallGraph Graph.Stack Standard simple stack data structure. Basic use: |a| a:= Stack new. a push: 'a'. a push:'b'. a pop. (return b) a top (return a) Instance Variables: stack <OrderedCollection> simulates the stack Node Graph Core.Object false none name id visited NextId SmallGraph SmallGraph Graph.Node Represents a single Node Instance Variables: id <int> unique node id number visited <Boolean> flag used for various algorithms name <string> name of the node. DFSAlgorithm Graph Core.Object false none result startNode matrix SmallGraph SmallGraph Graph.DFSAlgorithm Implements a simple DFS Traversal of a graph. Instance Variables: matrix <AdjacencyMatrix> the adjacency matrix for the algorithm result <(Collection of: Object)> the collection that holds the results of the algorithm startNode <Node> description of startNode AdjacencyMatrix Graph Core.Object false none rows directed nodes SmallGraph SmallGraph Graph.AdjacencyMatrix Represents a basic graph adjacency matrix. Instance Variables: directed <Boolean> flag to indicate whether graph is directed. true = directed. nodes <Dictionary> a dictionary of nodes keyed by id. rows <(Collection of: (Collection of: int))> the rows of the matrix Graph.Node class instance creation nextID: aNum "initialize nextid. THIS SHOULD ONLY BE CALLED ONCE!! Calling after nodes are created may cause node id's to be duplicated" NextId := aNum. named: aName "Create a new instance of Node, and set up its values" | inst | inst := Node new initialize. inst name: aName. ^inst nextID "get the next sequential id." NextId := NextId + 1. ^NextId. intialize super initialize. NextId := 0. Graph.Node printing printString "convert myself to printing string" ^'Node: ',self name,' ID: ', self id printString. asString "answer with my string representation" ^'Node: ',self name,' ID: ', self id printString. Graph.Node initialize-release initialize "Initialize a newly created instance. This method must answer the receiver." " *** Edit the following to properly initialize instance variables ***" name := 'none'. id := Node nextID. visited := false. " *** And replace this comment with additional initialization code *** " ^self Graph.Node accessing visited: aBool "set my visited status to aBool" visited := aBool. id "answer with my id" ^id name: aString "set my name to a new value" name := aString visited "answer with my visited status" ^ visited. name "answer with my name" ^name Graph.AdjacencyMatrix class initialize-release directed: aBoolean "Create a new Adjacency Matrix with directed flag set to aBoolean" |inst| inst := super new initialize. inst directed: aBoolean. ^inst. Graph.AdjacencyMatrix accessing adjacencyListFor: aNode "search the matrix and return all nodes that are adjacent to this one" |row list index| row := rows at: aNode id. index := 1. list := OrderedCollection new. row do: [ :i | i > 0 ifTrue: [ list add: (nodes at: index)]. index := index +1. ]. ^ list. nodeAt: anID "return the node given its id" ^nodes at: anID directed: aBool "set status. Treat this method as private used only for initialization" directed := aBool. expand "expand the matrix by 1 row" "first we make a new row. then pad the entries with 0 to keep it square" | row | row := OrderedCollection new. rows add: row. 1 to: rows size do: [ :i | row add: 0 ]. 1 to: (rows size) -1 do: [ :i | (rows at: i) add: 0]. addNode: aNode "add a node to the dictionary keyed by node id" nodes at: aNode id put: aNode directed "return directed status" ^directed. resetVisitStatus "foreach node in the dictionary, set its status to false" nodes keysAndValuesDo: [ :k :v | v visited: false.] Graph.AdjacencyMatrix initialize-release initialize "initialize this object instance" rows := OrderedCollection new. nodes := Dictionary new. Graph.AdjacencyMatrix printing print Transcript show: 'Adjacency Matrix: ' ; cr. rows isEmpty ifTrue:[Transcript show: 'Empty';cr.] ifFalse:[ rows do: [ :row | row do: [ :i | Transcript show: i printString ; show: ' '.] . Transcript cr.]. ]. Graph.AdjacencyMatrix controlling addEdgeFrom: sourceNode to: destNode |row| "First check if nodes are in dict, if not add them" (nodes includesKey: sourceNode id) ifFalse: [ nodes at: sourceNode id put: sourceNode ]. (nodes includesKey: destNode id) ifFalse: [ nodes at: destNode id put: destNode ]. "Check for expansion and expand if necessary" [sourceNode id > rows size] whileTrue: [ self expand.]. [destNode id > rows size] whileTrue: [self expand.]. "grab the correct row for the sourcenode and set edge" row := rows at: sourceNode id. row at: destNode id put: 1. "if not directed, add the opposite direction edge" directed ifFalse: [ row := rows at: destNode id. row at: sourceNode id put: 1]. hasEdgeFrom: sourceNode to: destNode "Check for an edge." | row | "First be sure that we have these nodes in the matrix" sourceNode id > rows size ifTrue:[ ^false]. destNode id > rows size ifTrue: [^false]. "Then just check the value" row := rows at: sourceNode id. ^ (row at: destNode id) > 0 clear "clear out the matrix. Not as efficient as zeroing everything out and just reusing the already expanded matrix. This way we truly have to start over" rows := OrderedCollection new. nodes := Dictionary new. removeEdgeFrom: sourceNode to: destNode "First be sure that we have these nodes in the matrix then just go to the correct position and set it to 0. If not directed, remove the mirror edge also" | row | sourceNode id > rows size ifTrue: [^false]. destNode id > rows size ifTrue: [^false]. row := rows at: sourceNode id. row at: destNode id put: 0. directed ifFalse: [row := rows at: destNode id. row at: sourceNode id put: 0] Graph.DFSAlgorithm class instance creation on: aMatrix "Create a new algorithm on aMatrix" |inst| inst := super new initialize. inst matrix: aMatrix. ^inst. new "Answer a newly created and initialized instance." ^super new initialize Graph.DFSAlgorithm accessing startNode "answer with the node to start from" ^startNode result "answer with the result list" ^result startNode: aNode "setup the starting node" startNode := aNode matrix: aMatrix "setup the matrix that the algorithm runs on" matrix := aMatrix. Graph.DFSAlgorithm printing print Transcript show: 'DFS Results starting at node ' ; show: startNode ; cr. result do: [ :i | Transcript show: i ; show: ' ' ]. Transcript cr. Graph.DFSAlgorithm initialize-release initialize "Initialize a newly created instance. This method must answer the receiver." " *** Edit the following to properly initialize instance variables ***" result := nil. startNode := nil. " *** And replace this comment with additional initialization code *** " ^self Graph.DFSAlgorithm controlling runFromNode: aNode "Run the standard DFS Algorithm" | stack node nodes | startNode := aNode. matrix resetVisitStatus. stack := Stack new. stack push: startNode. result := OrderedCollection new. [ stack notEmpty ] whileTrue: [ node := stack pop. result add: node. node visited: true. nodes := matrix adjacencyListFor: node. nodes do: [ :n | n visited ifFalse: [ (stack contains: n ) ifFalse: [stack push: n]. ]. ]. ]. Graph.Stack class instance creation new "Answer a newly created and initialized instance." ^super new initialize Graph.Stack initialize-release initialize "Initialize a newly created instance. This method must answer the receiver." " *** Edit the following to properly initialize instance variables ***" stack := OrderedCollection new. " *** And replace this comment with additional initialization code *** " ^self Graph.Stack accessing pop "standard stack pop" | val | val := stack last. stack removeLast. ^val. top "peek at the top element of the stack, but do not remove it." ^ stack last. notEmpty "answer true if I have elements, otherwise false" ^ stack size ~= 0. push: anObject "push anObject onto the stack" stack add: anObject contains: anObject "check if anObject is on the stack" ^ stack includes: anObject.