URGENT IN C++
Microsoft Word - Document1 CSE310 Assignment 7 Files To be Submitted: You are required to turn in the following source file(s) in C++: Assignment7.cpp Graph.h Queue.h LinkedList.h You can also submit additional files Objectives: -This is to practice making graphs and performing some operations. Assignment Description: You need to implement a graph data structure using an adjacency list to keep track of locations and paths. Their paths are bi-directional, thus you will need to represent a graph with undirected edges. Each of your graph’s nodes should represent a location with its name. You need to implement a driver program that reads in a number of nodes for a graph, followed by location names. Then the program needs to read in a number of edges (paths), followed by pairs of locations (each pair contains two location names, separated by a comma). 13 Archway Bayswater Borough Chorleywood Dagenham East Euston Edgware Road Finchley Road Gloucester Road Hampstead Hammersmith Kennington Lancaster Gate 14 Archway,Bayswater Archway,Gloucester Road Borough,Bayswater Gloucester Road,Borough Finchley Road,Hampstead Finchley Road,Edgware Road Borough,Chorleywood Dagenham East,Euston Euston,Hampstead Euston,Edgware Road Hampstead,Gloucester Road Hammersmith,Kennington Kennington,Lancaster Gate Lancaster Gate,Hammersmith where 13 is a user input to indicate that your graph should have 13 nodes. It is followed by 13 location names. Then 14 is a user input to indicate that your graph should have 14 bi-directional edges. It is followed by 14 pairs of location names. After reading in the number of nodes, your program needs to create an adjacency list that is an array of linked lists, using the number of nodes as its size. Then your program needs to store location names. While reading each pair of locations names, you will need to store each path information in the adjacency list. Because each path is bi- directional, you need to store two edges in the adjacency list. For instance, if your program reads in “Archway,Bayswater”, then Bayswater needs to be stored in the linked list for Archway, and Archway needs to be stored in the linked list for Bayswater. Important: for each linked list within the adjacency list, you need to add adjacency node at the end of the linked list as you read in each edge information (each pair of location names). If you do not follow this order, your output will not be the same. After your program is reading in all pairs of locations entered by a user, then your program needs to print out the adjacency list content using the following format: The Graph Content: ------------------- From: Archway To: Bayswater To: Gloucester Road From: Bayswater To: Archway To: Borough From: Borough To: Bayswater To: Gloucester Road To: Chorleywood From: Chorleywood To: Borough From: Dagenham East To: Euston From: Euston To: Dagenham East To: Hampstead To: Edgware Road From: Edgware Road To: Finchley Road To: Euston From: Finchley Road To: Hampstead To: Edgware Road From: Gloucester Road To: Archway To: Borough To: Hampstead From: Hampstead To: Finchley Road To: Euston To: Gloucester Road From: Hammersmith To: Kennington To: Lancaster Gate From: Kennington To: Hammersmith To: Lancaster Gate From: Lancaster Gate To: Kennington To: Hammersmith The order of adjacent locations is the same as the order that they are stored in their linked list. Then your program should perform Breadth First Search starting from the first location name entered. Your program needs to display the content of the queue it is using while BFS is running, and also its result parent (pi) and distance array contents, using the following format. The order of parent and distance arrays should be same as the order that locations are entered, and they are not necessarily in the alphabetical order. ---------------- BFS being performed... The Queue content: { Archway } { Bayswater, Gloucester Road } { Gloucester Road, Borough } { Borough, Hampstead } { Hampstead, Chorleywood } { Chorleywood, Finchley Road, Euston } { Finchley Road, Euston } { Euston, Edgware Road } { Edgware Road, Dagenham East } { Dagenham East } { Hammersmith } { Kennington, Lancaster Gate } { Lancaster Gate } The array pi content: pi[Archway]= none pi[Bayswater]= Archway pi[Borough]= Bayswater pi[Chorleywood]= Borough pi[Dagenham East]= Euston pi[Euston]= Hampstead pi[Edgware Road]= Finchley Road pi[Finchley Road]= Hampstead pi[Gloucester Road]= Archway pi[Hampstead]= Gloucester Road pi[Hammersmith]= none pi[Kennington]= Hammersmith pi[Lancaster Gate]= Hammersmith The array distance content: distance[Archway]=0 distance[Bayswater]=1 distance[Borough]=2 distance[Chorleywood]=3 distance[Dagenham East]=4 distance[Euston]=3 distance[Edgware Road]=4 distance[Finchley Road]=3 distance[Gloucester Road]=1 distance[Hampstead]=2 distance[Hammersmith]=0 distance[Kennington]=1 distance[Lancaster Gate]=1 Note that your program can be tested with different inputs from the above sample input, but the format will be the same. ---------------- The class Graph needs to have an adjacency list, i.e. an array of linked lists. Each node of each linked list needs to have a location information (or an index that corresponds to the location name), and a pointer to the next node. You can have additional variables. The size of the array will be the number of nodes of the graph. It needs to have the following functions (you can define which parameters are needed for each function). -Constructor or a function to initialize the adjacency list using the number of nodes in the graph when a graph information is read from a file. -insertNode( ) it is required to have this function to add a node information to the graph, so that you can add each node one by one. -insertEdge( ) it is required to have this function to add each edge information to the graph, so that you can add each edge one by one -printGraph( ) to print out the graph content using the format specified in the above description. -breadthFirstSearch( ) to perform the Breadth First Search algorithm from the first location specified by a user input. This will need multiple arrays such as parent (pi) array, distance array, and color array, and it will print out the Queue content while performing and print out the result parent and distance array contents. ----------- The class Queue needs to have a queue structure (it can be implemented using a linked list). It should have queue( ) function (add a new element at the end of the linked list), dequeue( ) function (to remove the first element in the linked list), and printQueue( ) function to prints out its content using the format described above. -------------------------------- The class LinkedList needs to be implemented to be used as part of the adjacency list. It should have addNode( ) and printList( ) function. You can add more functions. ------------------------------ Implementation/Documentation Requirements: You need to implement this program using C++ and it has to read from the standard input (from a keyboard). Your program needs to compile and execute in general.asu.edu, and in gradescope when it is submitted. You need to define Graph class with insertNode(), insertEdge(), printGraph(), breadthFirstSeatch() function for the graph, so that we can grade these functions for their correctness. You can decide which parameters are needed. You need to define Queue class with enqueue(), dequeue(), and printQueue() functions for the graph. You can decide which parameters are needed. You need to define LinkedList with addNode( ) and printList( ) functions. Your code should be well documented and commented. You must use the provided data sets. Also you are not allowed to use any predefined data structures (such as ones in the library in C++, etc. For instance, vectors are not allowed) except arrays and strings (you can use predefined functions of the string), you need to build your own data structures and operations associated with them (such as insert or search). For C++, the files need to compile and execute with the commands: g++ *.cpp ./a.out < sampleinput.txt you program should be well commented and documented sampleinput.txt="" you="" program="" should="" be="" well="" commented="" and="">