Undirected Unweighted Graph Implementation - C++

Question

For a class we needed to implement an undirected unweighted graph that:

• Maintains a distance matrix that can be printed
• Supports the computation of the graph's diameter (uses dist matrix)
• Prints the number of connected components and their included vertices

With the above being said, I opted for an adjacency matrix to represent the graph, as I already have to use a distance matrix so why not (though the change from matrix => list should be fairly trivial). I also implemented

• DFS from a given node
• BFS from a given node
• Shortest path. Returns the shortest number of edges between vertices v1 and v2 if such a path exists and -1 otherwise.

To implement the shortest path I used a modified BFS that would increment a variable called distance that indicates how far the node at the front of the queue is away from the node we started at. Got the idea from a similar algorithm which solves the problem "Given a binary tree return a vector of vectors where each nested vector contains the values of each node at a particular level". Found here.

The main goal of this implementation, and this post for that matter, is to determine whether the logic in my methods are reasonable, specifically with BFS/DFS. I'd like to know if I'm missing anything or if there's some simplification I had not considered. Note the implementation does not really have error handling for invalid input, it is just to practice and experiment with!

Graph.h

Note the reason I'm using two dimensional bool/int arrays is because I didn't feel the overhead from std::vector was necessary, though in production it would be a good choice

class Graph {
private:
  int numVertices;
  bool **adjacencyMatrix;
  int **distanceMatrix;
  bool distanceMatrixComputed;

  void initAdjacencyMatrix();
  void initDistanceMatrix();

  bool computeDistanceMatrix();
  std::unordered_map<int, int> bfsWithDistance(int);
  void dfsHelper(int, std::vector<int>&, std::unordered_set<int>&);

public:
  Graph(int);

  void addEdge(int, int);
  int shortestPath(int, int);
  int getDiameter();
  std::vector<int> bfs(int);
  std::vector<int> dfs(int);
  void printAdjacencyMatrix();
  void printDistanceMatrix();
  void printComponents();

  ~Graph();
};

Graph.cpp

In my actual implementation I defined MIN and MAX to avoid pulling in <algorithm> but they didn't format here properly so I removed them from this post

#include "Graph.h"

Graph::Graph(int inNumVertices): numVertices(MAX(inNumVertices, 0)), distanceMatrixComputed(false) {
  this->initAdjacencyMatrix();
  this->initDistanceMatrix();
}

/**
 * Allocate memory for adjacency matrix
 */
void Graph::initAdjacencyMatrix() {
  this->adjacencyMatrix = new bool*[this->numVertices];

  for (int i = 0; i < this->numVertices; ++i) {
    this->adjacencyMatrix[i] = new bool[this->numVertices];
  }
}

/**
 * Allocate memory for distance matrix
 */
void Graph::initDistanceMatrix() {
  this->distanceMatrix = new int*[this->numVertices];

  for (int i = 0; i < this->numVertices; ++i) {
    this->distanceMatrix[i] = new int[this->numVertices];

    for (int j = 0; j < this->numVertices; ++j) {
      this->distanceMatrix[i][j] = -1;
    }
  }
}

/**
 * Since this graph implementation is undirected,
 * our adjacency matrix must remain symmetrical.
 */
void Graph::addEdge(int i, int j) {
  this->adjacencyMatrix[i][j] = true;
  this->adjacencyMatrix[j][i] = true;
  this->distanceMatrixComputed = false;
}

std::vector<int> Graph::dfs(int vertex) {
  std::vector<int> returnVec;
  std::unordered_set<int> visited;
  dfsHelper(vertex, returnVec, visited);

  return returnVec;
}

void Graph::dfsHelper(int vertex, std::vector<int> &vec, std::unordered_set<int> &visited) {
  if (visited.find(vertex) != visited.end()) return;

  vec.push_back(vertex);
  visited.insert(vertex);

  for (int j = 0; j < this->numVertices; ++j) {
    if (this->adjacencyMatrix[vertex][j]) {
      dfsHelper(j, vec, visited);
    }
  }
}

std::vector<int> Graph::bfs(int vertex) {
  std::vector<int> returnVec;
  std::unordered_set<int> visited;
  std::queue<int> q;

  q.push(vertex);

  while (!q.empty()) {
    if (visited.find(q.front()) != visited.end()) {
      q.pop();
      continue;
    }

    returnVec.push_back(q.front());

    // Push all of q.front()'s children
    for (int j = 0; j < this->numVertices; ++j) {
      if (this->adjacencyMatrix[q.front()][j]) {
        q.push(j);
      }
    }

    // Visit q.front()
    visited.insert(q.front());
    q.pop();
  }

  return returnVec;
}

std::unordered_map<int, int> Graph::bfsWithDistance(int vertex) {
  std::unordered_map<int, int> visited;
  std::queue<int> q;

  q.push(vertex);
  int count, distance = 0;

  while (!q.empty()) {
    if (visited.find(q.front()) != visited.end()) {
      q.pop();
      continue;
    }

    count = q.size();

    while (count) {
      // Push all of q.front()'s children
      for (int j = 0; j < this->numVertices; ++j) {
        if (this->adjacencyMatrix[q.front()][j]) {
          q.push(j);
        }
      }

      // Visit q.front()
      // This works nicely because insert will
      // not update an already existing value
      visited.insert({q.front(), distance});
      q.pop();
      count--;
    }

    distance++;
  }

  return visited;
}

bool Graph::computeDistanceMatrix() {
  std::unordered_map<int, int> visited;

  for (int i = 0; i < this->numVertices; ++i) {
    visited = bfsWithDistance(i);
    for (auto it : visited) {
      this->distanceMatrix[i][it.first] = it.second;
    }
  }

  this->distanceMatrixComputed = true;
  return (visited.size() == this->numVertices);
}

int Graph::shortestPath(int v1, int v2) {
  std::unordered_map<int, int> component = bfsWithDistance(v1);
  std::unordered_map<int, int>::const_iterator it = component.find(v2);

  return (it != component.end()) ? it->second : -1;
}

int Graph::getDiameter() {
  bool isConnected = this->computeDistanceMatrix();
  if (!isConnected) return -1;

  int diameter = 0;

  for (int i = 0; i < this->numVertices; ++i) {
    for (int j = 0; j < this->numVertices; ++j) {
      diameter = MAX(diameter, this->distanceMatrix[i][j]);
    }
  }

  return diameter;
}

void Graph::printComponents() {
  if (!this->distanceMatrixComputed) this->computeDistanceMatrix();

  std::vector<std::unordered_map<int, int> > connectedComponents;
  std::unordered_map<int, int> allVisited, component;

  // Gather connected components
  for (int i = 0; i < this->numVertices; ++i) {
    // Component with root i is its own component if we've never seen it before
    if (allVisited.find(i) == allVisited.end()) {
      component = bfsWithDistance(i);
      connectedComponents.push_back(component);
      allVisited.insert(component.begin(), component.end());
    }
  }

  // Print all connected components
  std::cout << "The graph has " << connectedComponents.size() << " connected components" << '\n';

  for (int i = 0; i < connectedComponents.size(); ++i) {
    std::cout << "Connected component " << i + 1 << '\n';

    for (auto it = connectedComponents[i].begin(); it != connectedComponents[i].end(); ++it) {
      std::cout << it->first << " -> ";
    }

    std::cout << '\n';
  }
}

void Graph::printAdjacencyMatrix() {
  std::cout << "Adjacency matrix:" << '\n';
  for (int i = 0; i < this->numVertices; ++i) {
    for (int j = 0; j < this->numVertices; ++j) {
      std::cout << this->adjacencyMatrix[i][j] << " ";
    }

    std::cout << '\n';
  }

  std::cout << '\n';
}

void Graph::printDistanceMatrix() {
  std::cout << "Distance matrix:" << '\n';
  for (int i = 0; i < this->numVertices; ++i) {
    for (int j = 0; j < this->numVertices; ++j) {
      std::cout << this->distanceMatrix[i][j] << " ";
    }

    std::cout << '\n';
  }

  std::cout << '\n';
}

Graph::~Graph() {
  for (int i = 0; i < this->numVertices; ++i) {
    delete[] this->adjacencyMatrix[i];
    delete[] this->distanceMatrix[i];
  }

  delete[] this->adjacencyMatrix;
  delete[] this->distanceMatrix;
}

Answer 1

General Comments

Separation of Concerns

This principle basically says your class should do either business logic or resource management not both. You break this principle as your Graph object is responsible for maintaining a graph but also has to maintaining the memory (resources) associated with the graph (You try to dynamically manage adjacencyMatrix and distanceMatrix).

It would be better if you split these up into two different classes. Note: Them memory management can be done for you by simply using the std::vector<> to handle the resource management.

Rule of Three

Because you have not separated your concerns your resource management logic is flawed and your code broken (in terms of resource management).

{
    Graph   one(15);
    Graph   two(one);   // Compiler generated copy constructor is not
                        // doing what you actually need.
}
// Resulting in a double delete when these go out of scope.

You should look up the rule of three and implement it.

Move Semantics.

This is 2017. Move semantics have been around since 2011. You should definitely be thinking about how your objects are moved. Currently your classes can only be copied.

You should expand the rule of three to the rule of five on your code.

Distance calculator is half of dykstra

Your distance calculator is basically a simplification of dykstra. I did not read it thouroughly to make sure it works in all situations but I would check out "dykstra Algorithm" you will find many references on the web.

Visitor Pattern

Your DFS and BFS look like they probably work. Though I would look up the visitor pattern. It allows a more generic traversal of the graph and allows arbitrary actions to be taken at each node.

Code Review

Don't use this->

new bool*[this->numVertices];

Using this-> hides errors and will result in more bugs. The only reason to actually use this-> is when you have shadowed variables and you want to distinguish between a local and a member.

If you allow shadowed variables you will eventually forget to add this-> and get the wrong one. The compiler will not be able to detect that you got the wrong one and thus you have introduced a bug.

The better solution is to not allow shadowed variables and make the compiler generate an error when you do have shadowed variables. Since you now never have shadowed variables there is never a reason to use this->.

One Initialize per line

Just like normal variable declarations where you should only initialize one variable per line (we are human and we somebody probably has to read your code. You should arrange your initializer list so each member is on a separate line.

Graph::Graph(int inNumVertices): numVertices(MAX(inNumVertices, 0)), distanceMatrixComputed(false) {

This not only increases general readability but quickly allows you to establish order (and verify that it is correct).

Graph::Graph(int inNumVertices)
    : numVertices(MAX(inNumVertices, 0))
    , distanceMatrixComputed(false)
{

Never do manual memory management

/**
 * Allocate memory for adjacency matrix
 */
void Graph::initAdjacencyMatrix() {
  this->adjacencyMatrix = new bool*[this->numVertices];

  for (int i = 0; i < this->numVertices; ++i) {
    this->adjacencyMatrix[i] = new bool[this->numVertices];
  }
}

Use std::vector they have everything you need built in.

Here you forgot that new can fail. In which case you will end up leaking a lot of memory (if it is not the first new that fails).

###Is this test not redundant.
while (!q.empty()) { if (visited.find(q.front()) != visited.end()) { q.pop(); continue; }

If you have entered the loop. Then q is not empty. If q is not empty then front() will not be end().

Std::cout is not the only stream

void Graph::printComponents() {

Printing a graph should not change the state of the graph. So you should probably mark it const.

I would pass a stream as a parameter (it can default to std::cout). But the standard idiom for printing is using the operator<<. So you should also define one of those.

void Graph::printComponents(std::ostream& str = std::cout) const;
friend std::ostream& operator<<(std::ostream& str, Graph const& data)
{
    data.printComponents(str);
    return str;
}