C++

Forum

 
I need help trying to understand graphs

georgieboy (12)
So I am currently using the textbook "C++ Data Structures 3rd Edition", and I have taken some code out of the book. I need help understanding why I keep getting the same three errors. Again the .h and .cpp files are right out of the book. I am merely trying to understand how to make the code work so that I can apply it to my project. Here's the code:

GraphType.h
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
 
#ifndef GraphType_H
#define GraphType_H

#include "QueType.h"

template<class VertexType>
// Assumption: VertexType is a type for which the "=", 
// "==", and "<<" operators are defined
class GraphType
{
public:
  GraphType();                  // Default of 50 vertices
  GraphType(int maxV);          // maxV <= 50
  ~GraphType();
//  void MakeEmpty();
//  bool IsEmpty() const;
//  bool IsFull() const;
  void AddVertex(VertexType);
  void AddEdge(VertexType, VertexType, int);
  int WeightIs(VertexType, VertexType);
  void GetToVertices(VertexType, QueType<VertexType>&);
//  void ClearMarks();
//  void MarkVertex(VertexType);
//  bool IsMarked(VertexType);
private:
  int numVertices;
  int maxVertices;
  VertexType* vertices;
  int edges[50][50];
  bool* marks;	// marks[i] is mark for vertices[i].
};

#endif


GraphType.cpp
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
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
#include "GraphType.h"
template<class VertexType>
GraphType<VertexType>::GraphType()
// Post: Arrays of size 50 are dynamically allocated for  
//       marks and vertices.  numVertices is set to 0; 
//       maxVertices is set to 50.
{
  numVertices = 0;
  maxVertices = 50;
  vertices = new VertexType[50];
  marks = new bool[50];
}

template<class VertexType>
GraphType<VertexType>::GraphType(int maxV)
// Post: Arrays of size maxV are dynamically allocated for  
//       marks and vertices.  
//       numVertices is set to 0; maxVertices is set to maxV.
{
  numVertices = 0;
  maxVertices = maxV;
  vertices = new VertexType[maxV];
  marks = new bool[maxV];
}

template<class VertexType>
// Post: arrays for vertices and marks have been deallocated.
GraphType<VertexType>::~GraphType()
{
  delete [] vertices;
  delete [] marks;
}
const int NULL_EDGE = 0;

template<class VertexType>
void GraphType<VertexType>::AddVertex(VertexType vertex)
// Post: vertex has been stored in vertices.
//       Corresponding row and column of edges has been set 
//       to NULL_EDGE.
//       numVertices has been incremented.
{
  vertices[numVertices] = vertex;

  for (int index = 0; index < numVertices; index++)
  {
    edges[numVertices][index] = NULL_EDGE;
    edges[index][numVertices] = NULL_EDGE;
  }
  numVertices++;
}
template<class VertexType>
int IndexIs(VertexType* vertices, VertexType vertex)
// Post: Returns the index of vertex in vertices.
{
  int index = 0;

  while (!(vertex == vertices[index]))
    index++;  
  return index;
}       

template<class VertexType>
void GraphType<VertexType>::AddEdge(VertexType fromVertex,
     VertexType toVertex, int weight)
// Post: Edge (fromVertex, toVertex) is stored in edges.
{
  int row;
  int col;

  row = IndexIs(vertices, fromVertex);
  col = IndexIs(vertices, toVertex)
  edges[row][col] = weight;
}

template<class VertexType>
int GraphType<VertexType>::WeightIs
     (VertexType fromVertex, VertexType toVertex)
// Post: Returns the weight associated with the edge 
//       (fromVertex, toVertex).
{
  int row;
  int col;

  row = IndexIs(vertices, fromVertex);
  col = IndexIs(vertices, toVertex);
  return edges[row][col];
}
template<class VertexType>
void GraphType<VertexType>::GetToVertices(VertexType vertex, 
     QueType<VertexType>& adjVertices)
// Post: 
{
  int fromIndex;
  int toIndex;

  fromIndex = IndexIs(vertices, vertex);
  for (toIndex = 0; toIndex < numVertices; toIndex++)
    if (edges[fromIndex][toIndex] != NULL_EDGE)
      adjVertices.Enqueue(vertices[toIndex]);
}


Driver.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
#include <iostream>
#include "GraphType.h"

using namespace std;

int main()
{
	//I am using this driver to test the functions of GraphType
	GraphType<int> *graph(new GraphType<int>(50));

	graph->AddVertex(10);
	graph->AddVertex(12);

	graph->AddEdge(10,12,9);


	system("pause");
	return 0;
}


Error Logs
1
2
3
4
5
 
Error	4	error LNK1120: 3 unresolved externals	C:\Users\Nawgee\Documents\Visual Studio 2010\Projects\graphprac\Debug\graphprac.exe	graphprac
Error	3	error LNK2019: unresolved external symbol "public: __thiscall GraphType<int>::GraphType<int>(int)" (??0?$GraphType@H@@QAE@H@Z) referenced in function _main	C:\Users\Nawgee\Documents\Visual Studio 2010\Projects\graphprac\graphprac\driver.obj	graphprac
Error	1	error LNK2019: unresolved external symbol "public: void __thiscall GraphType<int>::AddEdge(int,int,int)" (?AddEdge@?$GraphType@H@@QAEXHHH@Z) referenced in function _main	C:\Users\Nawgee\Documents\Visual Studio 2010\Projects\graphprac\graphprac\driver.obj	graphprac
Error	2	error LNK2019: unresolved external symbol "public: void __thiscall GraphType<int>::AddVertex(int)" (?AddVertex@?$GraphType@H@@QAEXH@Z) referenced in function _main	C:\Users\Nawgee\Documents\Visual Studio 2010\Projects\graphprac\graphprac\driver.obj	graphprac
maeriden (872)
Could this be related to the compiler needing to see the implementation for template classes in every file it compiles? Maybe try including "GraphType.cpp" instead of the header in driver.cpp
georgieboy (12)
OMG Thanks Maeriden! That worked!

Thanks!
maeriden (872)
No problemo, but I don't think this is much more than a workaround. I don't have any formal education on templates so you might want to search around the correct way to do this
Topic archived. No new replies allowed.