Question: IN C++ FORMAT PLEASE: We needed to implement the graph.h header file based on list.h and i have provided all of those i have done
IN C++ FORMAT PLEASE:
We needed to implement the graph.h header file based on list.h and i have provided all of those
i have done most of the graph.cpp file but there are some functions that i was not able to finish that i have listed below. please fill in for the comments
this is the graph.h file:
#ifndef GRAPH_H_
#define GRAPH_H_
#include
#include
#include "List.h"
#include
using namespace std;
class Graph
{
public:
/**Constructors and Destructors*/
Graph(int n);
/*** Access Functions ***/
int getNumEdges();
int getNumVertices();
bool isEmpty();
/*** Manipulation Procedures ***/
void addEdge(int u, int v);
void removeEdge(int u, int v);
/*** Additional Operations ***/
void printGraph(ostream& output);
void printBFS(ostream& output);
void BFS(int source);
void printPath(int source, int destination, ostream& output);
int getDistance(int v);
private:
int vertices, edges;
vector
vector
vector
vector
};
#endif /* GRAPH_H_ */
for graph.cpp please implement and fill in the comment for:
1.void Graph:: printBFS(ostream& output
2. void Graph:: BFS(int source)
3. void Graph:: printPath(int source, int destination, ostream& output)
4. int Graph:: getDistance(int v)
graph.cpp file:
#include
#include
#include "List.h"
#include "Graph.h"
#include "assert.h"
#include
using namespace std;
Graph::Graph(int n)
{
vertices = n;
edges = 0;
for(int i=1;i<=n;i++)
{
List
adj.push_back(obj);
}
}
// is right
bool Graph::isEmpty()
{
return getNumVertices() == 0 || getNumEdges() == 0;
}
//is right
int Graph::getNumEdges()
{
return edges;
}
//is right
int Graph::getNumVertices()
{
return vertices;
}
void Graph::addEdge(int u,int v)
{
assert(u <= getNumVertices());
assert(v <= getNumVertices());
adj[u].insertLast(v);
adj[v].insertLast(u);
/*
if( adj[u].getSize() == 0 ||
(adj[u].getSize()!=0 && adj[u].linearSearch(v)==-1))
{
adj[u].insertFirst(v);
}
if(adj[v].getSize()==0 ||
(adj[v].getSize()!=0 && adj[v].linearSearch(u)==-1))
{
adj[v].insertFirst(u);
}
*/
edges++;
}
void Graph::removeEdge(int u,int v)
{
assert (u <= getNumVertices());
assert (v <= getNumVertices());
adj[u].startIterator();
while (!(adj[u].offEnd()))
{
if (adj[u].getIterator() == v)
{
adj[u].removeIterator();
break;
}
adj[u].advanceIterator();
}
adj[v].startIterator();
while (!(adj[v].offEnd()))
{
if (adj[v].getIterator() == u)
{
adj[v].removeIterator();
break;
}
adj[v].advanceIterator();
}
edges--;
}
void Graph::printGraph(ostream &output)
{
int VertSize = adj.size();
for(int i=1; i < VertSize ; i++)
{
output < adj[i].printList(); output << " " << endl; } output << "Total Vertices: "< output << "Total Edges: " << getNumEdges() << endl; } void Graph:: printBFS(ostream& output) { //Prints the current values in the parallel vectors after executing BFS //Prints to the console or to an output file given the ostream parameter //First prints the heading: //v //Then, prints out this information for each vertex in the graph //Note that this function is intended purely to help you debug your code } void Graph:: BFS(int source) { //Performs breath first search on this Graph give a source vertex //pre: at least one vertex must exist //pre: source is a vertex in the graph } void Graph:: printPath(int source, int destination, ostream& output) //Prints the path from the source to the destination vertex //Prints to the console or to an output file given the ostream parameter { /* if destination == source print source else if parent[destination] == 0 print "No path from " source "to " destination exists else Print_Path(Graph, source, parent[destination]) print destination */ } int Graph:: getDistance(int v) { //Returns the value of the distance[v] return -1; } and this is my list.h file: #ifndef LIST_H_ #define LIST_H_ #include #include #include "assert.h" using namespace std; template class List { private: struct Node { listdata data; Node* next; Node* previous; Node(listdata data): data(data), next(NULL), previous(NULL){} }; typedef struct Node* Nodeptr; Nodeptr first; Nodeptr last; Nodeptr iterator; int size; void reverse(Nodeptr node); //Helper function for the public printReverse() function. //Recursively prints the data in a List in reverse. bool isSorted(Nodeptr node); //Helper function for the public isSorted() function. //Recursively determines whether a list is sorted in ascending order. int binarySearch(int low, int high, listdata data); //Recursively searchs the list by dividing the search space in half //Returns the index of the element, if it is found in the List //Returns -1 if the element is not in the List public: /**Constructors and Destructors*/ List(); //Default constructor; initializes and empty list //Postcondition: A new list object is created List (const List &list); //copy constructor ~List(); //Destructor. Frees memory allocated to the list //Postcondition: Memory that was created has been freed /**Accessors*/ listdata getFirst(); //Returns the first element in the list //Precondition: List cannot be empty (there must be a first element) listdata getLast(); //Returns the last element in the list //Precondition: List cannot be empty (there must be a last element) bool isEmpty(); //Determines whether a list is empty. int getSize(); //Returns the size of the list listdata getIterator(); //returns the element currently pointed at by the iterator bool offEnd(); //returns whether the iterator is off the end of the list, i.e. is NULL bool isSorted(); //Wrapper function that calls the isSorted helper function to determine whether //a list is sorted in ascending order. //We will consider that a list is trivially sorted if it is empty. //Therefore, no precondition is needed for this function int getIndex(); //Indicates the index of the Node where the iterator is currently pointing //Nodes are numbered from 1 to size of the list //Pre: size != 0 //Pre: !off_end() int linearSearch(listdata data); //Searchs the list, element by element, from the start of the List to the end of the List //Returns the index of the element, if it is found in the List //Calls the above indexing functions in its implementation //Returns -1 if the element is not in the List //Pre: size != 0 // int binarySearch(int low, int high, listdata value,); //Returns the index where data is located in the List //Calls the private helper function binarySearch to perform the search //Pre: size != 0 //Pre: List is sorted (must test on a sorted list) /**Manipulation Procedures*/ void removeLast(); //Removes the value of the last element in the list //Precondition: List cannot be empty (there must be a last element to remove) //Postcondition: The last element is removed void removeFirst(); //Removes the value of the first element in the list //Precondition: List cannot be empty (there must be a first element to remove) //Postcondition: The first element is removed void insertLast(listdata data); //Inserts a new element at the end of the list //If the list is empty, the new element becomes both first and last //Postcondition: There is a new last element void insertFirst(listdata data); //insertFirst inserts a new Node IN FRONT OF the first node in the list each time it is called, //effectively creating a new front of the list. //Inserts a new element at the start of the list //If the list is empty, the new element becomes both first and last //Postcondition: There is a new first element void startIterator (); // moves the iterator to the start of the list void removeIterator(); //removes the element currently pointed to by the iterator. Iterator then points to NULL. void insertIterator(listdata data); //inserts an element after the node currently pointed to by the iterator void advanceIterator(); //advanceIterator: moves the iterator up by one node void advanceToIndex(int index); //Moves the iterator to the node whose index number is specified in the parameter //Pre: size != 0 //Pre: index <= size /**Additional List Operations*/ void printList(); //Prints to the console the value of each element in the list sequentially //and separated by a blank space //Prints nothing if the list is empty bool operator==(const List &list); //Tests two lists to determine whether their contents are equal //Postcondition: returns true if lists are equal and false otherwise void printReverse(); //Wrapper function that calls the reverse helper function to print a list in reverse //prints nothing if the List is empty }; template //default constructor List { first = NULL; last = NULL; size = 0; iterator = NULL; } //copy constructor template List { if(list.first == NULL) //If the original list is empty, make an empty list for this list { first = last = iterator = NULL; } else { first = new Node(list.first->data); //calling Node constructor Nodeptr temp = list.first; //set a temporary node pointer to point at the first of the original list iterator = first; //set iterator to point to first node of the new list while(temp->next != NULL) { temp = temp->next; //advance up to the next node in the original list iterator->next = new Node(temp->data); //using node constructor to create a new node with copy of data iterator = iterator->next; //advance to this new node } last = iterator; //Why do I need this line of code? iterator = NULL; } } //default destrcutor template List { Nodeptr cursor = first; Nodeptr temp; while(cursor != NULL) { temp = cursor->next; delete cursor; cursor = temp; } } template listdata List { assert(size!=0); return first->data; } template listdata List { assert(size!=0); return last->data; } template bool List { return (size == 0); } template int List { return size; } template listdata List { assert (size !=0); assert(iterator != NULL); return iterator->data; } template bool List { if (iterator == NULL) { return true; } else { return false; } } template void List { assert (size != 0); if (first->next == NULL) { delete last; first = NULL; last = NULL; size = 0; } else { Nodeptr temp = first; while (temp->next != last) { temp = temp->next; } delete last; last = temp; last->next = NULL; } size --; } template void List { assert(size!=0); if (size == 1) { delete first; first = last = NULL; size = 0; } else { Nodeptr temp= first; first = first->next; delete temp; size --; } } template void List { if (size == 0) { first = new Node(data); last = first; } else { last -> next = new Node(data); last = last -> next; } size++; } template void List { if (size==0) { first = new Node(data); last = first; } else { Nodeptr N = new Node(data); N->next = first; first->previous = N; first = N; } size++; } template void List { iterator = first; } template void List { assert(iterator != NULL); if (iterator == last) { removeLast(); } else if (iterator == first) { removeFirst(); } else { iterator->previous->next = iterator->next; iterator->next-> previous = iterator->previous; delete iterator; iterator = NULL; } size --; } template void List { assert(iterator != NULL); if (iterator == last) { insertLast(data); } else { Nodeptr N = new Node(data); N->previous = iterator; N->next = iterator->next; iterator->next->previous = N; iterator->next = N; size++; } } template void List { assert (size != 0); assert (iterator != NULL); iterator = iterator->next; } template void List { Nodeptr iter= first; while (iter != NULL) { cout << iter->data << " "; iter = iter->next; } cout << endl; } template bool List { if(size != list.size) return false; Nodeptr temp1 = first; Nodeptr temp2 = list.first; while(temp1 != NULL) { if(temp1->data != temp2->data) return false; temp1 = temp1->next; temp2 = temp2->next; } return true; } template void List { Nodeptr temp = last; if (temp == NULL) return; else { cout << temp->data << endl; temp = temp->previous; } } template void List { reverse(first); } template bool List { if (size ==0) { return isSorted(); } else reverse (last); return true; } template int List { assert (!offEnd()); assert (iterator != NULL); int count =1 ; Nodeptr temp= first; while (temp != iterator) { count++; temp = temp->next; } return cout ; } template void List { assert(size!=0); assert (iterator != NULL); iterator = first; for (int i = 1; i < index; i++) { iterator = iterator->next; } } template int List { assert (size != 0); Nodeptr temp; temp = first; int location = 1; while (temp != NULL) { if (temp->data == data) { return location; } else { location++; temp = temp->next; } } return -1; } template int List { if (high < low) return -1; int mid = (low + high); if (mid % 2 != 0) { return mid; } else advanceToIndex(mid); if (getIterator() == value) { return mid; } else if (value < getIterator()) { return binarySearch(low, mid -1, value); } else return binarySearch( low, mid +1, value); } #endif /* LIST_H_ */
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help