QuestionQuestion

Assignment Description
In this assignment you'll complete the implementation of a graph class that can represent simple mazes.

Implementation Specifications
The provided MazeGraph class is a skeleton implementation of a graph class that uses an adjacency matrix representation. The functionality of the class is limited, intended only for constructing simple, maze-like graphs and finding the shortest path between two locations in the graph. The vertices of the graph are conceptually arranged in a grid of a specified width and height. While the adjacency matrix can represent adjacency between any pair of vertices, for the purposes of this assignment vertices may only be connected to the vertices immediate above, below, to the left, or to the right of them.

The class' adjacency matrix is a four-dimensional boolean array called adjacent. The first and second pair of indices specify a location in the graph in row/column formation. For example, adjacent[1][4][6][3] records the adjacency of location 1,4 and 6,3, i.e., holds true of those vertices are adjacent, and false if those vertices are not adjacent.

There are three methods you will need to complete. As usual, do not modify the existing public interface of the class but you are free to add helper methods, etc. Additionally, you may not modify the adjacency matrix representation of the graph.
void connect(Location a, Location b)
This method connects (makes adjacent) two vertices in the graph. The two locations of those vertices must be side-by-side (left, right) or stacked (above, below). If the locations do not meet these criteria, this function should throw an IllegalArgumentException. Attempting to connect to vertices that are already adjacent should slightly fail (no changes made to the graph).

ArrayList<Location> getShortestPath(Location start, Location end)
The method should identify a shortest path between the two specified vertices, if one exists. The returned ArrayList holds the locations of the vertices in the path, in order from start to end inclusive. If there is no path from start to end then the returned ArrayList should be empty. String toString()
This method should return a String representation of the graph. Vertices that are adjacent to at least one other vertex should be represented by one character, and vertices that are not adjacent to any vertices sould be represented by a different character.

For example,
XXXXXXXXXXXXX
..........X.X
X.XXX.XXX.X.X
X.X.X...X.X.X
X.X.XXX.XXX.X
X...X.....X..
XXXXXXXXXXXXX

The characters you use do not matter, as long as they are distinct. Since adjacency is constrained to four possible neighbors, the character rules above will visually show the structure of the maze the graph represents.

Deliverables
1) The completed MazeGraph.java source file.
2) If needed, any additional source files required by MazeGraph.java.
Do not include any extraneous files, such as Eclipse IDE files, bytecode files, or subversion files.

Solution PreviewSolution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

import java.util.ArrayList;

public class MazeGraph {
   
public static class Location {
public int row;
public int column;

public Location(int row, int column) {
this.row = row;
this.column = column;
}

            @Override
            public boolean equals(Object o) {
                if (o == null) {
                   return false;
                }
                if (o instanceof Location) {
                   Location l = (Location) o;
                   return row == l.row && column == l.column;
                }
                return false;
            }               
}...
$73.00 for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats