Error during compilation stating undefined references in C++

Question

Sorry for the code dump

The code is being typed into a command line.

Graph.cpp

#ifndef GRAPH_CPP
#define GRAPH_CPP
#include <map>
#include <set>
#include <queue>
#include "Graph.h"
#include <iostream>

using namespace std;

template <typename T>
Graph<T>::Graph(){

}
//check if an edge exists between v and w
template <typename T>
bool Graph<T>::hasEdge(T v, T w) const
{
if (adjMap.find(v) == adjMap.end())
return false;
if (adjMap.at(v).find(w) != adjMap.at(v).end())
return true;
else
return false;
}

template <typename T>
void Graph<T>::addEdge(T v, T w) {
adjMap[v].insert(w);
adjMap[w].insert(v);
}

template <typename T>
int Graph<T>::BFS(T s, T t, map<T,int>& distance, map<T,T>& go_through) const
{
if (adjMap.find(s) == adjMap.end() || adjMap.find(t) == adjMap.end())
{
cout << "Invalid source vertex or/and destination vertex!" << endl;
return INVALID_VERTEX;
}
//Mark all the vertices with current distance to s: -1
for (auto it = adjMap.begin(); it != adjMap.end(); it++) {
distance[it->first] = NOPATH;
}

//Create queue for bfs
queue<T> bfs;
bfs.push(s);
//mark distance from source s to s:0
distance[s] = 0;
//mark shortest path to given source s going through s
go_through[s] = s;
T current = bfs.front();
while (!bfs.empty() && current != t) {
current = bfs.front();
set<T> adjVertices = adjMap.at(current);
for (auto i = adjVertices.begin(); i != adjVertices.end(); i++) {
if (distance[*i] == NOPATH) {
distance[*i] = distance[current] + 1;
go_through[*i] = current;
bfs.push(*i);
}
}
bfs.pop();
}
return distance[t];

}

#endif

Graph.h

#ifndef GRAPH_H
#define GRAPH_H

#include <map>
#include <set>
 
using namespace std;
 
const int NOPATH = -1;
const int INVALID_VERTEX = -2;

template <class T>
class Graph
{
   public:
    // default constructor
    Graph();
    
    // to check if an edge exists between v and w
    bool hasEdge(T v, T w) const;  
    
    // to add an edge beween v and w to the graph
    void addEdge(T v, T w);

    // Apply BFS traversal to find the shortest path from the given source s to destination t
    // return the distnace from s to t
    // if s or t does not exist, return INVALID_VERTEX (=-2) 
    // if there is no path from s to t, return NOPATH (=-1)
    // store the shortest path distance from the given source s  to vertex w in distance map<w, distance>
    // store which next vertex to go through on the shortest path to the given source s in go_through map<w, v>. 
    // Here a pair <w, v> in go_through map represents on the shortest path from w to the given source s, it needs to take the path: w-->v...-->s  
    int BFS(T s, T t, map<T, int>& distance, map<T, T>& go_through) const;
   
   private:    
    //represent the mapping from a Vertex, say u (key) to a set of vertices (value) which directly connect to u 
    map<T, set<T> > adjMap;        
};

#endif   /* GRAPH_H */

PA3Part2.cpp

#include <vector>
#include <iostream>
#include <string>
#include <fstream>
#include <stack>
#include <algorithm>     // for transform() function
#include "Graph.h"

using namespace std;

// declare global variable (constant only)
const int ARGUMENTS = 2;   // define the required command line arguments

// define a function to decide the collection of edges for a graph
// using "Word Buckets Approach"
Graph<string> WordBuckets_addEdges(const vector<string>& words);

int main(int argc, char* argv[])
{
    // Check whether the number of command line arguments match the required one 
    if (argc != ARGUMENTS)
    {
        cout << "Warning: need exactly " << ARGUMENTS-1 << " command line argument." << endl;
        cout << "Usage: " << argv[0] << " inputfile_name" << endl;
        return 1;
    }

    ifstream in_file;
    in_file.open(argv[1]);
    // Check whether the input file can be open successfully or not
    if (!in_file.good())
    {
        cout << "Warning: cannot open file named " << argv[1] << "!" << endl;
        return 2;
    }
    
    // Read data from the input file, assume "good data" from the input file
    // each line of the input file constains one word from English dictionary
    string word;
    vector<string> words;

    while (in_file >> word)
    {
        // convert word to all lower-case letters
        // if assume that each word from the input file is in lower-case letters, this step can be ignored
        transform(word.begin(), word.end(), word.begin(), ::tolower);
        words.push_back(word);
    }
    // close the input file
    in_file.close();

    // build the graph based on the collection of words
    // each word in the collection represents a Vertex in the graph
    // there is an edge from one word to another if these two words are only different by a single letter
    Graph<string> wordsG = WordBuckets_addEdges(words);

    string word1, word2;

    while (true)
    {
        cout << endl << endl;
        cout << "Welcome to CS216 Word Ladder!" << endl;
        cout << "Please give me two English words, and I will convert the first into the second by modifying one letter at a time." << endl;
        cout << "For the Demo purpose, let us try four-letter words only." << endl;
        cout << "Please type the FIRST four-letter word (or type Enter to quit): " << endl;
        getline(cin, word1);
        
        if (word1 == "")
            break;
        
        cout << "Please type the SECOND four-letter word (or type Enter to quit): " << endl;
        getline(cin, word2);
        
        if (word2 == "")
            break;

        // convert both word1 and word2 to all lower-case letters
        transform(word1.begin(), word1.end(), word1.begin(), ::tolower);
        transform(word2.begin(), word2.end(), word2.begin(), ::tolower);

        map<string,int> distance;
            map<string, string> go_through;
        int dis = wordsG.BFS(word1, word2, distance, go_through);
        // Display the ladder distance from word1 to word2
        // Display the shortest path on the word ladder from word1 to word2
        // the ladder distance is defined as the number of edges on the shortest path from one vertex to another
        // the ladder distance of the same vertex to itself is 0 
        // if word1 and word2 are the same word, your program should display "Two words should be different." 
        // there is no path from word1 to word2 if its ladder distance is -1
        // there is no path from word1 to word2 if its ladder distance is -2, which means either word1 or/and word2 is invalid
        if ( dis == NOPATH || dis == INVALID_VERTEX)
            cout << "There is no path from [" << word1 << "] to [" << word2 << "]" << endl;
        else if ( dis == 0)
        {
            cout << "Two words should be different." << endl;
        }
        else
        {
            cout << "The ladder distance from [" << word1 << "] to [" << word2 << "] is " << dis << "-step away." << endl;
            cout << "A ladder from [" << word1 << "] to [" << word2 << "]:" << endl;
        string nextVertex = word2;
            cout << word2;
            while (go_through[nextVertex] != word1)
            {
                cout << " ---> " << go_through[nextVertex];
                nextVertex = go_through[nextVertex];
            }
            cout << " ---> " << word1 << endl;
        }
    }

    cout << "Thank you for using this program, bye..." << endl;
    return 0;
}

/* define a function to decide the collection of edges for a graph
 * using "Word Buckets Approach"
 * Purpose: build a graph based on the collection of vertices
 *          each word stored in the vector, represents a Vertex in the graph
 *          there is an edge from one word to another 
 *          if these two words are only different by a single letter
 *@param words vector<string>: representing the collection of vertices, each string stored in the vector forms a vertex
 *@return Graph<string>: representing the graph built by
 *                       (1) the collection of vertices from words;
 *                       (2) the collection of edges are decided by if any two words are only different by a single letter
 *                         e.g. there is an edge between "cool" and "pool", but there is no edge between "cool" and "poll"
 *
 */
Graph<string> WordBuckets_addEdges(const vector<string>& words)
{    
    // build the graph
    // there is an edge from one word to another if the two words are only different by a single letter.
    // use "Word Bucket" solution described in Lab11 to efficiently decide whether an edge between two vertices
    Graph<string> wordsG;
    
    // provide your code here 
    // implement "Word Buckets Approach" to decide if you need to call addEdge() member function between two vertices
    map<string, vector<string> > bucket;
    for (int i = 0; i < words.size(); i++) {
        for (int j = 0; j < words[i].length(); j++) {
            string key = words[i];
            key[j] = '?';
            bucket[key].push_back(words[i]);
        }
    }

    for (auto k = bucket.begin(); k != bucket.end(); k++) {
        for (int s = 0; k->second.size(); s++) {
            for (int m = 0; m<k->second.size(); m++) {
                if (k->second[s] != k->second[m]) {
                    wordsG.addEdge(k->second[s],k->second[m]);
                }
            }
        }
    }
    return wordsG;
}

So after I completed the code and fixed all the errors, I tried compiling PA3Part2.cpp and Graph.cpp together into an executable program, which gave me this error below.

Error when attempting to compile:

/usr/bin/ld: /tmp/ccHsDrH9.o: in function main': PA3Part2.cpp:(.text+0x4ef): undefined reference to Graph<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >::BFS(std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::map<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, int, std::less<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits, std::allocator > const, int> > >&, std::map<std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::less<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >, std::allocator<std::pair<std::__cxx11::basic_string<char, std::char_traits, std::allocator > const, std::__cxx11::basic_string<char, std::char_traits, std::allocator > > > >&) const' /usr/bin/ld: /tmp/ccHsDrH9.o: in function WordBuckets_addEdges(std::vector<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::allocator<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > > const&)': PA3Part2.cpp:(.text+0x9f0): undefined reference to Graph<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >::Graph()' /usr/bin/ld: PA3Part2.cpp:(.text+0xcca): undefined reference to `Graph<std::__cxx11::basic_string<char, std::char_traits, std::allocator > >::addEdge(std::__cxx11::basic_string<char, std::char_traits, std::allocator >, std::__cxx11::basic_string<char, std::char_traits, std::allocator >)' collect2: error: ld returned 1 exit status

I'm stuck on what to do here, please help and thank you.

I recall having this problem before and not having as much trouble as I am with this.