Please write the following code in the Graph.cpp and the WriteGraph.cpp. The Lis
ID: 3850003 • Letter: P
Question
Please write the following code in the Graph.cpp and the WriteGraph.cpp. The List.h is already done.
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
#include <iostream>
#include <cstdlib>
#include "List.h"
#include <vector>
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 <= getNumVertices() && v <=getNumVertices()
//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 <= getNumVertices() && v <=getNumVertices()
//removes vertex v from the adjacency list of vertex u
//and removes u from v.
/*** Additional Operations ***/
void printGraph(ostream& output);
//Prints the adjacency list of each vertex in the graph,
//vertex: <space separated list of adjacent vertices>
//Prints to the console or to an output file given the ostream parameter
private:
int vertices, edges; //number of edges and vertices
vector<List<int> > adj;
};
Here is the List header code:
#ifndef LIST_H_
#define LIST_H_
#include <iostream>
#include <cstddef>
#include <stddef.h>
#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;
void reverse(Nodeptr node);
bool isSorted(Nodeptr node);
int binarySearch(int low, int high, listdata data);
int size;
public:
/**Constructors and Destructors*/
List();
//Default constructor; initializes and empty list
//Postcondition:create a link list.
List(const List &list);
~List();
//Destructor. Frees memory allocated to the list
//Postcondition:frees the memory associated with the linked list.
/**Accessors*/
listdata getFirst();
//Returns the first element in the list
//Precondition:first should not be empty.
listdata getLast();
//Returns the last element in the list
//Precondition:last should not be empty.
bool isEmpty();
//Determines whether a list is empty.
int getSize();
//Returns the size of the list
/**Manipulation Procedures*/
void removeLast();
//Removes the value of the last element in the list
//Precondition:list should not be empty.
//Postcondition:Remove the last element of the list.
void removeFirst();
//Removes the value of the first element in the list
//Precondition:list should not be empty
//Postcondition:Remove the last element of the list.
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:insert the new element at the end of the list.
void insertFirst(listdata data);
//Inserts a new element at the start of the list
//If the list is empty, the new element becomes both first and last
//Postcondition:insert the new element at the beginning of the list.
/**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
void startIterator();
//postcondition: set the beginning of the element equal to iterator.
void removeIterator();
// postcondition: Remove the iterator.
void insertIterator(listdata data);
//precondition: list should not be empty.
//postcondition: insert the new iterator.
void advanceIterator();
listdata getIterator();
bool offEnd();
bool operator==(const List &list);
void printReverse();
//Wrapper function that calls the reverse helper function to print a list in reverse
//prints nothing if the List is empty
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()
void advanceToIndex(int index);
//Moves the iterator to the node whose index number is specified in the parameter
//Pre: size != 0
//Pre: index <= size
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(listdata data);
//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)
};
template<class listdata>
List<listdata>::List() :
first(NULL), last(NULL), iterator(NULL), size(0) {
}
template<class listdata>
List<listdata>::List(const List &list) :
size(list.size) {
if (list.first == NULL) {
first = last = iterator = NULL;
} else {
first = new Node(list.first->data);
Nodeptr temp = list.first;
iterator = first;
while (temp->next != NULL) {
temp = temp->next;
iterator->next = new Node(temp->data);
iterator = iterator->next;
}
last = iterator;
iterator = NULL;
}
}
template<class listdata>
List<listdata>::~List() {
Nodeptr cursor = first;
Nodeptr temp;
while (cursor != NULL) {
temp = cursor->next;
delete cursor;
cursor = temp;
}
}
template<class listdata>
void List<listdata>::reverse(Nodeptr node) {
node = last;
while (node->previous != NULL) {
cout << node->data << " ";
node = node->previous;
}
cout << first->data << endl;
}
template<class listdata>
void List<listdata>::printList() {
Nodeptr temp = first;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
template<class listdata>
void List<listdata>::printReverse() {
Nodeptr temp = last;
reverse(temp);
}
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>::insertLast(listdata data) {
if (size == 0) {
Nodeptr N = new Node(data);
first = last = N;
} else {
Nodeptr N = new Node(data);
last->next = N;
N->previous = last;
last = N;
}
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;
first->previous = NULL;
size--;
}
}
template<class listdata>
void List<listdata>::removeLast() {
assert(size != 0);
if (size == 1) {
delete last;
last = first = NULL;
size = 0;
}
else {
Nodeptr temp = last;
last = last->previous;
cout << last->data << endl;
delete temp;
last->next = NULL;
size--;
}
}
template<class listdata>
void List<listdata>::insertIterator(listdata data) {
assert(size != 0);
assert(iterator!= NULL);
if (iterator == last) {
insertLast(data);
} else {
Nodeptr N = new Node(data);
N->next = iterator->next;
N->previous = iterator;
iterator->next->previous = N;
iterator->next = N;
}
size++;
}
template<class listdata>
void List<listdata>::startIterator() {
iterator = first;
}
template<class listdata>
void List<listdata>::advanceIterator() {
assert(iterator != NULL);
assert(size != 0);
iterator = iterator->next;
}
template<class listdata>
void List<listdata>::removeIterator() {
assert(iterator != NULL);
assert(size != 0);
if (size == 1) {
delete iterator;
iterator = first = last = NULL;
size = 0;
} else if (iterator == first) {
removeFirst();
} else if (iterator == last) {
removeLast();
} else {
iterator->previous->next = iterator->next;
iterator->next->previous = iterator->previous;
delete iterator;
iterator = NULL;
size--;
}
}
template<class listdata>
void List<listdata>::advanceToIndex(int index) {
assert(size != 0);
assert(index <= size);
iterator = first;
for (int i = 1; i < index; i++) {
iterator = iterator->next;
}
}
template<class listdata>
int List<listdata>::getIndex() {
assert(size != 0);
assert(!offEnd());
Nodeptr n = first;
int count = 1;
while (n != iterator) {
n = n->next;
count++;
}
return count;
}
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>::getFirst() {
assert(first != NULL);
return first->data;
}
template<class listdata>
listdata List<listdata>::getLast() {
assert(last != NULL);
return last->data;
}
template<class listdata>
bool List<listdata>::offEnd() {
if (iterator == NULL) {
return true;
} else {
return false;
}
}
template<class listdata>
listdata List<listdata>::getIterator() {
assert(iterator!= NULL);
return iterator->data;
}
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>
bool List<listdata>::isSorted(Nodeptr node) {
if(node == last)
{
return true;
}
else if((node->data) > (node->next->data))
{
return false;
}
else
{
return isSorted(node->next);
}
}
template<class listdata>
int List<listdata>::binarySearch(int low, int high, listdata data) {
if (high < low) {
return -1;
}
int mid = low + (high - low) / 2;
advanceToIndex(mid);
if (getIterator() == data) {
return mid;
}
else if (getIterator() > data) {
return binarySearch(low, mid - 1, data);
} else {
return binarySearch(mid + 1, high, data);
}
}
template<class listdata>
bool List<listdata>::isSorted() {
Nodeptr temp = first;
return isSorted(temp);
}
template<class listdata>
int List<listdata>::linearSearch(listdata data) {
assert(size != 0);
int count = 0;
Nodeptr N = first;
while (N != NULL) {
count++;
if (N->data == data) {
cout << count << endl;
return count;
}
N = N->next;
}
return -1;
}
template<class listdata>
int List<listdata>::binarySearch(listdata data) {
assert(size != 0);
assert(isSorted());
return binarySearch(1, size, data);
}
#endif /* LIST_H_ */
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
Example Input File:
7
1 4
1 5
4 5
2 3
2 6
3 7
6 7
Example Output File:
1: 4 5
2: 3 6
3: 2 7
4: 1 5
5: 1 4
6: 2 7
7: 3 6
Total vertices: 7
Total edges: 7
WriteGraph.cpp
Your WriteGraph.cpp should work identically to the sample output below.
It should prompt a user for the name of a file and then use a loop to report an error if the file name is not found in the directory.
It should read in the contents of the file specified by the user
It should then prompt the user for the name of an output file and print the graph inside this file:
Welcome to WriteGraph!
Enter the name of the file containing the graph information: asdkshjkdshljkdsf
Invalid file name!
Please enter the name of the file: input
Invalid file name!
Please enter the name of the file: input.txt
***Reading from input.txt***
Please enter the name of the output file: output.txt
Thank you! Your Graph is now written to output.txt!
Explanation / Answer
#include "dirtyd.h"
#include "GLOWWORM.h"
#include "MyBMP.h"
#define OUT_BMPFILENAME "HW06_PR01.bmp"
#include
#include
#define BBC_PACKET_LENGTH_BYTES (1024)
#define BBC_MESSAGE_LENGTH_BYTES ( 32) // bytes, not bits
#define BBC_CHECKSUM_BITS ( 8) // bits
#define BBC_PACKET_LENGTH_BITS (8 * BBC_PACKET_LENGTH_BYTES)
#define BBC_MESSAGE_LENGTH_BITS (8 * BBC_MESSAGE_LENGTH_BYTES)
#define isSet(c,b) ((c) & (1 << (b)))
#define TASKPRINT (!TRUE)
#define TASK(s) if(TASKPRINT) printf("%s ", (s))
#define WIDTH (640)
#define HEIGHT (480)
#define fileREAD "message_tx.txt"
//#define DEBUG_ON
#ifdef DEBUG_ON
#define DEBUG(s) s
#else
#define DEBUG(s)
#endif
uint8_t *bbc_encode_byte(GLOWWORM *gw, uint8_t *packet, uint8_t c, MyBMP *bmp)
{
for (int bit = 7; bit >= 0; bit--)
{
uint8_t bitValue = isSet(c, bit);
uint64_t hash = GLOWWORM_addBit(gw, !!bitValue);
uint32_t chip = hash % BBC_PACKET_LENGTH_BITS;
printf("%c[%i] = %u (chip = %u) ", c, bit, !!bitValue, chip);
packet[chip] = TRUE;
if (!!bitValue == 1){
MyBMP_drawPixel(bmp, chip/WIDTH, chip%WIDTH, 0, 0, 0);
// MyBMP_drawPixel(bmp, chip%WIDTH, chip%HEIGHT, 255, 255, 255);
// MyBMP_drawCircle(bmp, chip%WIDTH, chip%HEIGHT, 5,
// 0, 0, 0, 1);
printf("%i and %i ", chip/WIDTH, chip%WIDTH);
}else {
MyBMP_drawPixel(bmp, chip/WIDTH, chip%WIDTH, 255, 255, 255);
}
//packet[GLOWWORM_addBit(gw, isSet(c,bit)) % (BBC_PACKET_LENGTH_BITS)] = TRUE;
}
return packet;
}
uint8_t *bbc_encode(uint8_t *packet, uint8_t *s, MyBMP *bmp)
{
int byte = 0;
if (NULL == packet)
{
TASK("Create packet (1 byte per bit for convenience)");
packet = (uint8_t *) malloc(BBC_PACKET_LENGTH_BITS * sizeof(uint8_t));
if (!packet)
{
printf("Failed to allocate packet -- abort! ");
exit(EXIT_FAILURE);
}
for (int i = 0; i < BBC_PACKET_LENGTH_BITS; i++)
packet[i] = 0;
}