Question

In this exercise you're going to implement a graph class using an adjacency matrix of size 26x26. This allows up to 26 vertices, which will be denoted by the uppercase letters A .. Z. Initially a graph is empty, and then vertices and edges are added. Edges are directed, and have weights. Example: (A, B, 100) denotes an edge from A to B with weight 100; there is no edge from B to A unless one is explicitly added.

A main program is provided in "main.cpp" for testing. Your assignment is to implement "graph.h" and define a graph class; you must create the class from scratch, do not use templates. Inside your class, the adjacency matrix should be defined in the private section as follows:

int matrix[26][26];

Row 0 of the matrix denotes the edges starting at vertex A; row 1 denotes the edges starting at vertex B, etc. Similarly, column 0 denotes the edges ending at vertex A, column 1 denotes the edges ending at vertex B, etc. Example: the edge (A, B, 100) is represented by matrix[0][1] == 100. Since edge weights will be 0 or positive, the graph constructor should initialize the matrix to -1 (denoting no edge).

Add the following functions to your graph class, exactly as defined here:

// add the vertex v to the graph

void addvertex(char v);

// add the edge (from, to, weight) to the graph, but only if

// the vertices from and to have been added to the graph

void addedge(char from, char to, int weight);

// return the weight on the edge (from, to, ?); return -1 if no edge exists

int getweight(char from, char to);

// returns the vertices in the graph, in order A .. Z

vector<char> vertices();

// returns the neighbors of a vertex v, i.e. all vertices you can reach from

// v by traversing one edge.

vector<char> neighbors(char v);

Since a graph is initially empty, you'll need another data structure to keep track of vertices as they are added to the graph. You can use a vector, or a boolean array, or whatever you prefer. Be sure to initialize this data structure (if necessary) in the constructor.

/*graph.h*/ is the file to work on

#pragma once

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class graph
{
//
// TODO:
//
};

/*main.cpp*/ is a read only file

#include <iostream>
#include <vector>
#include <string>

#include "graph.h"

using namespace std;

void outputGraph(graph& g)
{
vector<char> vertices = g.vertices();

cout << "**Vertices: ";

for (char c : vertices)
{
cout << c << " ";
}

cout << endl;

cout << "**Edges: ";

for (char v : vertices)
{
vector<char> neighbors = g.neighbors(v);

for (char n : neighbors)
{
int weight = g.getweight(v, n);
cout << "(" << v << "," << n << "," << weight << ") ";
}
}

cout << endl;
}

int main()
{
graph g;
string input;

//
// Input vertices as single uppercase letters: A B C ...
//
cout << "Enter vertices as single letters, separated by spaces, end with #> ";
cin >> input;

while (input != "#")
{
char vertex = input[0];

g.addvertex(vertex);

cin >> input;
}

cout << endl;

//
// Now input edges:
//
string src, dest, weight;

cout << "Enter edge as LETTER LETTER WEIGHT, or #> ";
cin >> src;

while (src != "#")
{
cin >> dest;
cin >> weight;

//cout << src << ", " << dest << ", " << weight << endl;

g.addedge(src[0], dest[0], stoi(weight));

cout << "Enter edge as LETTER LETTER WEIGHT, or #> ";
cin >> src;
}

cout << endl;

//
// Now dump the graph to output stream:
//
outputGraph(g);

//
// done:
//
return 0;
}

Answer 1

// graph.h

#pragma once

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class graph
{
private :
   bool vertex[26];
   int matrix[26][26];

public:
   graph();
   // add the vertex v to the graph
   void addvertex(char v);
   // add the edge (from, to, weight) to the graph, but only if
   // the vertices from and to have been added to the graph
   void addedge(char from, char to, int weight);
   // return the weight on the edge (from, to, ?); return -1 if no edge exists
   int getweight(char from, char to);
   // returns the vertices in the graph, in order A .. Z
   vector<char> vertices();
   // returns the neighbors of a vertex v, i.e. all vertices you can reach from
   // v by traversing one edge.
   vector<char> neighbors(char v);
};

// constructor to initialize the matrix entries with -1 and vertex entries with false
graph::graph()
{
   // loop over the rows of matrix
   for(int i=0;i<26;i++)
   {
       vertex[i] = false; // set the vertices to false
       // loop over the columns of matrix
       for(int j=0;j<26;j++)
           matrix[i][j] = -1; // set the weight of each edge to -1 (initially no edge)
   }
}

// function to add a vertex to the graph
void graph:: addvertex(char v)
{
   int idx = (int)(v-'A'); // get the index of the letter relative to 'A'
   // check if it is valid upper case letter
   if(idx >= 0 && idx < 26)
       vertex[idx] = true; // if valid set the vertex entry to true
}

// function to add an edge from vertex to vertex with weight
void graph:: addedge(char from, char to, int weight)
{
   int fromIdx = (int)(from-'A'); // get the index of from vertex in the vertex array
   int toIdx = (int)(to-'A'); // get the index of to vertex in the vertex array

   // check both from and to vertex are valid uppercase letter and both vertex are added to the graph
   if(fromIdx >=0 && fromIdx < 26 && toIdx >=0 && toIdx < 26 && vertex[fromIdx] && vertex[toIdx])
   {
       matrix[fromIdx][toIdx] = weight; // if all valid then set the weight in matrix
   }
}

// function to return the weight from vertex from to vertex to
int graph::getweight(char from, char to)
{
   int fromIdx = (int)(from-'A'); // get the index of from vertex in the vertex array
   int toIdx = (int)(to-'A'); // get the index of to vertex in the vertex array

   // check both from and to vertex are valid uppercase letter and both vertex are added to the graph
   if(fromIdx >=0 && fromIdx < 26 && toIdx >=0 && toIdx < 26 && vertex[fromIdx] && vertex[toIdx])
   {
       return matrix[fromIdx][toIdx]; // return the weight from matrix
   }

   return -1; // no edge exists
}

// function to return the vertices of the graph
vector<char> graph::vertices()
{
   vector<char> letterVertices; // create a vector of vertices
   // loop over the vertex array
   for(int i=0;i<26;i++)
   {
       if(vertex[i]) // if vertex if added
           letterVertices.push_back((char)(i+'A')); // add the corresponding vertex to the vector
   }

   return letterVertices;
}

// function to return the vertices that are neighbors to vertex v i.e. all vertices you can reach from
// v by traversing one edge.
vector<char> graph:: neighbors(char v)
{
   vector<char> letterNeighbors;

   int idx = (int)(v-'A'); // get the index of v in the vertex array
   // check that vertex v is valid uppercase letter and v is added to the graph
   if(idx >= 0 && idx < 26 && vertex[idx])
   {
       // loop over the columns of matrix
       for(int i=0;i<26;i++)
       {
           // if edge from v exists to vertex at ith index
           if(matrix[idx][i] > -1)
               letterNeighbors.push_back((char)('A'+i)); // add the corresponding letter to the vector
       }
   }

   return letterNeighbors;
}
//end of graph.h

//main.cpp is a read only file

#include <iostream>
#include <vector>
#include <string>

#include "graph.h"

using namespace std;

void outputGraph(graph& g)
{
vector<char> vertices = g.vertices();

cout << "**Vertices: ";

for (char c : vertices)
{
cout << c << " ";
}

cout << endl;

cout << "**Edges: ";

for (char v : vertices)
{
vector<char> neighbors = g.neighbors(v);

for (char n : neighbors)
{
int weight = g.getweight(v, n);
cout << "(" << v << "," << n << "," << weight << ") ";
}
}

cout << endl;
}

int main()
{
graph g;
string input;

//
// Input vertices as single uppercase letters: A B C ...
//
cout << "Enter vertices as single letters, separated by spaces, end with #> ";
cin >> input;

while (input != "#")
{
char vertex = input[0];

g.addvertex(vertex);

cin >> input;
}

cout << endl;

//
// Now input edges:
//
string src, dest, weight;

cout << "Enter edge as LETTER LETTER WEIGHT, or #> ";
cin >> src;

while (src != "#")
{
cin >> dest;
cin >> weight;

//cout << src << ", " << dest << ", " << weight << endl;

g.addedge(src[0], dest[0], stoi(weight));

cout << "Enter edge as LETTER LETTER WEIGHT, or #> ";
cin >> src;
}

cout << endl;

//
// Now dump the graph to output stream:
//
outputGraph(g);

//
// done:
//
return 0;
}

//end of main.cpp

Output: