Recall that a complete graph is one in which every node is connected to every ot
ID: 3597586 • Letter: R
Question
Recall that a complete graph is one in which every node is connected to every other node by an edge. In this problem, you will write a function to test whether or not a graph (based on an adjacency matrix) is complete
• completeGraph.cpp contains a graph class based on an adjacency matrix.
• This file has an empty function called complete.
• Fill in this function so that it tests the graph to check if it is complete or not and returns a boolean.
• The main function tests this function on a graph that is complete and one that is not. For grading purposes your function may be tested on other graphs as well.
//
// completeGraph.cpp
#include <cstring>
#include <iostream>
using namespace std;
template <int N>
class Graph {
public:
// start with no edges at all
Graph() {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
matrix[i][j] = 0;
}
}
count = 0;
}
// insert an edge
void insertEdge(const char fromcity[], const char tocity[], int
cost) {
int from = lookup(fromcity);
int to = lookup(tocity);
matrix[from][to] = cost;
matrix[to][from] = cost;
}
// lookup the index of a name
int lookup(const char name[]) const {
for(int i = 0; i < count; i++) {
if(strcmp(names[i], name) == 0) {
return i;
}
}
return -1;
}
// return name of an index
const char* name(int index) const {
return names[index];
}
// insert a node
void insertNode(const char* name) {
strcpy(names[count], name);
count++;
}
// return the cost of an edge or 0 for none
int getCost(int from, int to) const {
return matrix[from][to];
}
// remove an edge
void removeEdge(const char fromcity[], const char tocity[]) {
int from = lookup(fromcity);
int to = lookup(tocity);
matrix[from][to] = 0;
matrix[to][from] = 0;
}
// return the number of nodes
int size() const {
return count;
}
// return whether the graph is complete
bool complete() const {
// fill in!
}
private:
int matrix[N][N];
char names[N][25];
int count;
};
int main() {
Graph<5> graph;
graph.insertNode("A");
graph.insertNode("B");
graph.insertNode("C");
graph.insertNode("D");
graph.insertNode("E");
graph.insertEdge("A", "B", 1);
graph.insertEdge("A", "C", 1);
graph.insertEdge("A", "D", 1);
graph.insertEdge("A", "E", 1);
graph.insertEdge("B", "C", 1);
graph.insertEdge("B", "D", 1);
graph.insertEdge("B", "E", 1);
graph.insertEdge("C", "D", 1);
graph.insertEdge("C", "E", 1);
graph.insertEdge("D", "E", 1);
// should print "Complete!"
if(graph.complete()) {
cout << "Complete!" << endl;
} else {
cout << "Not complete!" << endl;
}
// remove an edge and try it again
graph.removeEdge("B", "C");
// should print "Not complete!"
if(graph.complete()) {
cout << "Complete!" << endl;
} else {
cout << "Not complete!" << endl;
}
return 0;
}
Explanation / Answer
#include <cstring>
#include <iostream>
using namespace std;
template <int N>
class Graph {
public:
// start with no edges at all
Graph() {
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
matrix[i][j] = 0;
}
}
count = 0;
}
// insert an edge
void insertEdge(const char fromcity[], const char tocity[], int
cost) {
int from = lookup(fromcity);
int to = lookup(tocity);
matrix[from][to] = cost;
matrix[to][from] = cost;
}
// lookup the index of a name
int lookup(const char name[]) const {
for(int i = 0; i < count; i++) {
if(strcmp(names[i], name) == 0) {
return i;
}
}
return -1;
}
// return name of an index
const char* name(int index) const {
return names[index];
}
// insert a node
void insertNode(const char* name) {
strcpy(names[count], name);
count++;
}
// return the cost of an edge or 0 for none
int getCost(int from, int to) const {
return matrix[from][to];
}
// remove an edge
void removeEdge(const char fromcity[], const char tocity[]) {
int from = lookup(fromcity);
int to = lookup(tocity);
matrix[from][to] = 0;
matrix[to][from] = 0;
}
// return the number of nodes
int size() const {
return count;
}
// return whether the graph is complete
bool complete() const {
// fill in!
}
private:
int matrix[N][N];
char names[N][25];
int count;
};
int main() {
Graph<5> graph;
graph.insertNode("A");
graph.insertNode("B");
graph.insertNode("C");
graph.insertNode("D");
graph.insertNode("E");
graph.insertEdge("A", "B", 1);
graph.insertEdge("A", "C", 1);
graph.insertEdge("A", "D", 1);
graph.insertEdge("A", "E", 1);
graph.insertEdge("B", "C", 1);
graph.insertEdge("B", "D", 1);
graph.insertEdge("B", "E", 1);
graph.insertEdge("C", "D", 1);
graph.insertEdge("C", "E", 1);
graph.insertEdge("D", "E", 1);
// should print "Complete!"
if(graph.complete()) {
cout << "Complete!" << endl;
} else {
cout << "Not complete!" << endl;
}
// remove an edge and try it again
graph.removeEdge("B", "C");
// should print "Not complete!"
if(graph.complete()) {
cout << "Complete!" << endl;
} else {
cout << "Not complete!" << endl;
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.