The given main function will test your implementation of directed graphs via adjacency matrices by creating a graph and testing its edges and nodes. Your are provided a simple set of structs to work with as well as the function createVertices(int n) which creates a graph of n vertices with no edges.

Your job is to implement the functions:

containsEdge(Graph const * const g, int src, int dest) which outputs true or false based on whether graph g contains an edge from src to dest.

addEdge(int src, int dest) which creates a directed edge from vertex src to vertex dest. There should at most be one unique edge between any two pairs of nodes (including itself)

numOutgoingEdges(Graph const * const g, int v) which outputs the number of outgoing edges for vertex v in graph g

numIncomingEdges(Graph const * const g, int v) which outputs the number of incoming edges for vertex v in graph g

Note: This graph may contain directed edges to itself. Self-edges count as both an incoming and outgoing edge. If a node contains only one edge which points to itself, then the number of incoming and outgoing edges is 1 in that case.

//main.cpp

#include

#include

#include "adjacency_matrix.h"

using namespace std;

int main() {

// Construct graph

Graph* g = createVertices(3);

addEdge(g, 0, 1);

addEdge(g, 1, 0);

addEdge(g, 2, 1);

// Print the edges

printGraph(g);

cout << "Edge from 0 to 1 exists (expected output is 1): " << containsEdge(g, 0, 1) << endl;

cout << "Edge from 1 to 0 exists (expected output is 1): " << containsEdge(g, 1, 0) << endl;

cout << "Edge from 2 to 0 exists (expected output is 0): " << containsEdge(g, 2, 0) << endl;

}

//adjacency_matrix.h

#include

#include

#ifndef _GRAPH_

#define _GRAPH_

using namespace std;

struct Graph {

bool** adjMatrix;

int n;

};

bool containsEdge(Graph const * const g, int src, int dest);

void addEdge(Graph* g, int src, int dest);

int numOutgoingEdges(Graph const * const g, int v);

int numIncomingEdges(Graph const * const g, int v);

void printGraph(Graph const * const g);

Graph* createVertices(int numV);

#endif

//adjacency_matrix.cpp

#include

#include

#include "adjacency_matrix.h"

using namespace std;

/*

Implement the functions below

*/

bool containsEdge(Graph const * const g, int src, int dest) {

return false;

}

void addEdge(Graph* g, int src, int dest) {

}

int numOutgoingEdges(Graph const * const g, int v) {

return 0;

}

int numIncomingEdges(Graph const * const g, int v) {

return 0;

}

void printGraph(Graph const * const g) {

cout << "Adjacency Matrix: " << endl;

for (int i = 0; i < g->n; i += 1) {

for (int j = 0; j < g->n; j += 1) {

bool neighbor = g->adjMatrix[i][j];

cout << neighbor << " ";

}

cout << " ";

}

}

Graph* createVertices(int numV) {

// No need to modify this function

Graph* g = new Graph();

g->n = numV;

g->adjMatrix = new bool*[numV];

for (int i = 0; i < numV; i += 1) {

g->adjMatrix[i] = new bool[numV];

for (int j = 0; j < numV; j += 1) {

g->adjMatrix[i][j] = 1;

}

}

return g;

}