IN C++ FORMAT PLEASE: We needed to implement the graph.h header file based on li
ID: 3865097 • Letter: I
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 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 <iostream>
#include <cstdlib>
#include "List.h"
#include <vector>
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 <List<int> > adj;
vector<char> color;
vector<int> distance;
vector<int> parent;
};
#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 <iostream>
#include <cstdlib>
#include "List.h"
#include "Graph.h"
#include "assert.h"
#include <vector>
using namespace std;
Graph::Graph(int n)
{
vertices = n;
edges = 0;
for(int i=1;i<=n;i++)
{
List<int> obj;
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 <<i<<": ";
adj[i].printList();
output << " " << endl;
}
output << "Total Vertices: "<<getNumVertices()<<endl;
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 <tab> c <tab> p <tab> d <tab>
//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 <iostream>
#include <cstddef> //for NULL
#include "assert.h"
using namespace std;
template <class listdata>
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 <class listdata>
//default constructor
List<listdata> ::List()
{
first = NULL;
last = NULL;
size = 0;
iterator = NULL;
}
//copy constructor
template <class listdata>
List<listdata>::List(const List &list) : size(list.size)
{
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 <class listdata>
List<listdata> ::~List()
{
Nodeptr cursor = first;
Nodeptr temp;
while(cursor != NULL)
{
temp = cursor->next;
delete cursor;
cursor = temp;
}
}
template <class listdata>
listdata List<listdata>:: getFirst()
{
assert(size!=0);
return first->data;
}
template <class listdata>
listdata List<listdata>::getLast()
{
assert(size!=0);
return last->data;
}
template <class listdata>
bool List<listdata>::isEmpty()
{
return (size == 0);
}
template <class listdata>
int List<listdata>:: getSize()
{
return size;
}
template <class listdata>
listdata List<listdata>:: getIterator()
{
assert (size !=0);
assert(iterator != NULL);
return iterator->data;
}
template <class listdata>
bool List<listdata>:: offEnd()
{
if (iterator == NULL)
{
return true;
}
else
{
return false;
}
}
template <class listdata>
void List<listdata>:: removeLast()
{
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 <class listdata>
void List<listdata>:: removeFirst ()
{
assert(size!=0);
if (size == 1)
{
delete first;
first = last = NULL;
size = 0;
}
else
{
Nodeptr temp= first;
first = first->next;
delete temp;
size --;
}
}
template <class listdata>
void List<listdata>:: insertLast (listdata data)
{
if (size == 0)
{
first = new Node(data);
last = first;
}
else
{
last -> next = new Node(data);
last = last -> next;
}
size++;
}
template <class listdata>
void List<listdata>::insertFirst(listdata data)
{
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 <class listdata>
void List<listdata>:: startIterator ()
{
iterator = first;
}
template <class listdata>
void List<listdata>:: removeIterator()
{
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 <class listdata>
void List<listdata>:: insertIterator(listdata data)
{
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 <class listdata>
void List<listdata>:: advanceIterator()
{
assert (size != 0);
assert (iterator != NULL);
iterator = iterator->next;
}
template <class listdata>
void List<listdata>::printList()
{
Nodeptr iter= first;
while (iter != NULL)
{
cout << iter->data << " ";
iter = iter->next;
}
cout << endl;
}
template <class listdata>
bool List<listdata>:: operator == (const List& 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 <class listdata>
void List <listdata>:: reverse(Nodeptr list)
{
Nodeptr temp = last;
if (temp == NULL)
return;
else
{
cout << temp->data << endl;
temp = temp->previous;
}
}
template <class listdata>
void List<listdata>:: printReverse()
{
reverse(first);
}
template <class listdata>
bool List<listdata>:: isSorted()
{
if (size ==0)
{
return isSorted();
}
else
reverse (last);
return true;
}
template <class listdata>
int List<listdata>:: getIndex()
{
assert (!offEnd());
assert (iterator != NULL);
int count =1 ;
Nodeptr temp= first;
while (temp != iterator)
{
count++;
temp = temp->next;
}
return cout ;
}
template <class listdata>
void List<listdata>:: advanceToIndex(int index)
{
assert(size!=0);
assert (iterator != NULL);
iterator = first;
for (int i = 1; i < index; i++)
{
iterator = iterator->next;
}
}
template <class listdata>
int List<listdata>::linearSearch(listdata data)
{
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 <class listdata>
int List<listdata>:: binarySearch(int low, int high, listdata value)
{
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_ */
Explanation / Answer
struct Edge{
Vertex *destination;
int weight;
};
struct Vertex{
std::list<Edge> incident;
std::string name;
};
class Graph{
private:
std::list<Vertex> vertices;
public:
Graph() = default; //good enough
~Graph() = default; //good enough
void AddVertex(std::string name){
for( auto &v : vertices )
if( v.name == name ) return; /
vertices.push_back( Vertex(name) );
}
};