Using pointers and references, can't figure out why DFS is recurring infinitely

Question

I'm trying to implement a simple DFS on a directed graph using homemade data structures (HashMap and LinkedList) to learn C++, but for some reason the DFS method is infinitely recurring.

I think it's infinitely recurring because for some reason the nodes stored in the hashmap (the graph) are not actually being marked visited during the DFS. I thought I understood pointers and references but apparently I do not. I would appreciate it if someone could help me see what I'm doing wrong.

Here's the infinitely recurring DFS method:

template <class T>
bool Graph<T>::DFS(const T& v1, const T& v2) {
    if(v1 == v2)
        return true;

    Graph<T>::Node * node = *(map->find(v1));
    node->visited = true;

    for(int i = 0; i < node->adjacent->size(); i++) 
        if(node->adjacent->get(i).visited == false) 
            return DFS(node->adjacent->get(i).data, v2);

    return false;
}

Here's the HashMap class find() method

template <class K, class V>
V* HashMap<K, V>::find(const K& key) const {
    int bucket = (int) hash_fn(key) % arrLength;

    HashMap<K, V>::Node * temp = buckets[bucket];
    while(temp != NULL && temp->key != key)
        temp = temp->next;
    if(temp == NULL)
        return NULL;
    else
        return &(temp->value);
}

Here's the Graph class

template <class T>
class Graph {
    struct Node {
        T data;
        bool visited;
        LinkedList<Node> * adjacent;
        Node() {
            adjacent = nullptr;
            visited = false;
        }
        Node(T data) {
            this->data = data;
            adjacent = new LinkedList<Node>();
            visited = false;
        }
    };
    public:
        Graph();
        ~Graph();
        void addEdge(const T& v1, const T& v2);
        bool DFS(const T& v1, const T& v2);

    private:
        HashMap<T, Graph<T>::Node*> * map;
};

template <class T>
Graph<T>::Graph() {
    map = new HashMap<T, Graph<T>::Node*>();
}

template <class T>
Graph<T>::~Graph() {
    map->~Map<T, Graph<T>::Node*>();
}

template <class T>                                  // directed graph
void Graph<T>::addEdge(const T& v1, const T& v2) {  // add edge from v1 to v2

    if(map->find(v1) == NULL)   
        map->insert(v1, new Graph<T>::Node(v1));
    if(map->find(v2) == NULL)
        map->insert(v2, new Graph<T>::Node(v2));

    (*map->find(v1))->adjacent->append( **map->find(v2) ); // oh god
}

Here's the Main method where I construct and populate the graph, and then call the DFS method.

int main() {

    Graph<int> * graph1 = new Graph<int>(); 
    graph1->addEdge(1, 5);
    graph1->addEdge(5, 9);
    graph1->addEdge(9, 20);

    graph1->DFS(1, 20);

    return 0;
}

Thanks in advance for any help or insight. -Bob

Answer 1

If anything your use of pointers looks almost random and arbitrary. You have pointers where they don't make sense: HashMap<T, Graph<T>::Node*>, and lack of pointers where there should be: LinkedList<Node> * adjacent.

You also use dynamic allocation in places that make no sense, like the afformentioned adjacent member of Node, and your cleanup is either non-existent (Graph::Node has no destructor, when it should have one), or completely broken (Graph<T>::~Graph() will lead to a guaranteed memory leak).

Furthermore, nothing ever cleans up your visited flag, so only one call to DFS will ever work.

Bluntly put, there are a LOT of problem with your code, both design-wise, and implementation-wise.

Your specific DFS issue probably comes from using LinkedList<Node> instead of LinkedList<Node*> for the adjency list, because that likely causes the graph to become a massive DAG with subgraphs copied into the adjency list, but it's hard to tell without knowing how LinkedList<> is implemented.

Edit I feel kinda bad for just bluntly saying "this is bad accross the board", here's how I'd implement your code correctly (using the stl instead of your custom containers):

#include <unordered_map>
#include <vector>

template<typename T>
class Graph {
  struct Node {
    T data;
    bool visited;
    std::vector<Node*> adjacent;

    Node(T const& d) : data(d), visited(false) {}
  };
public:
  inline void addEdge(T const& v1, T const& v2);
  inline bool DFS(T const& v1, T const& v2);

private:
  inline bool DFS_recur(T const& v1, T const& v2);
  std::unordered_map<T, Node> map;
};

template<typename T>
void Graph<T>::addEdge(T const& v1, T const& v2) {
  auto v1_found = map.emplace(v1, v1).first;
  auto v2_found = map.emplace(v2, v2).first;

  v1_found->second.adjacent.emplace_back(&v2_found->second);
}

template<typename T>
bool Graph<T>::DFS(T const& v1, T const& v2) {
  auto result = DFS_recur(v1, v2);

  // Return to the invariant state.
  for(auto & n : map) {
    n.second.visited = false;
  }
  return result;
}

template<typename T>
bool Graph<T>::DFS_recur(T const& v1, T const& v2) {
  if(v1 == v2) return true;

  auto v1_found = map.find(v1);
  // If v1 is not in the map, we'll be in trouble.
  if(v1_found == map.end()) return false;

  v1_found->second.visited = true;

  for(auto const & neighbour : v1_found->second.adjacent) {
    if(!neighbour->visited) {
      return DFS_recur(neighbour->data, v2);
    }
  }

  return false;
}

int main() {

    Graph<int> graph1;
    graph1.addEdge(1, 5);
    graph1.addEdge(5, 9);
    graph1.addEdge(9, 20);

    graph1.DFS(1, 20);

    return 0;
}

Notice how all the memory management is handled through RAII, not a new or delete in sight.