4
\$\begingroup\$

I'm working on my data structures knowledge and wanted to create a graph with a small DFS driver which simply prints the nodes as it visits them. Here's my graph class:

#ifndef GRAPH_H_
#define GRAPH_H_

#include <stack>
#include <random>
#include <iterator>
#include <unordered_map>
#include <unordered_set>

template <typename T>
class Graph {
  public:
    Graph(bool directed) : directed{directed}, adj_matrix{} {}
    ~Graph() {}
    void add_edge(const T& start, const T& end) {
      adj_matrix[start][end] = true;
      adj_matrix[start][start] = false;
      adj_matrix[end][end] = false;
      adj_matrix[end][start] = directed ? false : true;
    }

    void DFS(T const *start=nullptr) const {
      if(!adj_matrix.size())
        return;
      if(start==nullptr) {
        DFS_helper(get_random_node());
      } else {
        DFS_helper(*start);
      }
    }

    void DFS_helper(const T& start) const {
      std::unordered_set<T> visited;
      std::stack<T> s;
      s.push(start);
      while(!s.empty()) {
        T top = s.top();
        s.pop();
        // If top is unvisited
        if(visited.find(top) == std::end(visited)) {
          // visit it
          visited.insert(top);
          std::cout << top << ' ';
          for(const auto& adj_node: get_adjacent_nodes(top)) {
             s.push(adj_node);
          }
        }
      }
      std::cout << '\n';
    }

  private:
    std::vector<T> get_adjacent_nodes(const T& v) const {
        std::vector<T> adj;
        for(const auto& pair: adj_matrix.at(v)) {
            T neighbor = pair.first;
            bool is_neighbor = pair.second;
            if(is_neighbor) {
                adj.push_back(neighbor);
            }
        }
        return adj;
    }
    T get_random_node() const {
      auto random_it = std::next(std::begin(adj_matrix), std::rand() % (adj_matrix.size()-1));
      return random_it->first;
    }
    const bool directed;
    std::unordered_map<T, std::unordered_map<T, bool>> adj_matrix;
};

#endif //GRAPH_H_

And here's my driver (inspired from this Wikipedia image):

#include <iostream>
#include "graph.h"

int main() {
  bool directed = false;
  Graph<char> g(directed);
  g.add_edge('A', 'B');
  g.add_edge('B', 'D');
  g.add_edge('A', 'E');
  g.add_edge('E', 'F');
  g.add_edge('A', 'C');
  g.add_edge('C', 'G');
  g.add_edge('B', 'F');

  char a = 'A';
  g.DFS(&a);
}

I'm interested in any tips or recommendations!

\$\endgroup\$
3
\$\begingroup\$

Your code looks reasonable, yet I have one suggestion: decouple algorithms from output:

std::vector<T> DFS(T const *start=nullptr) const {
    if(!adj_matrix.size())
        return std::vector<T>();
    if(start==nullptr) {
        return DFS_helper(get_random_node());
    } else {
        return DFS_helper(*start);
    }
}

std::vector<T> DFS_helper(const T& start) const {
    std::unordered_set<T> visited;
    std::unordered_map<T, T*> parents {{start, nullptr}};
    std::stack<T> s;
    std::vector<T> nodes;
    s.push(start);
    while(!s.empty()) {
        T top = s.top();
        s.pop();
        // If top is unvisited
        if(visited.find(top) == std::end(visited)) {
            // visit it
            visited.insert(top);
            nodes.push_back(top);
            for(const auto& adj_node: get_adjacent_nodes(top)) {
                s.push(adj_node);
                parents[adj_node] = &top;
            }
        }
    }
    return nodes;
}

Suppose what happens if your friend needs to run your DFS on a large graph. Most definitely, he or she will be overwhelmed with all the output. So, let the DFS return silently a list of visited nodes; only after that print the nodes if need be.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.