Introduction to Data Structures and Algorithms
Assignment 6: Graphs
- Due 12 July , 7pm
Resources and links
- Download zip file containing the necessary code and data.
- Java Documentation
- Submit your answers
- Marks and feedback
What To Hand In
- You are NOT allowed to change any code provided in Template, including the headers, the names or parameters of any existing methods. You can add new methods, but do not change the names/parameters of any existing methods.
- You are NOT allowed to delete any constructors in any classes. You are not allowed to change the headers of any existing constructors.
- Do NOT rename any file provided in the Template.
- Make sure the output of your program matches exactly the example given in the grey boxes below. Please note that the printed out message is compared with the model solutions. If you print out any debugging messages, your answer will not match with our model solutions. So please remember to comment out or delete any lines that print any extra information.
Part 1: Maze Search (50%)The MazeSearch program creates mazes and then finds a path through the maze from any point the user clicks on to the goal square (shown in green). The part of the program that creates the maze is written for you. It creates a graph of
MazeCellrepresents one square of the maze, and contains a collection of the neighbour
MazeCells that are connected to it. You are to write the methods that search for a paths through the graph of
MazeCells to the goal
exploreFromCellmethod which searches for a path from a given cell to the goal. As long as it hasn't visited the cell before, it should start by visiting the cell (using the
cell.visit()method), colouring it yellow (using the
cell.draw(Color.yellow)method), and pausing for a brief delay. It should then keep exploring from each of the neighbours. If it succeeds in finding a path through any of its neighbours, it should return
true. If it cannot find a path through any of its neighbours, it should colour the cell red, and return
false, to indicate that the cell was on a dead-end and it failed to find a path to the goal. Your method should use a recursive depth-first search, but because the maze is a graph rather than a tree, it needs to mark each cell it goes to so that it can check that it does not visit it again later. Because you are only looking for one path, you don't need to "unvisit" the cells - just turning them red to indicate they were a dead end is enough. The left hand image below shows a maze of size 9, where the user clicked in the top-left cell, and the program found a path to the goal. The yellow cells are the cells on the path, the blue cell is the goal, and the red cells are the cells that were on dead-end parts of the search.
Note that the search didn't find the shortest path (shown in the right hand image) - finding the shortest path is for the challenge.
|Find a Path||Find Shortest Path|
exploreFromCellAllmethod which searches for all paths from the given cell to the goal. It should colour cells yellow (and pause briefly) as it visits them, but it should also unvisit them and colour them white after it has finished exploring the neighbours (successful or not). (This is so it can use the cell again in a different path). Whenever it reaches the goal MazeCell, it should colour it blue, pause for 500 milliseconds, and then colour it green again. It should never try to explore past the goal cell.
exploreFromCellShortestmethod which searches for the shortest path from the given cell to goal. It should not color the cells while it is searching. Instead, once it gets to the goal, it should colour all the cells on the path that got to the goal. To do this, it must have some way of recording the paths as is builds them, eg by recording the cell it came from every time it gets to a new cell. The right hand image above shows the shortest path from the top left corner.
Part 2: Bus Networks (40%)For this question, you are to write part of the
BusNetworksprogram for analysing a proposed network of inter-city buses. The network consists of nodes for each of the towns in the region and links between pairs of cities that have a direct bus service. The program reads data about the network from a file. The first line of the file has a list of the names of the towns in the region. Each remaining line has two names which are downs with a direct bus service. For example, the file
"data-small.txt"file has just 7 towns and six direct bus services:
Auckland Hamilton Napier NewPlymouth PalmerstonNorth Wellington Whanganui Auckland Hamilton Hamilton Napier Hamilton PalmerstonNorth NewPlymouth Whanganui Napier PalmerstonNorth PalmerstonNorth WellingtonThe
loadNetworkmethod should ask the user for a file, read the data in the file, and construct a graph of the towns and their connections.
Townclass describes the nodes of the graph, with the name of the town and its set of neighbours (towns it has a direct bus service to).
busNetworkfield should contain a set of all the towns in the network. They may or may not be all connected.
printNetworkmethod should print out the network by printing one line for each town in the network, giving the name of the town, followed by its neighbours. Note,
printNetworkdoes not need to traverse the graph - it can just use the set of towns in
busNetwork. For example, for the "data-small.txt" file, it should print Make sure your output match the format: "Town->its neighbours split by space"
The current network: ==================== Auckland->Hamilton Hamilton->Auckland PalmerstonNorth Napier Napier->PalmerstonNorth Hamilton NewPlymouth->Whanganui PalmerstonNorth->Wellington Hamilton Napier Wellington->PalmerstonNorth Whanganui->NewPlymouthThe
printConnectedTownsmethod should find all the connected sets of towns, and print each set on a separate line. It will use the
findAllConnectedmethod to find all the towns connected to a particular town. For example, for the "data-small.txt" file, there are two connected sets of towns that aren't connected to each other, so it should print: Make sure the towns split by space, and print each connected set on a separate line
Connected Towns =============== Auckland Hamilton PalmerstonNorth Wellington Napier NewPlymouth Whanganui
- Complete the
- Complete the
findAllConnectedmethods. You may need to construct a recursive "helper" method for the
- Display the network of towns graphically
Part 3: Permutations (10%)The final part is a program to generate all possible permutations of a list of items. This is somewhat related to the program in the lectures that generated all combinations, and is most easily solved using a recursive algorithm. The program uses a collection of emoji images, which are displayed down the left side of the graphics pane. The user can use the mouse to select images for the list to permute. Clicking the Permute button will make the program search for and display all the possible permutations. Note that if there are too many permutations to find on the graphics pane, the program displays all the extra permutations by overwriting the final column. All the user interface code and display code is written for you; you only have to implement one method which finds all the permuations. The
findPermutationsmethod sets things up and calls the
extendPermutationis a recursive method that builds up the possible permutations.
extendPermutationis passed a Set of remaining items that it can use to extend the permutation and a List of the items in the permutation built so far, and. The comments on the method outline the algorithm. Use the
display(permuationSoFar)method to display each permutation as you find it. The
displaymethod takes care of where and how to display the permutation. Here is an image of the screen after the user has selected three emoji's (crying, halo, and smiling) and then asked for all permutations of them:
Note: finding all permutations of large lists takes a lot of time, but most of the program time is drawing the images. You can pause the display which will then just show the progress of the permutation count in the message line at the bottom of the window. Unpausing will turn the display back on from wherever it is currently up to.