0 10 21 21 32 43 43 54 54 65 6 #include <iostream> #include <fstream> #include <
ID: 3708536 • Letter: 0
Question
0 10 21 21 32 43 43 54 54 65 6#include <iostream> #include <fstream>
#include <ctime> #include <ratio> #include <chrono> #include <time.h> #include <stdlib.h>
#include <string> #include <cstring> // for string tokenizer and c-style string processing
using namespace std;
// implementing the dynamic List ADT using Linked List
class Node{ private: int data; Node* nextNodePtr; public: Node(){} void setData(int d){ data = d; } int getData(){ return data; } void setNextNodePtr(Node* nodePtr){ nextNodePtr = nodePtr; } Node* getNextNodePtr(){ return nextNodePtr; } };
class List{
private: Node *headPtr; public: List(){ headPtr = new Node(); headPtr->setNextNodePtr(0); } Node* getHeadPtr(){ return headPtr; } bool isEmpty(){ if (headPtr->getNextNodePtr() == 0) return true; return false; } void insert(int data){ Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; while (currentNodePtr != 0){ prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); } Node* newNodePtr = new Node(); newNodePtr->setData(data); newNodePtr->setNextNodePtr(0); prevNodePtr->setNextNodePtr(newNodePtr); } void insertAtIndex(int insertIndex, int data){ Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; int index = 0; while (currentNodePtr != 0){ if (index == insertIndex) break; prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); index++; } Node* newNodePtr = new Node(); newNodePtr->setData(data); newNodePtr->setNextNodePtr(currentNodePtr); prevNodePtr->setNextNodePtr(newNodePtr); } int read(int readIndex){ Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; int index = 0; while (currentNodePtr != 0){ if (index == readIndex) return currentNodePtr->getData(); prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); index++; } return -1; // an invalid value indicating // index is out of range } void modifyElement(int modifyIndex, int data){ Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; int index = 0; while (currentNodePtr != 0){ if (index == modifyIndex){ currentNodePtr->setData(data); return; } prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); index++; } } void deleteElementAtIndex(int deleteIndex){ Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; Node* nextNodePtr = headPtr; int index = 0; while (currentNodePtr != 0){ if (index == deleteIndex){ nextNodePtr = currentNodePtr->getNextNodePtr(); break; } prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); index++; } prevNodePtr->setNextNodePtr(nextNodePtr); } void deleteElement(int deleteData){ Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; Node* nextNodePtr = headPtr; while (currentNodePtr != 0){ if (currentNodePtr->getData() == deleteData){ nextNodePtr = currentNodePtr->getNextNodePtr(); break; } prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); } prevNodePtr->setNextNodePtr(nextNodePtr); } void IterativePrint(){ Node* currentNodePtr = headPtr->getNextNodePtr(); while (currentNodePtr != 0){ cout << currentNodePtr->getData() << " "; currentNodePtr = currentNodePtr->getNextNodePtr(); } cout << endl; } // add any required member function here };
class Graph{ private: int numNodes; List* adjacencyList; public: Graph(int n){ numNodes = n; adjacencyList = new List[numNodes]; } void addEdge(int u, int v){
adjacencyList[u].insert(v); adjacencyList[v].insert(u);
} List getNeighborList(int id){ return adjacencyList[id]; } // add any required member function here
};
int main(){
string graphEdgesFilename; cout << "Enter the file name for the edges of the graph: "; cin >> graphEdgesFilename; int numNodes; cout << "Enter number of nodes: "; cin >> numNodes;
Graph graph(numNodes); ifstream graphEdgeFileReader(graphEdgesFilename); if (!graphEdgeFileReader){ cout << "File cannot be opened!! "; return 0; }
int numCharsPerLine = 25; char *line = new char[numCharsPerLine]; // '25' is the maximum number of characters per line graphEdgeFileReader.getline(line, numCharsPerLine, ' '); // ' ' is the delimiting character to stop reading the line while (graphEdgeFileReader){ char* cptr = strtok(line, " "); string uNodeToken(cptr); int uNodeID = stoi(uNodeToken); cptr = strtok(NULL, " "); string vNodeToken(cptr); int vNodeID = stoi(vNodeToken); graph.addEdge(uNodeID, vNodeID); graphEdgeFileReader.getline(line, numCharsPerLine, ' '); }
cout << endl;
// add code here to find and print the probabilities of finding vertices with certain degree // and compute the average degree based on these probabilities return 0; } #include <iostream> #include <fstream>
#include <ctime> #include <ratio> #include <chrono> #include <time.h> #include <stdlib.h>
#include <string> #include <cstring> // for string tokenizer and c-style string processing
using namespace std;
// implementing the dynamic List ADT using Linked List
class Node{ private: int data; Node* nextNodePtr; public: Node(){} void setData(int d){ data = d; } int getData(){ return data; } void setNextNodePtr(Node* nodePtr){ nextNodePtr = nodePtr; } Node* getNextNodePtr(){ return nextNodePtr; } };
class List{
private: Node *headPtr; public: List(){ headPtr = new Node(); headPtr->setNextNodePtr(0); } Node* getHeadPtr(){ return headPtr; } bool isEmpty(){ if (headPtr->getNextNodePtr() == 0) return true; return false; } void insert(int data){ Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; while (currentNodePtr != 0){ prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); } Node* newNodePtr = new Node(); newNodePtr->setData(data); newNodePtr->setNextNodePtr(0); prevNodePtr->setNextNodePtr(newNodePtr); } void insertAtIndex(int insertIndex, int data){ Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; int index = 0; while (currentNodePtr != 0){ if (index == insertIndex) break; prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); index++; } Node* newNodePtr = new Node(); newNodePtr->setData(data); newNodePtr->setNextNodePtr(currentNodePtr); prevNodePtr->setNextNodePtr(newNodePtr); } int read(int readIndex){ Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; int index = 0; while (currentNodePtr != 0){ if (index == readIndex) return currentNodePtr->getData(); prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); index++; } return -1; // an invalid value indicating // index is out of range } void modifyElement(int modifyIndex, int data){ Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; int index = 0; while (currentNodePtr != 0){ if (index == modifyIndex){ currentNodePtr->setData(data); return; } prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); index++; } } void deleteElementAtIndex(int deleteIndex){ Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; Node* nextNodePtr = headPtr; int index = 0; while (currentNodePtr != 0){ if (index == deleteIndex){ nextNodePtr = currentNodePtr->getNextNodePtr(); break; } prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); index++; } prevNodePtr->setNextNodePtr(nextNodePtr); } void deleteElement(int deleteData){ Node* currentNodePtr = headPtr->getNextNodePtr(); Node* prevNodePtr = headPtr; Node* nextNodePtr = headPtr; while (currentNodePtr != 0){ if (currentNodePtr->getData() == deleteData){ nextNodePtr = currentNodePtr->getNextNodePtr(); break; } prevNodePtr = currentNodePtr; currentNodePtr = currentNodePtr->getNextNodePtr(); } prevNodePtr->setNextNodePtr(nextNodePtr); } void IterativePrint(){ Node* currentNodePtr = headPtr->getNextNodePtr(); while (currentNodePtr != 0){ cout << currentNodePtr->getData() << " "; currentNodePtr = currentNodePtr->getNextNodePtr(); } cout << endl; } // add any required member function here };
class Graph{ private: int numNodes; List* adjacencyList; public: Graph(int n){ numNodes = n; adjacencyList = new List[numNodes]; } void addEdge(int u, int v){
adjacencyList[u].insert(v); adjacencyList[v].insert(u);
} List getNeighborList(int id){ return adjacencyList[id]; } // add any required member function here
};
int main(){
string graphEdgesFilename; cout << "Enter the file name for the edges of the graph: "; cin >> graphEdgesFilename; int numNodes; cout << "Enter number of nodes: "; cin >> numNodes;
Graph graph(numNodes); ifstream graphEdgeFileReader(graphEdgesFilename); if (!graphEdgeFileReader){ cout << "File cannot be opened!! "; return 0; }
int numCharsPerLine = 25; char *line = new char[numCharsPerLine]; // '25' is the maximum number of characters per line graphEdgeFileReader.getline(line, numCharsPerLine, ' '); // ' ' is the delimiting character to stop reading the line while (graphEdgeFileReader){ char* cptr = strtok(line, " "); string uNodeToken(cptr); int uNodeID = stoi(uNodeToken); cptr = strtok(NULL, " "); string vNodeToken(cptr); int vNodeID = stoi(vNodeToken); graph.addEdge(uNodeID, vNodeID); graphEdgeFileReader.getline(line, numCharsPerLine, ' '); }
cout << endl;
// add code here to find and print the probabilities of finding vertices with certain degree // and compute the average degree based on these probabilities return 0; } You are given the code of graph implementation in which the information of the neighbors of the nodes (i.e., the adjacency list) ?s stored as an array of linked lists. The code for the List class, implemented as a Singly Linked List, is also given. Note that the implementation assumes the vertices are labeled from 0 to N-1, where N is the number of vertices in the graph. Your tasks in this project are to: (i add member functions to the List class and the Graph class so that we could find the degree (the number of neighbors) for any node in the graph (ii) after implementing the required member functions, add code in the main function to print the degrees of the vertices in the graph as well as compute and print the probability of finding vertices with a certain degree (ranging from 1 to N-1, where N is the number of vertices in the graph) and the average degree of the vertices in the given graph based on these probabilities (computed as the weighted average of the number of vertices with the possible degree values, as shown in the slides). Test your code with a connected graph of 10 vertices or more such that the degree of any vertex is at least 1 and is at most N-1 (where N is the number of vertices in the graph) The edgeList is passed as input to your program. The edges of a graph (edgeList) are stored as an ordered pair of vertices with the ID of the first vertex in the pair being always less than the ID of the second vertex in the pair. For example, the edgeList for the graph below is shown alongside. 0 2 3 5 2 4 6 5 6 A sample screenshot of the output for the above 7-vertex graph is shown below. Your code should generate a similar output for your test graph of 10 or more vertices. nter the file nane for the edges of the graph: edgeList.txt nter nunber of nodes: ? gree of vertex B is 2 gree of vertex 1 is 3 gree of vertex 2 is 3 gree of vertex 3 is 3 gree of vertex 4 is 4 gree of vertex 5 is 3 gree of vertex 6 is2 bability of finding a vertex with degree 1 is B robability of finding a vertex ith degree 2 is 8.285714 robability of finding a vertex with degree 3 is 8.571429 bability of finding a vertex with degree 4 is 8.142857 robability of finding a vertex with degree 5 is 8 robability of finding a vertex with degree 6 is 8 verage Degree is 2.85714
Explanation / Answer
Hello There,
The following things are added to the code provided to support the requested functionality.
A method int sizeOfList() is added to the class List which returns the size of the list. This method is needed as the size of neighbour list of any vertex is its degree.
Code to compute degrees of each of the vertices is added to the main method.
PFB code in full and the output of test run.
Prog.cpp
------------------------------------------
#include <iostream>
#include <fstream>
#include <ctime>
#include <ratio>
#include <chrono>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <cstring> // for string tokenizer and c-style string processing
using namespace std;
// implementing the dynamic List ADT using Linked List
class Node{
private:
int data;
Node* nextNodePtr;
public:
Node(){}
void setData(int d){
data = d;
}
int getData(){
return data;
}
void setNextNodePtr(Node* nodePtr){
nextNodePtr = nodePtr;
}
Node* getNextNodePtr(){
return nextNodePtr;
}
};
class List{
private:
Node *headPtr;
public:
List(){
headPtr = new Node();
headPtr->setNextNodePtr(0);
}
Node* getHeadPtr(){
return headPtr;
}
bool isEmpty(){
if (headPtr->getNextNodePtr() == 0)
return true;
return false;
}
void insert(int data){
Node* currentNodePtr = headPtr->getNextNodePtr();
Node* prevNodePtr = headPtr;
while (currentNodePtr != 0){
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr->getNextNodePtr();
}
Node* newNodePtr = new Node();
newNodePtr->setData(data);
newNodePtr->setNextNodePtr(0);
prevNodePtr->setNextNodePtr(newNodePtr);
}
void insertAtIndex(int insertIndex, int data){
Node* currentNodePtr = headPtr->getNextNodePtr();
Node* prevNodePtr = headPtr;
int index = 0;
while (currentNodePtr != 0){
if (index == insertIndex)
break;
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr->getNextNodePtr();
index++;
}
Node* newNodePtr = new Node();
newNodePtr->setData(data);
newNodePtr->setNextNodePtr(currentNodePtr);
prevNodePtr->setNextNodePtr(newNodePtr);
}
int read(int readIndex){
Node* currentNodePtr = headPtr->getNextNodePtr();
Node* prevNodePtr = headPtr;
int index = 0;
while (currentNodePtr != 0){
if (index == readIndex)
return currentNodePtr->getData();
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr->getNextNodePtr();
index++;
}
return -1; // an invalid value indicating
// index is out of range
}
void modifyElement(int modifyIndex, int data){
Node* currentNodePtr = headPtr->getNextNodePtr();
Node* prevNodePtr = headPtr;
int index = 0;
while (currentNodePtr != 0){
if (index == modifyIndex){
currentNodePtr->setData(data);
return;
}
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr->getNextNodePtr();
index++;
}
}
void deleteElementAtIndex(int deleteIndex){
Node* currentNodePtr = headPtr->getNextNodePtr();
Node* prevNodePtr = headPtr;
Node* nextNodePtr = headPtr;
int index = 0;
while (currentNodePtr != 0){
if (index == deleteIndex){
nextNodePtr = currentNodePtr->getNextNodePtr();
break;
}
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr->getNextNodePtr();
index++;
}
prevNodePtr->setNextNodePtr(nextNodePtr);
}
void deleteElement(int deleteData){
Node* currentNodePtr = headPtr->getNextNodePtr();
Node* prevNodePtr = headPtr;
Node* nextNodePtr = headPtr;
while (currentNodePtr != 0){
if (currentNodePtr->getData() == deleteData){
nextNodePtr = currentNodePtr->getNextNodePtr();
break;
}
prevNodePtr = currentNodePtr;
currentNodePtr = currentNodePtr->getNextNodePtr();
}
prevNodePtr->setNextNodePtr(nextNodePtr);
}
void IterativePrint(){
Node* currentNodePtr = headPtr->getNextNodePtr();
while (currentNodePtr != 0){
cout << currentNodePtr->getData() << " ";
currentNodePtr = currentNodePtr->getNextNodePtr();
}
cout << endl;
}
// add any required member function here
// returns the size of list
int sizeOfList(){
int size = 0;
Node* currentNodePtr = headPtr->getNextNodePtr();
while (currentNodePtr != 0){
size++;
currentNodePtr = currentNodePtr->getNextNodePtr();
}
return size;
}
};
class Graph{
private:
int numNodes;
List* adjacencyList;
public:
Graph(int n){
numNodes = n;
adjacencyList = new List[numNodes];
}
void addEdge(int u, int v){
adjacencyList[u].insert(v);
adjacencyList[v].insert(u);
}
List getNeighborList(int id){
return adjacencyList[id];
}
// add any required member function here
};
int main(){
string graphEdgesFilename;
cout << "Enter the file name for the edges of the graph: ";
cin >> graphEdgesFilename;
int numNodes;
cout << "Enter number of nodes: ";
cin >> numNodes;
Graph graph(numNodes);
ifstream graphEdgeFileReader(graphEdgesFilename);
if (!graphEdgeFileReader){
cout << "File cannot be opened!! ";
return 0;
}
int numCharsPerLine = 25;
char *line = new char[numCharsPerLine];
// '25' is the maximum number of characters per line
graphEdgeFileReader.getline(line, numCharsPerLine, ' ');
// ' ' is the delimiting character to stop reading the line
while (graphEdgeFileReader){
char* cptr = strtok(line, " ");
string uNodeToken(cptr);
int uNodeID = stoi(uNodeToken);
cptr = strtok(NULL, " ");
string vNodeToken(cptr);
int vNodeID = stoi(vNodeToken);
graph.addEdge(uNodeID, vNodeID);
graphEdgeFileReader.getline(line, numCharsPerLine, ' ');
}
cout << endl;
// add code here to find and print the probabilities of finding vertices with certain degree
// and compute the average degree based on these probabilities
int degree[numNodes];
int totalDegree = 0;
int verticesWithDegrees[numNodes];
for(int i=0; i<numNodes; i++){
verticesWithDegrees[i] = 0;
}
for(int i=0; i<numNodes; i++){
degree[i] = graph.getNeighborList(i).sizeOfList();
cout << "degree of vertex " << i << " is " << degree[i] << endl;
totalDegree += degree[i];
verticesWithDegrees[degree[i]]++;
}
cout << endl;
for(int i=1; i<numNodes; i++){
cout << "Probability of finding vertex with degree " << i << " is " << verticesWithDegrees[i]/(double)numNodes << endl;
}
cout << endl;
cout << "Average Degree is " << totalDegree/(double)numNodes << endl;
return 0;
}
----------------------------------------
Test run:
---------------------------------------------
$ cat edges
0 1
0 2
1 2
1 3
2 4
3 4
3 5
4 5
4 6
5 6
$ g++ -std=c++11 Prog.cpp
$ ./a.out
Enter the file name for the edges of the graph: edges
Enter number of nodes: 7
degree of vertex 0 is 2
degree of vertex 1 is 3
degree of vertex 2 is 3
degree of vertex 3 is 3
degree of vertex 4 is 4
degree of vertex 5 is 3
degree of vertex 6 is 2
Probability of finding vertex with degree 1 is 0
Probability of finding vertex with degree 2 is 0.285714
Probability of finding vertex with degree 3 is 0.571429
Probability of finding vertex with degree 4 is 0.142857
Probability of finding vertex with degree 5 is 0
Probability of finding vertex with degree 6 is 0
Average Degree is 2.85714
$
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.