Graph.h #pragma once #include <vector> #include <string> #include <map> typedef
ID: 3835421 • Letter: G
Question
Graph.h
#pragma once
#include <vector>
#include <string>
#include <map>
typedef int Vertex;
using namespace std;
class Graph {
public:
Graph(int n); // TO DO
int size(); // TO DO
void addLabel(Vertex i, string s); // TO DO
void addEdge(Vertex i, Vertex j); // TO DO
vector<Vertex> getAdjacentVertices(Vertex); // TO DO
Vertex getVertex(string label); // OPTIONAL: may help your code
string getLabel(Vertex n); // OPTIONAL: may help your code
private:
// TO DO
// member variables and functions to implement the public member functions
map<string,Vertex> labelsToInt;
map<Vertex,string> intToLabels;
vector<vector<bool>> adj;
};
// TO DO
// return a list of names that contain friends of friends of person
// names should not be repeated
vector<string> recommendFriends(Graph &graph, const string& person);
// COMPLETED
// read from a text file, the labels (names) to be associate with each vertex (int)
void readNamesFromFile(Graph &graph, const string& filename);
// COMPLETED
// read from a text file, the list of friends for each vertex (int)
void readFriendsFromFile(Graph &graph, const string& filename);
Graph.cpp
#include <fstream>
#include <iostream>
#include <sstream> // for std::istringstream
#include "Graph.h"
// TO DO
// initialize an undirected graph that can store at most n vertices
Graph::Graph(int n) {
}
// TO DO
// return the maximum number of vertices
int Graph::size() {
}
// TO DO
// give a string label to vertex
void Graph::addLabel(Vertex i, string s) {
}
// TO DO
// add an edge between vertices i and j
void Graph::addEdge(Vertex i, Vertex j) {
}
// TO DO
// return a vector of vertices adjacent to vertex n
vector<Vertex> Graph::getAdjacentVertices(Vertex n) {
}
// TO DO
// return a list of names that contain friends of friends of person
// names should not be repeated
vector<string> recommendFriends(Graph &graph, const string &person) {
}
// COMPLETED
// read from a text file, the labels (names) to be associate with each vertex (int)
void readNamesFromFile(Graph &graph, const string& filename) {
ifstream inputFile;
inputFile.open(filename);
if (!inputFile)
throw invalid_argument("Unable to open file " + filename);
string s;
int i;
while (!inputFile.eof()) {
inputFile >> i >> s;
// cout << "adding label " << i << ": " << s << endl;
graph.addLabel(i, s);
}
}
// COMPLETED
// read from a text file, the list of friends for each vertex (int)
void readFriendsFromFile(Graph &graph, const string& filename) {
ifstream inputFile;
inputFile.open(filename);
if (!inputFile)
throw invalid_argument("Unable to open file " + filename);
for (string line; getline(inputFile, line); ) {
istringstream iss(line);
int i;
iss >> i;
int j;
while (!iss.eof()) {
iss >> j;
// cout << "adding edge " << i << " to " << j << endl;
graph.addEdge(i, j);
}
}
}
main.cpp
#include <iostream>
#include <vector>
#include "Graph.h"
using namespace std;
template <typename E>
bool checkIfEqual(vector<E> actual, vector<E> correct);
int main() {
try {
{
// test basic graph operations
const int N = 3;
Graph g(N);
if (g.size() == N)
cout << "Number of vertices test passed" << endl;
else
cout << "Number of vertices test failed" << endl;
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 0);
g.addEdge(2, 0);
vector<Vertex> v = g.getAdjacentVertices(0);
if (checkIfEqual<Vertex>(v, { 1, 2 }))
cout << "Test Adjacent Vertices passed" << endl;
else
cout << "Test Adjacent Vertices failed" << endl;
v = g.getAdjacentVertices(1);
if (checkIfEqual<Vertex>(v, { 0}))
cout << "Test Adjacent Vertices passed" << endl;
else
cout << "Test Adjacent Vertices failed" << endl;
v = g.getAdjacentVertices(2);
if (checkIfEqual<Vertex>(v, { 0}))
cout << "Test Adjacent Vertices passed" << endl;
else
cout << "Test Adjacent Vertices failed" << endl;
}
{
Graph g(10); // build a social network graph
readFriendsFromFile(g, "friends10.txt");
readNamesFromFile(g, "names10.txt");
string name = "Jonathan";
cout << " Friend recommendations for " << name << ":" << endl;
vector<string> persons = recommendFriends(g, name);
for (unsigned i = 0; i < persons.size(); i++)
cout << " " << persons[i] << endl;
if (checkIfEqual<string>(persons, { "Youngeun", "Alfredo"}))
cout << "Recommendation test passed" << endl;
else
cout << "Recommendation test failed" << endl;
}
{// A larger example
Graph g(150); // build a social network graph
readFriendsFromFile(g, "friends140.txt");
readNamesFromFile(g, "names143.txt");
string name = "Jonathan";
cout << " Friend recommendations for " << name << ":" << endl;
vector<string> persons = recommendFriends(g, name);
for (unsigned i = 0; i < persons.size(); i++)
cout << " " << persons[i] << endl;
if (checkIfEqual<string>(persons, { "Alfredo", "Rakan", "Derek", "Julian", "Jackie", "Samrah", "Ryan", "Khadijah", "Alexandra", "Qiyuan", "Andrea", "Christopher" }))
cout << "Recommendation test (large graph) passed" << endl;
else
cout << "Recommendation test (large graph) failed" << endl;
}
}
catch (exception &e) {
cout << e.what() << endl;
}
system("pause");
}
template <typename E>
bool checkIfEqual(vector<E> actual, vector<E> correct) {
if (actual.size() != correct.size())
return false;
for (unsigned i = 0; i < actual.size(); i++) {
bool found = false;
for (unsigned j = 0; j < correct.size(); j++)
if (actual[i] == correct[j]) {
found = true;
break;
}
if (!found) return false;
}
return true;
}
friends10.txt
0 1 3
1 0 3 8 9
2 4 5 8 9
3 0 1 4
4 2 3 5 9
5 2 4
6
7
8 1 2
9 1 2 4
names10.txt
0 Kenny
1 Jonathan
2 Alfredo
3 Mohammadreza
4 Youngeun
5 Rakan
6 Omar
7 Katelyn
8 Gabriel
9 Samantha
friends140.txt
0 1 3 11 16 17
1 0 3 4 7 8
2 3 9 13 24 38
3 0 1 2 5 7
4 1 5 20 27 35
5 3 4 8 11 13
6 11 14 18 19 22
7 1 3 17 20 24
8 1 5 23 29 32
9 2 11 15 17 18
10 16 23 24 25 29
11 0 5 6 9 13
12 13 18 28 33 35
13 2 5 11 12 17
14 6 16 19 38 43
15 9 21 27 33 39
16 0 10 14 17 21
17 0 7 9 13 16 19 20 29 39 40 45 49 56 67 69 81 83 87 89 91 97 98 102 103 115 119 121 128 130
18 6 9 12 24 25
19 6 14 17 22 26
20 4 7 17 21 23
21 15 16 20 22 23
22 6 19 21 34 45
23 8 10 20 21 28
24 2 7 10 18 27
25 10 18 27 30 37
26 19 30 34 37 39
27 4 15 24 25 35
28 12 23 32 35 37
29 8 10 17 35 37
30 25 26 34 36 38
31 35 43 54 56 57
32 8 28 35 36 37
33 12 15 43 48 54
34 22 26 30 53 60
35 4 12 27 28 29 31 32 42 43 44 45 49 51 54 59 61 71 73 74 80 91 97 100 101 112 121 128 132 137
36 30 32 41 47 50
37 25 26 28 29 32 40 45 48 51 52 65 67 68 69 75 83 89 106 110 111 114 115 119 120 121 123 126 130 135 137
38 2 14 30 47 50
39 15 17 26 74 80
40 17 37 42 46 48
41 36 43 44 53 58
42 35 40 45 57 61
43 14 31 33 35 41 46 49 50 52 54 67 69 71 73 76 77 78 82 91 95 103 105 109 118 120 124 125 127 137 138 139
44 35 41 45 50 63
45 17 22 35 37 42 44 46 47 50 61 64 68 73 79 82 85 92 107 110 115 124 126 137 139
46 40 43 45 47 53
47 36 38 45 46 49
48 33 37 40 62 67
49 17 35 43 47 57
50 36 38 43 44 45 59 67 71 86 90 92 95 96 100 101 124 127 128 129 132 133
51 35 37 57 58 59
52 37 43 56 58 60
53 34 41 46 54 58
54 31 33 35 43 53 56 57 58 68 69 73 86 87 107 117 121 123 134 137 139
55 58 63 70 72 73
56 17 31 52 54 61
57 31 42 49 51 54 59 62 64 68 74 81 84 94 111 112 117 130 135 137
58 41 51 52 53 54 55 59 61 64 66 68 80 82 92 93 100 117 118 120 125 127 133 136 139
59 35 50 51 57 58 75 76 82 84 89 91 94 96 102 114 124 126 132 134 135 139
60 34 52 61 70 74
61 35 42 45 56 58 60 63 64 65 76 77 79 101 108 112 116 122 126 128 130 131 132 137 139
62 48 57 64 71 80
63 44 55 61 66 77
64 45 57 58 61 62 66 82 83 84 85 91 98 100 104 108 109 116 133 135 137 138
65 37 61 72 84 92
66 58 63 64 67 71
67 17 37 43 48 50 66 76 81 94 97 104 110 111 121 123 125 133
68 37 45 54 57 58 78 82 85 87 99 101 107 118 119 121 123
69 17 37 43 54 75
70 55 60 74 81 85
71 35 43 50 62 66 73 76 77 82 87 93 97 106 112
72 55 65 75 76 77
73 35 43 45 54 55 71 75 82 87 91 93 100 101 117 122
74 35 39 57 60 70 79 84 103 119 123 127 133 134 136 139
75 37 59 69 72 73 85 87 93 95 103 106 109 121 122 126 127 139
76 43 59 61 67 71 72 86 93 99 106 107 117 119 123 128 137
77 43 61 63 71 72 84 106 107 117 122 125 126 130 132 133 135
78 43 68 80 98 103
79 45 61 74 80 81
80 35 39 58 62 78 79 90 96 98 102 109 110 113 132 134 138 139
81 17 57 67 70 79 87 88 91 93 110 117 118 119 124 129 131 133
82 43 45 58 59 64 68 71 73 85 87 90 95 98 100 103 111 114 115 119 123 126 130 132
83 17 37 64 87 97
84 57 59 64 65 74 77 90 92 97 102 106 107 112 114 118 129
85 45 64 68 70 75 82 86 90 94 112 114 118 121 123 131 132
86 50 54 76 85 92
87 17 54 68 71 73 75 81 82 83 96 98 99 101 102 104 113 121 132 136 138
88 81 92 107 108 115
89 17 37 59 103 106
90 50 80 82 84 85 91 97 127
91 17 35 43 59 64 73 81 90 94 97 98 110 111 112 113 114 116 121 123 133 135 136 137
92 45 50 58 65 84 86 88 100 102 104 109 110 112 115 117 119 122 123 135
93 58 71 73 75 76 81 97 102 116 117 127 131 137 139
94 57 59 67 85 91 103 108 116 117 118 120 126 130 131 137 139
95 43 50 75 82 113
96 50 59 80 87 101
97 17 35 67 71 83 84 90 91 93 98 101 105 111 114 116 119 126
98 17 64 78 80 82 87 91 97 103 116 124 133 134 137 138
99 68 76 87 100 101
100 35 50 58 64 73 82 92 99 105 109 112 113 120 126
101 35 50 61 68 73 87 96 97 99 103 110 127 136
102 17 59 80 84 87 92 93 104 105 107 111 116 130 132 134
103 17 43 74 75 78 82 89 94 98 101 108 109 128 129 130 131 132 137 138
104 64 67 87 92 102 114 119 121 125 128 136
105 43 97 100 102 111
106 37 71 75 76 77 84 89 108 113 116 117 118 121 124 125 131 132 135
107 45 54 68 76 77 84 88 102 119 121 123 126 127 134 138 139
108 61 64 88 94 103 106 116 118 120 121 124 127 132
109 43 64 75 80 92 100 103 113 114 118 123 125 127 131
110 37 45 67 80 81 91 92 101 111 115 124 133 134
111 37 57 67 82 91 97 102 105 110 128 133 137
112 35 57 61 71 84 85 91 92 100 116 122 135
113 80 87 91 95 100 106 109 114 117 133 134
114 37 59 82 84 85 91 97 104 109 113 124 129 131 134
115 17 37 45 82 88 92 110 122 128 131
116 61 64 91 93 94 97 98 102 106 108 112 122 124 128 133 135
117 54 57 58 73 76 77 81 92 93 94 106 113 120 122 124 135 136
118 43 58 68 81 84 85 94 106 108 109 122 123 125 126 137 139
119 17 37 68 74 76 81 82 92 97 104 107 123
120 37 43 58 94 100 108 117 128 129 131 134 135 136
121 17 35 37 54 67 68 75 85 87 91 104 106 107 108 133 136
122 61 73 75 77 92 112 115 116 117 118 125 129 131 136
123 37 54 67 68 74 76 82 85 91 92 107 109 118 119 127 139
124 43 45 50 59 81 98 106 108 110 114 116 117 125 131 136 137
125 43 58 67 77 104 106 109 118 122 124 129 130 133
126 37 45 59 61 75 77 82 94 97 100 107 118 129 130 134
127 43 50 58 74 75 90 93 101 107 108 109 123 135
128 17 35 50 61 76 103 104 111 115 116 120 130 134 135 137
129 50 81 84 103 114 120 122 125 126 134 135 138
130 17 37 57 61 77 82 94 102 103 125 126 128 133 134 139
131 61 81 85 93 94 103 106 109 114 115 120 122 124 133 134 139
132 35 50 59 61 77 80 82 85 87 102 103 106 108
133 50 58 64 67 74 77 81 91 98 110 111 113 116 121 125 130 131 134 135 137
134 54 59 74 80 98 102 107 110 113 114 120 126 128 129 130 131 133
135 37 57 59 64 77 91 92 106 112 116 117 120 127 128 129 133
136 58 74 87 91 101 104 117 120 121 122 124
137 35 37 43 45 54 57 61 64 76 91 93 94 98 103 111 118 124 128 133
138 43 64 80 87 98 103 107 129
139 43 45 54 58 59 61 74 75 80 93 94 107 118 123 130 131
names143.txt
0 Kenny
1 Jonathan
2 Alfredo
3 Mohammadreza
4 Youngeun
5 Rakan
6 Omar
7 Katelyn
8 Gabriel
9 Samantha
10 Dylan
11 Derek
12 Anthony
13 Wyatt
14 Nancy
15 Brian
16 Julian
17 Jackie
18 Griffin
19 Elizabeth
20 Samrah
21 Yasmin
22 Kenneth
23 Ryan
24 Khadijah
25 Grant
26 Austin
27 Alexandra
28 Luisfernando
29 Andrea
30 Evan
31 Tony
32 Qiyuan
33 Kelcee
34 Ken
35 Christopher
36 Victor
37 Steven
38 Melissa
39 Edgar
40 Maysa
41 Sarah
42 Nicodemus
43 Raed
44 James
45 Alberto
46 Jazmin
47 Alexis
48 Andrew
49 Erick
50 Alyssa
51 Nowriz
52 Patrick
53 Kenji
54 Bianca
55 Abid
56 John
57 Hunter
58 Rene
59 Trung
60 Javier
61 Tien
62 Robby
63 Vikki
64 Mario
65 Alecsander
66 Raul
67 Rawabi
68 Timothy
69 Sergio
70 Bryan
71 Kunal
72 Salvatore
73 Yucheng
74 Aaron
75 Hasibullah
76 Angel
77 Lino
78 Hamad
79 Roman
80 Julia
81 Adam
82 Nikita
83 Chase
84 Justin
85 Dion
86 Ankit
87 Dennis
88 NicoPascal
89 Ali
90 Joseph
91 Randy
92 Lauren
93 LinThu
94 Jesus
95 Kyle
96 Zane
97 Tri
98 Alondra
99 Anh
100 Carla
101 Zulema
102 Michael
103 Nicholas
104 Jason
105 Gonzalo
106 Daniel
107 Leah
108 Mason
109 Brandon
110 Francisco
111 Bao
112 Shivam
113 Jimmy
114 Seth
115 Ian
116 Beren
117 Allen
118 William
119 Lucas
120 David
121 Jan
122 Carlos
123 Theresa
124 Cyrus
125 Kevin
126 Emmanuel
127 Rigel
128 BeauJayme
129 Vincent
130 Matthew
131 Eric
132 Arnold
133 Bill
134 Sri
135 Ethan
136 Jack
137 Alexander
138 Emmet
139 Joe
140 Mike
141 Arshya
142 Marco
#pragma once
#include <vector>
#include <string>
#include <map>
typedef int Vertex;
using namespace std;
class Graph {
public:
Graph(int n); // TO DO
int size(); // TO DO
void addLabel(Vertex i, string s); // TO DO
void addEdge(Vertex i, Vertex j); // TO DO
vector<Vertex> getAdjacentVertices(Vertex); // TO DO
Vertex getVertex(string label); // OPTIONAL: may help your code
string getLabel(Vertex n); // OPTIONAL: may help your code
private:
// TO DO
// member variables and functions to implement the public member functions
map<string,Vertex> labelsToInt;
map<Vertex,string> intToLabels;
vector<vector<bool>> adj;
};
// TO DO
// return a list of names that contain friends of friends of person
// names should not be repeated
vector<string> recommendFriends(Graph &graph, const string& person);
// COMPLETED
// read from a text file, the labels (names) to be associate with each vertex (int)
void readNamesFromFile(Graph &graph, const string& filename);
// COMPLETED
// read from a text file, the list of friends for each vertex (int)
void readFriendsFromFile(Graph &graph, const string& filename);
Explanation / Answer
I have developed the Graph.h file which contains Class Graph and included the comments for each part of the program.
Graph.h Program:
class Graph {
public:
Graph(int n);
int size();
void addLabel(Vertex i, string s);
void addEdge(Vertex i, Vertex j);
vector<Vertex> getAdjacentVertices(Vertex);
Vertex getVertex(string label);
string getLabel(Vertex n);
private:
private:
int n;
list<int> *graphAdj;
void graphDirected(int v, bool visited[]);
map<string,Vertex> labelsToInt;
map<Vertex,string> intToLabels;
vector<vector<bool>> graphAdj;
};
bool isConnected();
Graph getTranspose();
vector<string> recommendFriends(Graph &graph, const string& person);
Next comes the Graph.cpp file which is used to find the undirected graph and the No. of maximum vertices.
Graph.cpp Program:
// initialize an undirected graph that can store at most n vertices
Graph::Graph(int n) {
visited[v] = true;
list<int>::iterator i;
for (i = graphAdj[v].begin(); i != graphAdj[v].end(); ++i)
if (!visited[*i])
graphDirected(*i, visited);
}
// return the maximum number of vertices
int Graph::size() {
int countSize = 0;
for (int i = 0; i < cover.size(); i++)
if (cover[i] == 1)
countSize++;
return countSize;
}
// give a string label to vertex
void Graph::addLabel(Vertex i, string s) {
if (i.find(l) != i.end())
return i.find(l)->second;
else
return 0;
}
}
// add an edge between vertices i and j
void Graph::addEdge(Vertex i, Vertex j) {
graphAdj[v].push_back(w);
}
// return a vector of vertices adjacent to vertex n
vector<Vertex> Graph::getAdjacentVertices(Vertex n) {
bool visited[V];
for (int i = 0; i < V; i++)
visited[i] = false;
graphDirected(0, visited);
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
Graph g = recommendFriends();
for(int i = 0; i < V; i++)
visited[i] = false;
g.graphDirected(0, visited);
for (int i = 0; i < V; i++)
if (visited[i] == false)
return false;
return true;
}
vector<string> recommendFriends(Graph &graph, const string &person) {
Graph g(V);
for (int v = 0; v < V; v++)
{
list<int>::iterator i;
for(i = graphAdj[v].begin(); i != graphAdj[v].end(); ++i)
{
g.graphAdj[*i].push_back(v);
}
}
return g;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.