In this lab implement a Graph with an adjacency matrix.
Implement the following class:
#ifndef GRAPHAM_H
#define GRAPHAM_H
/* This class represents a weighted directed graph via an adjacency matrix.
* Vertices are given an index, starting from 0 and ascending
* Class W : W represent the weight that can be associated with an edge.
* We will not weight the vertices.
* W is the data type for the weight. Normally an int.
*/
template<class W> class GraphAM { private:
/* Recommended, but not necessary. */ void depthFirstTraversal(void (*visit)(const int node), int *visited, const int cVertex);
/* You fill out private member variables. */ public:
/* Initialize an empty graph. */ GraphAM();
/* Initialize the Graph with a fixed number of vertices. */
GraphAM(const int vertices);
/* Deconstructor shall free up memory */
~GraphAM();
/* Removes a vertex.
* return whether successful or not
* Note: You must shift all vertices accordingly.
*/ bool removeVertex(int idx);
/* Adds amt vertices to the graph. Returns the starting point * of the vertice count.
*/ int addVertices(int amt);
/* Adds an edge with weight W to the graph.
* The return is for you convience and will not be graded. */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
bool addEdge(const int start, const int end, const W &weight);
/*
* Remove edge from graph.
* The return is for you convience and will not be graded.
*/ bool removeEdge(const int start, const int end);
void depthFirstTraversal(void (*visit)(const int node)); void breadthFirstTraversal(void (*visit)(const int node));
/*
* Return adjacent weight from start to end (or -1 if they are * not adjacent.
*/
W adjacent(const int start, const int end);
/* Run Dijkstra’s Shortest Path to find the shortest path from start * to end and returning that smallest weight.
* return -1 if a path does not exist!
*/
W dijkstraShortestPath(const int start, const int end);
/* Print out the Graph */ void print() const;
};
#include "grapham.cpp"
#endif
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
Write some test cases:
Create some test cases, using cxxtestgen, that you believe would cover all aspects of your code.
Memory Management:
Now that are using new, we must ensure that there is a corresponding delete to free the memory. Ensure there are no memory leaks in your code! Please run Valgrind on your tests to ensure no memory leaks!
