# CS441 Systems Biology II CS231 Lab 10 -- Graphs

#### Overview

This week I decided to make a logic puzzle/game. I have several ideas, but the (first?) one I decided to implement was a topological ordering of a graph -- but of course I don't call it that! The premise is that a group of people (the names are of my cousins) got together and played a game. In the game (the details of which are unknown and unimportant), each player got a score that was distinct from all of the others so that they can be ordered into first, second, third ... places. In my puzzle, a list of hints are given to help you figure out the order. You solve the puzzle by moving the names around the landscape with the mouse so that first place is on the left, last place is on the right, and the others are ordered between them.

#### Implementation

###### Vertices

Vertex is the Agent in this simulation, so, as mentioned above, it is up to them to draw whatever part of the Graph should be shown. When a Vertex constructor is called, it not only initializes the instance variables, but also adds the Vertex to the landscape. Apart from accessors and mark()/unmark(), the only methods with any code deal with drawing. drawLineTo(Vertex destination), called from Graph's drawArrows() or when the user connects two words, adds the destination vertex to a sort of adjacency list (it is not really an adjacency list because it may or may not have all of the adjacent vertices, and it could have vertices not connected by edges). When draw() is called, it iterates through the list, drawing arrows to each vertex. Afterward, it draws a filled oval and writes the string on top of it.

###### User Interface

When the program starts up, simulation's initialize() method builds a graph (using an array of vertex labels, it scrambles them into an order, then adds edges randomly so that the new order is the only order). The vertices all have empty 'adjacency lists,' so all that is drawn of the graph are vertices. In addition, I have a Text resource that accepts a String[] and draws the Strings on the Landscape. It writes a hint for every edge, and these are drawn in the upper left corner of the screen. The user can click on vertices (vertices turn blue when selected) to move them (by clicking on empty area) or draw a line from one to another (by clicking on the destination vertex). When the user thinks he has ordered them from left to right, he can click on the button "Submit Solution" to receive an appropriate message via JOptionPane. If he gets stuck, he can get help by clicking "Show Arrows," which calls graph's drawArrows(), removing any wrong arrows that the user may have added and adding any arrows not yet on the landscape. If the user still has trouble, he can click "Show Solution," and the vertices will jump into topological order. The buttons' actionListener is the LandscapeDisplay, but it sends the ActionEvents to sim.react(String command), where it is translated into a graph method.

#### Pictures

Sorry about the fuzzyness. The reddish text is instructions, the green is the hints (for example "Marsha scored lower than Sarah," and "Karen scored higher than Danielle").

#### Conclusion

I was a little unsure of having the same assignment for a third week, but I'm happy with the puzzle I created, and am glad I was able to learn to work with graphs. I feel like I have really deviated from the whole idea of agents, and that my LandscapeDisplay class bears little resemblance to the original, but I guess that doesn't really matter.

After this project was due, I implemented a maze-generating and -solving algorithm. The maze is a graph where the vertices are each square of the path and the edges indicate that there is no wall between the two vertices.

##### Generating the maze

My sister shared with me an algorithm she found online for generating mazes. I unfortunately do not recall the reference. The idea is to have a list of vertices (initially only containing the start square) from which you randomly choose one. From that vertex, visit each adjacent vertex. If it has been encountered before, do not add an edge (this prevents loops). If it has not, then do add an edge, and add it to the list. This eventually visits every vertex, so every location is reachable from the start, including the finish.

##### Solving the maze

I included five different algorithms for solving the maze as agents in this simulation. All are Robots, which display a dialog box upon successfully reaching the end. The five Agents listed below extend Robot.

• UserBot: The user controls this Agent with the arrow keys.
• SmartBot: This bot finds the straight path to the end using a recursive depth-first algorithm that builds a stack of directions. It gives the other bots a head-start, and then follows its instructions to quickly reach the end.
• DepthBot: This bot uses a similar algorithm to the SmartBot to develop its instruction queue. In order to add some variation, at each decision it randomly chooses an order in which to explore the paths. During the recursive search, it adds every node it visits to a queue. I create several of these at the beginning, and they immediately begin to pursue their paths.
• BreadthBot: This bot differs from SmartBot and DepthBot because it calculates its next moves as it goes along. Like breadth-first search, it works by splitting itself and trying all options at the same time. To be fair, only one of its MiniBots moves each iteration. These are stored in a queue, and in each move one is polled and commanded to move itself. Whenever it reaches an intersection, it splits itself into more MiniBots; otherwise it simply moves forward. Regardless, at the end of the move it adds itself and any new bots to the queue.
• WillyNillyBot: This bot also calculates its next move as it goes along. These are memoryless and choose a random direction in which to move each time. Occasionally they actually make it to the finish.
##### Comparison of methods
Different mazes end up with different length paths to the end, which is shown by the SmartBot's time. Since the DepthBots have some randomness, they may do as well as the SmartBot, but usually do somewhat worse. The BreadthBot has no randomness, but rarely beats many DepthBots. The WillyNillyBots are hardly worth considering.

Smart

Depth

WillyNilly

38

207,233,573

375

3473

38

49,187,677

372

8014

40

381,393,635

381

2518

Labels