Starting from:

$30

Data. Structure - lab 22 Graphs via Adjacency Matrix Solved





Instructions: 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!

How to turn in:

Turn in via GitHub. Ensure the file(s) are in your directory and then:

•    $ git add <files

•    $ git commit

•    $ git push


More products