IN C++ FORMAT PLEASE: graph assignment

assignment guidelines:

1.Copy the code below into a new header file called Graph.h

2. Then, create a new source code file called Graph.cpp.

3. Since we are not using templates, we are going to write our function definitions inside of the Graph.cpp.

We will test them in GraphTest.cpp

4. We will be using the adjacency list representation of a Graph for this data structure.

5. The heart of the Graph data structure will be a vector of linked lists, to store the adjacent vertices of each vertex in the Graph (will create a vector of linked lists to represent our Graph)

6. For this assignment, you could visualize the above Graph as shown in the diagram to its right.

- 1, 2, 3, 4 and 5 in the left hand column of the diagram are indices of the vector (array).

- Those values to their right are their adjacency lists which are stored as linked lists.

- Specifically, for our purposes, we will be representing the Graph as a vector of linked lists named "adj"

- Thus, we could visualize storing the graph as depicted below for this assignment:

adj[0] (purposely left empty!)

adj[1] = 2 -> 3 -> 4 -> NULL //at index 1, we store the adjacency list of vertex 1

adj[2] = 3 -> NULL //at index 2, we store the adjacency list of vertex 2

adj[3] = 2 ->NULL //at index 3, we store the adjacency list of vertex 3, etc

adj[4] = 4 -> NULL

adj[5] = 2 -> NULL

Header File

#include #include #include "List.h" #include

using namespace std; class Graph { public:

/**Constructors and Destructors*/ Graph(int n); //initializes an empty graph to have n vertices and no edges

/*** Access Functions ***/

int getNumEdges();

//returns the number of edges in the graph

int getNumVertices(); //returns the number of vertices in the graph

bool isEmpty();

//returns whether the graph is empty

/*** Manipulation Procedures ***/

void addEdge(int u, int v);

//Pre: u

//inserts vertex v into the adjacency list of vertex u (i.e. inserts v into the list at index u)

//and inserts u into v. void removeEdge(int u, int v); //Pre: u

/*** Additional Operations ***/

void printGraph(ostream& output);

//Prints the adjacency list of each vertex in the graph,

//vertex:

//Prints to the console or to an output file given the ostream parameter

private: int vertices, edges; /umber of edges and vertices vector > adj;

};

A Word on Printing

We are representing our Graph using the Adjacency List Representation.

Thus, we will need to print out its adjacency lists.

Below is an example of how to print your Graph when the user calls printGraph():

1: 2 5

2: 1 3 4

3: 2 4

4: 2 3 5

5: 1 4 5

File Input and Output

Save two text files in the main project directory on Eclipse. These two files must be named infile.txt and outfile.txt.

Create a new source file named WriteGraph.cpp which will contain logic for reading in information about a Graph from a file and then writing out the results to a file

The input file will be in two parts. The first part will begin with a line consisting of a single integer n giving the number of vertices in the graph.

You will pass this value n into your Graph constructor when you create your Graph, setting the numVertices to be this value n.

Each subsequent line will represent an edge by a pair of distinct numbers in the range 1 to n, separated by a space. These numbers are the end vertices of the corresponding edge.

Your WriteGraph.cpp file should then write out the corresponding graph to outfile.txt. See the examples below:

Sample Input File

6 1 2 1 3 2 4 2 5 2 6 3 4 4 5 5 6 Example Output File: 1: 2 3 2: 1 4 5 6 3: 1 4 4: 2 3 5 5: 2 4 6 6: 2 5

Total vertices: 6

Total edges: 8

MY LIST.H FILE IS HERE:

#ifndef LIST_H_

#define LIST_H_

#include

#include //for NULL

#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 value, int low, int high);

//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

/**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 ::List()

{

first = NULL;

last = NULL;

size = 0;

iterator = NULL;

}

//copy constructor

template

List::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

List ::~List()

{

Nodeptr cursor = first;

Nodeptr temp;

while(cursor != NULL)

{

temp = cursor->next;

delete cursor;

cursor = temp;

}

}

template

listdata List:: getFirst()

{

assert(size!=0);

return first->data;

}

template

listdata List::getLast()

{

assert(size!=0);

return last->data;

}

template

bool List::isEmpty()

{

return (size == 0);

}

template

int List:: getSize()

{

return size;

}

template

listdata List:: getIterator()

{

assert (size !=0);

assert(iterator != NULL);

return iterator->data;

}

template

bool List:: offEnd()

{

if (iterator == NULL)

{

return true;

}

else

{

return false;

}

}

template

void List:: 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

void List:: 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

void List:: insertLast (listdata data)

{

if (size == 0)

{

first = new Node(data);

last = first;

}

else

{

last -> next = new Node(data);

last = last -> next;

}

size++;

}

template

void List::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

void List:: startIterator ()

{

iterator = first;

}

template

void List:: 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

void List:: 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

void List:: advanceIterator()

{

assert (size != 0);

assert (iterator != NULL);

iterator = iterator->next;

}

template

void List::printList()

{

Nodeptr iter= first;

while (iter != NULL)

{

cout data

iter = iter->next;

}

cout

}

template

bool List:: 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

void List :: reverse(Nodeptr list)

{

Nodeptr temp = last;

if (temp == NULL)

return;

else

{

cout data

temp = temp->previous;

}

}

template

void List:: printReverse()

{

reverse(first);

}

template

bool List:: isSorted()

{

if (size ==0)

{

return isSorted();

}

else

reverse (last);

return true;

}

template

int List:: getIndex()

{

assert (!offEnd());

assert (iterator != NULL);

int count =1 ;

Nodeptr temp= first;

while (temp != iterator)

{

count++;

temp = temp->next;

}

return cout ;

}

template

void List:: advanceToIndex(int index)

{

assert(size!=0);

assert (iterator != NULL);

iterator = first;

for (int i = 1; i

{

iterator = iterator->next;

}

}

template

int List::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

int List:: binarySearch(int low, int high, listdata value)

{

if (high

return -1;

int mid = (low + high);

if (mid % 2 != 0)

{

return mid;

}

else

advanceToIndex(mid);

if (getIterator() == value)

{

return mid;

}

else if (value

{

return binarySearch(low, mid -1, value);

}

else

return binarySearch( low, mid +1, value);

}

#endif /* LIST_H_ */

5 4 2 2 3 2