Please need help with this.
Description After spending several weeks taking summer courses, youve become worn out and you would like to chill for a bit before the fall semester begins, playing call of duty, overwatch, or fortnite. The issue is that after not leaving the house for the past few weeks (except when you went to classes), you forgot that your friends have all taken summer trips and will not be back before the summer ends, and they have no internet connection. Luckily there are other people out there who want to play online, you will need to find a person in the closest city to you to be able to play online. In this program, you will be given given a graph (in a form of pairs of connecting cities), and the cities in which someone wants to play online. Starting from city 0, you need to find the person in the closest city (minimum number of edges between city 0 and the other gamer). You will implement breadth first search to accomplish this, you will need to implement the following classes template class myQueue { struct node { Type item ; node * link ; }; public : myQueue (); myQueue ( const myQueue &); myQueue & operator =( const myQueue &); ~ myQueue (); Type front () const ; void enqueue ( const Type &); void dequeue (); bool isEmpty () const ; private : node * head ; node * tail ; }; node * head - pointer that points to the front node node * tail - pointer that points to the end node 1 myQueue() - default constructor that sets an empty queue, you would need to set head and tail to NULL myQueue(const myQueue&) - the copy constructor that creates a deep copy of the object passed into it myQueue& operator=(const myQueue&) - the assignment operator that creates a deep copy of the object on the right side of the operator, remember to avoid memory leaks here and check for self assignments ~myQueue() - destructor that will deallocate the queue object Type front() const - returns the front element of the queue void enqueue(const Type&) - insert an item to the back of the queue void dequeue() - removes the front element from the queue bool isEmpty() const - returns true if the queue is empty and false otherwise These classes will be used to store and traverse a graph (contains the outnieghbor list for the nodes) template class vertex { struct node { Type item ; node * link ; }; public : class edgeIterator { public : friend class vertex ; edgeIterator (); edgeIterator ( node *); edgeIterator operator ++( int ); Type operator *(); bool operator ==( const edgeIterator &); bool operator !=( const edgeIterator &); private : node * current ; }; vertex (); vertex ( const vertex &); const vertex & operator =( const vertex &); ~ vertex (); edgeIterator begin (); edgeIterator end (); void addEdge ( const Type &); private : node * neighbors ; }; 2 Edge Iterator Class node * current - contains the node to which the iterator object currently points edgeIterator() - default constructor that sets current to NULL edgeIterator(node*) - constructor that sets current with the pointer passed in edgeIterator operator++(int) - overloads the ++ operator which moves the iterator over to the next node in the list Type operator*() - returns the item that current pointer points to bool operator==(const edgeIterator&) - compares two iterators, if they both point to the same node then the function returns true otherwise it returns false bool operator!=(const edgeIterator&) - compares two iterators, if they do not both point to the same node then the function returns true otherwise it returns false Vertex Class node * neighbors- this will be a head pointer for a linked list that contains all the outneighbors for a node vertex() - default constructor that assigns neighbors to NULL vertex(const vertex&) - the copy constructor that creates a deep copy of the object passed into the constructor const vertex& operator=(const vertex&) - assignment operator that creates a deep copy of the object on the right side, check for self assignment and make sure you avoid memory leaks ~vertex() - destructor that deallocates the neighbors list edgeIterator begin() - returns an iterator that points to the first node in the outneighbor list edgeIterator end() - returns an iterator that points to NULL void addEdge(const Type&) - adds and edge to the outneighbor list, inserts a new node into neighbors linked list, doesnt matter where in the list, it just needs to be added to the list, the item will be set to the parameter passed into the function Implementation You will be given an input file which consists of a number n which denotes the number of nodes in the graph. You will have a dynamic array of vertex objects which will represent your adjacency matrix, which we will call vertices, so vertices[0] will contain a list of outneighbors of node 0, and vertices[1] will contain a list of outneighbors of node 1 and so on. You will read each pair of integers, call them from and to (the first integer on the line is stored into from and the second integer on the line is stored into from) and you will insert each node into the adjacency list by having vertices[from - 1].addEdge(to - 1); so if you have an edge from 1 to 2 (so the line contains 1 2 which means node 0 has an edge that connects to egde 1) and you will continue this until you read a 0. Then the rest of the files will contain the nodes where other games are waiting to play online, you will need to read the rest of those numbers and maintain them in an array which I call int * friends You will need to use the iterator to traverse the outneighbors of a given node, to set this up, you will have an iterator declared vertex::edgeIterator it and you assign it to the front of any nodes outneighbor list by having the assignment it = vertices[i].begin() where i is a node index, then you 3 use *it to retrieve a node in the outneighbor list of vertices[i] and it++ allows you to go to the next node in the outneighbor list and once it == vertices[i].end() that means you reached the end of the list. Once you build up your adjacency list, you will run the breadth first search algorithm 1. Create a myQueue object 2. Allocate a bool visited array where its length will be the number of nodes and all elements will be set to false 3. Using an iterator, traverse through all the nodes in vertices[0] and insert them into the queue object and each node in the list, mark each of those nodes as visited, i.e. each node it touches, set that node to true in the visited array 4. While the queue is not empty (a) Pop an element from the queue (use the front function to get the front item and then dequeue the item) (b) Check if that node is in the friends list, if so output that node and terminate the program (c) Traverse that nodes outputneighbor list (the node acquired from step 4a) and for each node in that list that has not been marked visited, enqueue into the queue object (d) Go back to step 4a 5. Output no friends have been found, if a friend was found, then you wouldve terminated the program and would have never reached this point Sample Output vasty$ g ++ Asst.cpp vasty$ ./ a . out < I09_1 . txt Friend found at city : 4 :) vasty$ ./ a . out < I09_2 . txt Friend found at city : 7 :) vasty$ ./ a . out < I09_3 . txt Friends not found :(
//asst.cpp
#include "myQueue.h" #include "vertex.h" #include #include using namespace std;
int main() { int nodes, from, to, amtFriends = 0, pal; int * friends; vertex * vertices; cin >> nodes; vertices = new vertex[nodes]; friends = new int[nodes]; //YOUR CODE COMES HERE //YOU MAY ALSO DECLARE FUNCTIONS AND EXTRA VARIABLES AS NEEDED delete [] friends; delete [] vertices; return 0; }
//myQueue.h
#include
template class myQueue { struct node { Type item; node * link; }; public: myQueue(); myQueue(const myQueue&); myQueue& operator=(const myQueue&); ~myQueue(); Type front() const; void enqueue(const Type&); void dequeue(); bool isEmpty() const; private: node * head; node * tail; };
template myQueue::myQueue() { }
template myQueue::myQueue(const myQueue& copy) { }
template myQueue& myQueue::operator=(const myQueue& rhs) { if (this != &rhs) { } return *this; } template myQueue::~myQueue() { }
template Type myQueue::front() const { }
template void myQueue::enqueue(const Type& insert) { }
template void myQueue::dequeue() { }
template bool myQueue::isEmpty() const { }
//vertex.h
#include
#include
using namespace std;
template
class vertex
{
struct node
{
Type item;
node * link;
};
public:
class edgeIterator
{
public:
friend class vertex;
edgeIterator();
edgeIterator(node*);
edgeIterator operator++(int);
Type operator*();
bool operator==(const edgeIterator&);
bool operator!=(const edgeIterator&);
private:
node * current;
};
vertex();
vertex(const vertex&);
const vertex& operator=(const vertex&);
~vertex();
edgeIterator begin();
edgeIterator end();
void addEdge(const Type&);
private:
node * neighbors;
};
template
vertex::edgeIterator::edgeIterator()
{
}
template
vertex::edgeIterator::edgeIterator(vertex::node * edge)
{
}
template
typename vertex::edgeIterator vertex::edgeIterator::operator++(int)
{
}
template
Type vertex::edgeIterator::operator*()
{
}
template
bool vertex::edgeIterator::operator==(const vertex::edgeIterator& rhs)
{
}
template
bool vertex::edgeIterator::operator!=(const vertex::edgeIterator& rhs)
{
}
template
vertex::vertex()
{
}
template
vertex::vertex(const vertex& copy)
{
}
template
const vertex& vertex::operator=(const vertex& rhs)
{
if (this != &rhs)
{
}
return *this;
}
template
vertex::~vertex()
{
}
template
typename vertex::edgeIterator vertex::begin()
{
}
template
typename vertex::edgeIterator vertex::end()
{
}
template
void vertex::addEdge(const Type& edge)
{
}
sample input:
//INPUT1
6 1 2 1 3 1 4 2 5 2 6
0
4 5 6 3
//INPUT2
7 1 2 2 3 3 4 4 5 5 6 6 7 4 1 6 4 5 1 0
7
//INPUT3
8 1 3 3 4 4 1 5 4 4 6 6 7 8 2 7 1 1 7 5 6 2 8
0
8
