Introduction to Data Structures and Algorithms
Assignment 6: Graphs

  • Due 12 July , 7pm

What To Hand In

  • MazeSearch.java
  • BusNetworks.java
  • Permutations.java

Do not rename these files.

Remember to submit all of these files. When you have submitted them, check that you can read the files listed on the submission page, and complete the submission process.

In order to make sure your code can be recognised correctly by our automatic marking program, please notice the following strict rules when implementing your program:

  • 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 MazeCells. Each MazeCell represents 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 MazeCell.

Core

Complete the exploreFromCell method 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
maze9.png maze9shortest.png

Completion

Complete the exploreFromCellAll method 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.

Challenge

Complete the exploreFromCellShortest method 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 BusNetworks program 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 Wellington

The loadNetwork method should ask the user for a file, read the data in the file, and construct a graph of the towns and their connections.
  • The Town class 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).
  • The busNetwork field should contain a set of all the towns in the network. They may or may not be all connected.

The printNetwork method 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, printNetwork does 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->NewPlymouth 

The printConnectedTowns method should find all the connected sets of towns, and print each set on a separate line. It will use the findAllConnected method 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 

Core

  • Complete the loadNetwork and printNetwork methods

Completion

  • Complete the printConnectedTowns and findAllConnected methods. You may need to construct a recursive "helper" method for the findAllConnected method.

Challenge

  • 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 findPermutations method sets things up and calls the extendPermutation method. extendPermutation is a recursive method that builds up the possible permutations.

extendPermutation is 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 display method 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:
permute3.png

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.