Question

I need help with this project:

AaBbCcDc AaBbccdc Body) 11-AA Aa PO y va x x Al-A. 24 EEEEEE T Normal * No Spac... Font Paragraph CSIT 254 Project 4 - Graphs using Linked Lists Purpose To implement a Graph using a Linked List for the neighbors of a vertex. Overview For this project you will create a Graph as a collection of Nodes/Vertexes as 'Locations' and the Links/Edges will be implemented as a Linked List of Locations from a Location The user interface for the Project will be similar to the demo "Undirected NonWeightedExampleSlide19House.java" that is in the "Programming Lab 09 Graphs" in Canvas. However in that demo the room numbers were fixed, here the rooms from the neighbors Linked List will be numbered on output from 1 to n based on the neighbors that a room has. The House Graph.java" file is provided in Canvas. It extends the LinkedGraph.java that you will write. The UML that follows describes the classes and after the UML are some descriptions of the methods. The addvertex method that is in LinkedGraph is to add a vertex to the known' graph. The addedeel method in LinkedGraph calls the addNeighbor) method in Location for the source Location

Code provided:

HOUSEGRAPH.java
public class HouseGraph extends LinkedGraph
{
// establish rooms
private final Location kitchen = new Location("Kitchen");
private final Location pantry = new Location("Pantry");
private final Location diningRoom = new Location("Dining Room");
private final Location backFoyer = new Location("Back Foyer");
private final Location frontFoyer = new Location("Front Foyer");
private final Location study = new Location("Study");
private final Location livingRoom = new Location("Living Room");
private final Location stairs = new Location("Stairs");
private final Location upstairsHallway = new Location("Upstairs Stairs Hallway");
  
// establish the "home" (a.k.a. "starting") location
private final Location homeLocation = frontFoyer;
  
/**
* Constructor (pun intended) builds a house as a LinkedGraph
*/
public HouseGraph()
{
// add rooms to graph - first floor
addVertex(kitchen);
addVertex(pantry);
addVertex(diningRoom);
addVertex(backFoyer);
addVertex(frontFoyer);
addVertex(study);
addVertex(livingRoom);
// add rooms to graph - second floor
addVertex(stairs);
addVertex(upstairsHallway);
// you add 5 more rooms
  
// Add each edge (this undirected Graph has 7 edges,
// so we add 14 edges)
addEdge(kitchen,pantry);
addEdge(pantry,kitchen);

addEdge(pantry,diningRoom);
addEdge(diningRoom,pantry);

addEdge(diningRoom,frontFoyer);
addEdge(frontFoyer,diningRoom);

addEdge(kitchen,backFoyer);
addEdge(backFoyer,kitchen);

addEdge(backFoyer,frontFoyer);
addEdge(frontFoyer,backFoyer);

addEdge(frontFoyer,livingRoom);
addEdge(livingRoom,frontFoyer);

addEdge(backFoyer,study);
addEdge(study,backFoyer);
  
// connect and build second floor
addEdge(frontFoyer, stairs);
addEdge(stairs, frontFoyer);
  
addEdge(stairs, upstairsHallway);
addEdge(upstairsHallway, stairs);
}
  
/**
* the getHomeLocation method returns "a" location as the starting point
* @return a Location that is the "home"(starting) location
*/
public Location getHomeLocation()
{
return homeLocation;
}
  }

Lister.java

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
*
* @author Stephen T. Brower<[email protected]>
*/
public class Lister<E> implements Iterator<E>
{
private Node<E> cursor;
  
/**
* Constructor initializes cursor to the beginning of a Linked List
* @param head pointer to the first node in a Linked List
*/
public Lister(Node<E> head)
{
cursor = head;
}
  
/**
* hasNext method returns a true if cursor is not null, false otherwise
* meaning does cursor point to a Node?
* @return a boolean that indicates if cursor is pointing to a Node
*/
public boolean hasNext()
{
return cursor != null;
}
  
/**
* next method returns data from the Node<E> and advances cursor
* @return data from the Node<E>
*/
public E next()
{
E answer;
  
if (!hasNext())
throw new NoSuchElementException("The lister is empty");
  
// get the data
answer = cursor.getData();
  
// advance cursor
cursor = cursor.getLink();
  
return answer;
}
  
/**
* remove method is not implemented
*/
public void remove()
{
throw new UnsupportedOperationException("Lister has no remove method");
}
}

files like LinkegBag.java, LinkedGraph.java, Location.java, Node.java, project04Option2Summer2018.java are needed.

Thank you!

Answer 1

Working code implemented in Java and appropriate comments provided for better understanding:

Here I am attaching code for these files:

• HouseGraph.java
• LinkedBag.java
• LinkedGraph.java
• Lister.java
• Location.java
• Node.java
• Project04Option2Summer2018.java

Source code for HouseGraph.java:

public class HouseGraph extends LinkedGraph
{
// establish rooms
private final Location kitchen = new Location("Kitchen");
private final Location pantry = new Location("Pantry");
private final Location diningRoom = new Location("Dining Room");
private final Location backFoyer = new Location("Back Foyer");
private final Location frontFoyer = new Location("Front Foyer");
private final Location study = new Location("Study");
private final Location livingRoom = new Location("Living Room");
private final Location stairs = new Location("Stairs");
private final Location upstairsHallway = new Location("Upstairs Stairs Hallway");
  
// establish the "home" (a.k.a. "starting") location
private final Location homeLocation = frontFoyer;
  
/**
* Constructor (pun intended) builds a house as a LinkedGraph
*/
public HouseGraph()
{
// add rooms to graph - first floor
addVertex(kitchen);
addVertex(pantry);
addVertex(diningRoom);
addVertex(backFoyer);
addVertex(frontFoyer);
addVertex(study);
addVertex(livingRoom);
// add rooms to graph - second floor
addVertex(stairs);
addVertex(upstairsHallway);
// you add 5 more rooms
  
// Add each edge (this undirected Graph has 7 edges,
// so we add 14 edges)
addEdge(kitchen,pantry);
addEdge(pantry,kitchen);

addEdge(pantry,diningRoom);
addEdge(diningRoom,pantry);

addEdge(diningRoom,frontFoyer);
addEdge(frontFoyer,diningRoom);

addEdge(kitchen,backFoyer);
addEdge(backFoyer,kitchen);

addEdge(backFoyer,frontFoyer);
addEdge(frontFoyer,backFoyer);

addEdge(frontFoyer,livingRoom);
addEdge(livingRoom,frontFoyer);

addEdge(backFoyer,study);
addEdge(study,backFoyer);
  
// connect and build second floor
addEdge(frontFoyer, stairs);
addEdge(stairs, frontFoyer);
  
addEdge(stairs, upstairsHallway);
addEdge(upstairsHallway, stairs);
}
  
/**
* the getHomeLocation method returns "a" location as the starting point
* @return a Location that is the "home"(starting) location
*/
public Location getHomeLocation()
{
return homeLocation;
}
  
}

Source code for LinkedBag.java:

public class LinkedBag<E extends Comparable<E>>
{
private Node<E> head;
private Node<E> tail;
private int numElements;

/**
* No-arg constructor
*/
public LinkedBag() {
head = null;
tail = null;
numElements = 0;
}

/**
* getSize method returns the number of elements
*
* @return The value in the numElements field
*/
public int getSize() {
return numElements;
}

/**
* appendList method adds an element after the tail
*
* @param newElement The E object to be added
*/
public void appendList(E newElement) {
if (tail == null) {
head = new Node<E>(newElement, null);
tail = head;
} else {
tail.setNext(new Node<E>(newElement, null));
tail = tail.getNext();
}
numElements++;
}

/**
* prependList method adds an element before the head
*
* @param newElement The E object to be added
*/
public void prependList(E newElement) {
head = new Node<E>(newElement, head);
numElements++;
}
  
/**
* add method adds the elements in order
* @param newElement value to be added to the list
*/
public void add(E newElement) {
Node<E> previous = null;
Node<E> cursor = head;
boolean found = false;
  
if (cursor == null){
head = new Node<E>(newElement, head);
tail = head;
found = true;
}
  
while (found != true) {
if (newElement.compareTo(cursor.getData()) > 0) {
if (cursor == tail){
tail.setNext(new Node<E>(newElement,null));
tail = tail.getNext();
found = true;
}
previous = cursor;
cursor = cursor.getNext();
}
else
{
if (cursor == head){
head = new Node<E>(newElement,head);
}
else if (cursor == tail){
tail.setNext(new Node<E>(newElement,null));
tail = tail.getNext();
}
else{
previous.setNext(new Node<E>(newElement,cursor));
}
found = true;
}
}
numElements++;
}

/**
* exists boolean checks if a string exists in the data
*
* @param target is the target value checked for existence
* @return That the value has been found
*/
public boolean exists(E target) {
boolean found = false;
Node<E> cursor = head;

while (cursor != null && !found) {
if (cursor.getData().equals(target)) {
found = true;
} else {
cursor = cursor.getNext();
}
}
return found;
}

/**
* countOccurences method looks for a String in the data
*
* @param target The String to be found in the data
* @return an int with the number of times target is found in the data
*/
public int countOccurences(E target) {
int numOccur = 0;
Node<E> cursor = head;

while (cursor != null) {
if (cursor.getData().equals(target)) {
numOccur++;
} else {
cursor = cursor.getNext();
}
}
return numOccur;
}

/**
* remove method looks for the 1st occurrence of a String and removes it
*
* @param target The String to be removed
* @return a boolean to indicate if the target was removed
*/
public boolean remove(E target) {
Node<E> cursor = head, previous = null;
boolean found = false;

while (cursor != null && !found) {
if (cursor.getData().equals(target)) {
found = true;
} else {
previous = cursor;
cursor = cursor.getNext();
}
}
if (found && cursor != null) {
if (previous == null) {
head = head.getNext();
} else {
previous.setNext(cursor.getNext());
}

if (tail == cursor) {
tail = previous;
}
numElements--;
}
return found;
}

/**
* the iteratorPrototype method "copies" the linked list and passes the
* copied linked list to a new Lister<E>
*
* @return a Lister<E> using a copy of the linked list
*/
public Lister<E> iterator() {
// declare variables
Node headOfListToReturn; // beginning of new "copied" list
Node cursorOfListToCopy; // active node of list to copy
Node lastNodeOfListToReturn; // end of new "copied" list

// establish the copied list
headOfListToReturn = null;

if (head != null) {
// create the head of the new list
headOfListToReturn = new Node(head.getData(), null);
// use lastNodeOfListToReturn as a pointer to the last node in the copied list
lastNodeOfListToReturn = headOfListToReturn;
// use currentCursor as the pointer to the existing list
cursorOfListToCopy = head.getNext();
// if we have a node...
while (cursorOfListToCopy != null) {
// create a new node from the end of the new list
lastNodeOfListToReturn.setNext(new Node(cursorOfListToCopy.getData(), null));
// move lastNodeOfListToReturn to the new last node
lastNodeOfListToReturn = lastNodeOfListToReturn.getNext();
// move the cursorOfListToCopy to the next node
cursorOfListToCopy = cursorOfListToCopy.getNext();
}
}

return new Lister(headOfListToReturn);
}
}

Source code for LinkedGraph.java:

public class LinkedGraph
{
   private LinkedBag<Location> vertexList;
  
/**
* No-arg constructor
*/
public LinkedGraph(){
vertexList = new LinkedBag<Location>();
}
  
/**
* addVertex method adds a new location to known graph
* @param newVertex value to be added to the graph
*/
public void addVertex(Location newVertex){
vertexList.add(newVertex);
}
  
/**
* size method returns the size of the vertex list
* @return the number of elements held in the vertex list
*/
public int size(){
return vertexList.getSize();
}
  
/**
* addEdge method receives 2 locations and if the source and
* destination are in the known list of vertices, the second location
* is added as a neighbor to the first Location passed
* @param source starting location
* @param destination location to add
*/
public void addEdge(Location source, Location destination){
if (vertexList.exists(source) && vertexList.exists(destination))
source.addNeighbor(destination);
}
  
/**
* isEdge method receives 2 Locations and if the source and
* destination are in the known list of vertices, the second Location
* is checked to see if it is a neighbor of the first Location
* @param source location you are at
* @param destination location to see if it is a neighbor of source
* @return true if destination is a neighbor of source, false if not
*/
public boolean isEdge(Location source, Location destination){
if (vertexList.exists(source) && vertexList.exists(destination)){
if (source.isNeighbor(destination))
return true;
else
return false;
}
else
return false;
}
  
/**
* neighbors method returns a Lister of Location which are the
* neighbors of the Location passed
* @param vertex value whose neighbors user wants to see
* @return lister of location of neighbors
*/
public Lister<Location> neighbors(Location vertex){
return vertex.neighbors();
}
}

Source code for Lister.java:

import java.util.Iterator;
import java.util.NoSuchElementException;

public class Lister<E> implements Iterator<E>
{
private Node<E> cursor;
  
/**
* Constructor initializes cursor to the beginning of a Linked List
* @param head pointer to the first node in a Linked List
*/
public Lister(Node<E> head)
{
cursor = head;
}
  
/**
* hasNext method returns a true if cursor is not null, false otherwise
* meaning does cursor point to a Node?
* @return a boolean that indicates if cursor is pointing to a Node
*/
public boolean hasNext()
{
return cursor != null;
}
  
/**
* next method returns data from the Node<E> and advances cursor
* @return data from the Node<E>
*/
public E next()
{
E answer;
  
if (!hasNext())
throw new NoSuchElementException("The lister is empty");
  
// get the data
answer = cursor.getData();
  
// advance cursor
cursor = cursor.getNext();
  
return answer;
}
  
/**
* remove method is not implemented
*/
public void remove()
{
throw new UnsupportedOperationException("Lister has no remove method");
}
}

Source code for Location.java:

public class Location implements Comparable<Location>
{
   private String description;
private LinkedBag<Location> neighbors;
  
/**
* Constructor
* @param initDescription value for the description field
*/
public Location(String initDescription){
description = initDescription;
neighbors = new LinkedBag<Location>();
}
  
/**
* getDescription method returns the description of the location
* @return value in the description field
*/
public String getDescription(){
return description;
}
  
/**
* isNeighbor method returns a boolean that indicates whether other
* location is a neighbor of this location
* @param otherLocation value to see if it is neighbors with current location
* @return boolean indicating whether the two locations are neighbors
*/
public boolean isNeighbor(Location otherLocation){
if (neighbors.exists(otherLocation))
return true;
else
return false;
}
  
/**
* compareTo method compares this description field to another locations
* @param otherLocation value of whose description will be compared
* @return int with result of comparison
*/
public int compareTo(Location otherLocation){
if (!(otherLocation instanceof Location))
throw new ClassCastException("A Location object expected.");
  
return description.compareToIgnoreCase(otherLocation.getDescription());
}
  
/**
* equals method compares the description for this location to another
* @param otherLocation is the other location whose description will be compared
* @return a boolean for whether or not the descriptions are equal
*/
public boolean equals(Location otherLocation){
if (!(otherLocation instanceof Location))
throw new ClassCastException("A Location object expected.");
  
if (description.equalsIgnoreCase(otherLocation.getDescription()))
return true;
else
return false;
}
  
/**
* addNeighbor method receives a location and adds it to the neighbors
* linked list
* @param neighbor value to add to the linked list of neighbors
*/
public void addNeighbor(Location neighbor){
neighbors.add(neighbor);
}
  
/**
* toString method used to return a String representing this location
* @return a string representing the location
*/
@Override
public String toString(){
return description;
}
  
/**
* numNeighbors method returns the length of the neighbors linked list
* @return length of neighbors linked list
*/
public int numNeighbors(){
return neighbors.getSize();
}
  
/**
* neighbors method returns the Lister from the neighbors linked list
* @return lister from neighbors linked list
*/
public Lister<Location> neighbors(){
return neighbors.iterator();
}
}

Source code for Node.java:

public class Node<E>
{
private E data;
private Node<E> next;

/**
*
* @param initialData value for the initial data
* @param initialNext value for the initial next
*/
public Node(E initialData, Node<E> initialNext) {
data = initialData;
next = initialNext;
}

/**
* getData method returns the data
*
* @return The value in the data field
*/
public E getData() {
return data;
}

/**
* getNext method returns the next
*
* @return The value in the next field
*/
public Node<E> getNext() {
return next;
}

/**
* The setData method accepts an argument which is stored in the data field.
*
* @param newData value for data field
*/
public void setData(E newData) {
data = newData;
}

/**
* The setNext method accepts an argument which is stored in the next field.
*
* @param newNext value for next field
*/
public void setNext(Node<E> newNext) {
next = newNext;
}
}

Source code for Project04Option2Summer2018.java:

import java.util.Scanner;

public class project04Option2Summer2018
{
/**
* @param args the command line arguments
*/
public static void main(String[] args)
{
int userChoice;
Scanner input = new Scanner(System.in);
  
//Creating the graph
HouseGraph myHouse = new HouseGraph();
Location found;
found = myHouse.getHomeLocation();
  
userChoice = -1;
do
{
// display the current vertex
System.out.println("\nYou are currently in room " + found.getDescription());

// who are our neighbors?
System.out.println("neighbors of " + found.getDescription() + " are:");
  
Lister<Location> neighborsList = myHouse.neighbors(found);
int n = 1;
while (neighborsList.hasNext())
{
Location displayNeighbors = neighborsList.next();
System.out.print(n + "-" + displayNeighbors.getDescription());
if (neighborsList.hasNext())
{
System.out.print( ", ");
n++;
}
}
  
//Ask for user choice
System.out.print("\n\nWhere would you like to go? (-1 to exit): ");
userChoice = input.nextInt();

// if their choice is -1 then exit
if (userChoice == -1)
System.out.println("\nGood bye!");
else if (userChoice < 1 || userChoice > n)
System.out.println("\noops! not a neighbor");
else
{
neighborsList = myHouse.neighbors(found);
n = 1;
while (neighborsList.hasNext())
{
Location newLocation = neighborsList.next();
if (userChoice == n)
found = newLocation;
n++;
}
}

  
} while (userChoice != -1);
}
}

Sample Output Screenshots:

Hope it helps, if you like the answer give it a thumbs up. Thank you.