Constructing a graph and performing a depth-first traversal

Question

Please review the use of pointers and design in graph construction code and its depth first traversal. I haven't used smart pointers as I want to understand any issues in following implementation with raw pointers.

Graphs.h

namespace DS {
 struct Vertex;
 typedef std::list<Vertex*> VerticesList;
 typedef std::map<int, VerticesList::const_iterator> DataVertexMap;
 class Graph {
 VerticesList _verticesList;
 DataVertexMap _dataVertexMap;
 //TODO: Need some design to have this function internal only and not exposed to client
 Vertex* addAndGetVertex(int data);
 public:
 Graph();
 ~Graph();
 bool isEmpty();
 //We don't check for duplicate vertex
 void addVertex(int data);
 void addEdge(int srcData, int dstData, int cost);
 int getCostForEdge(int srcData, int dstData);
 void displayGraph();
 void dfsTraversal();
 };
} //End namespace DS

Graphs.cpp

#include "Graphs.h"
#include <stack>
namespace DS {
 struct Vertex;
 typedef struct Edge {
 int cost;
 struct Vertex* srcVertex;
 struct Vertex* dstVertex;
 }Edge;
 typedef std::list<Edge*> EdgeList;
 class Vertex {
 public:
 Vertex() {
 bVisited = false;
 }
 int data;
 EdgeList edgeList;
 bool bVisited;
 };
 Graph::Graph() {
 }
 Graph::~Graph() {
 for (std::list<Vertex*>::const_iterator iter = _verticesList.begin(); iter != _verticesList.end(); ++iter) {
 Vertex * vertex = *iter;
 std::list<Edge*> edgeList = vertex->edgeList;
 for (std::list<Edge*>::const_iterator edgeIter = edgeList.begin(); edgeIter != edgeList.end(); ++edgeIter) {
 delete *edgeIter;
 }
 delete vertex;
 }
 }
 bool Graph::isEmpty() {
 return _verticesList.empty();
 }
 void Graph::addVertex(int data) {
 Vertex* node = new Vertex();
 node->data = data;
 node->edgeList.clear();
 VerticesList::const_iterator iter = _verticesList.insert(_verticesList.end(), node);
 _dataVertexMap.insert(std::make_pair(data, iter));
 }
 Vertex* Graph::addAndGetVertex(int data) {
 Vertex* node = new Vertex();
 node->data = data;
 node->edgeList.clear();
 VerticesList::const_iterator iter = _verticesList.insert(_verticesList.end(), node);
 //TODO: Evaluate if this is right approach to insert in map i.e iterator
 _dataVertexMap.insert(std::make_pair(data, iter));
 return node;
 }
 void Graph::addEdge(int srcData, int dstData, int cost) {
 DataVertexMap::const_iterator srcIter = _dataVertexMap.find(srcData);
 DataVertexMap::const_iterator dstIter = _dataVertexMap.find(dstData);
 Vertex* srcVertex = NULL;
 Vertex* dstVertex = NULL;
 if(srcIter == _dataVertexMap.end())
 srcVertex = addAndGetVertex(srcData);
 else
 srcVertex = *(srcIter->second);
 if(dstIter == _dataVertexMap.end())
 dstVertex = addAndGetVertex(dstData);
 else
 dstVertex = *(dstIter->second);
 Edge* newEdge = new Edge();
 newEdge->cost = cost;
 newEdge->srcVertex = srcVertex;
 newEdge->dstVertex = dstVertex;
 srcVertex->edgeList.push_back(newEdge);
 }
 int Graph::getCostForEdge(int srcData, int dstData) {
 DataVertexMap::const_iterator srcIter = _dataVertexMap.find(srcData);
 DataVertexMap::const_iterator dstIter = _dataVertexMap.find(dstData);
 if(srcIter == _dataVertexMap.end() || dstIter == _dataVertexMap.end())
 return -1;
 EdgeList edgeList = (*(srcIter->second))->edgeList;
 for (EdgeList::const_iterator iter = edgeList.begin(); iter != edgeList.end(); ++iter) {
 Edge* edge = *iter;
 if(edge->dstVertex == *(dstIter->second))
 return edge->cost;
 }
 return -1;
 }
 void Graph::displayGraph() {
 }
 void Graph::dfsTraversal() {
 std::stack<Vertex*> vertexStack;
 vertexStack.push(_verticesList.front());
 while(!vertexStack.empty())
 {
 Vertex *vertex = vertexStack.top();
 vertexStack.pop();
 vertex->bVisited = true;
 printf("%d\n", vertex->data);
 const EdgeList edgeList = vertex->edgeList;
 for (EdgeList::const_iterator iter = edgeList.begin(); iter != edgeList.end(); ++iter) {
 Edge *edge = *iter;
 Vertex *dstVertex = edge->dstVertex;
 if(!dstVertex->bVisited)
 vertexStack.push(dstVertex);
 }
 }
 //TODO: mark visited back to false for each node.
 }
}

Answer 1

I won't go into detail about memory management now, but it seems to be correct. You are deleting the edges and vertexes in the destructors, so you should't have any leaks.

Things you could improve in the code:

• No need to define an empty constructor. Don't provide one if you have no manual initialization to perform.

• You don't have to typedef struct in C++, like you would in C. Just struct Edge { }; is enough.

• Beginning with C++11, you can now directly initialize member variables on declaration. So you could init Vertex::bVisited directly. E.g.: bool bVisited = false;. I also recommend initializing Vertex::data to zero or some other default value.

• The for loops in Graph's destructor are quite verbose and long. You could make them a lot more concise by using range based for loops.

• Methods that don't mutate state of an object should be const. isEmpty() is an example: bool isEmpty() const; This is Const Correctness.

• Several declaration are using the long winded iterator and const_iterator names. You could simplify all of them by using auto and letting the compiler do the type inference for you.

• Don't use NULL in C++. This is very outdated. Start using nullptr.

• Names starting with an _ are arguable. _verticesList and _dataVertexMap are not wrong though, but this practice might still be disapproved by some, as it might lead to eventually slipping such a name into the global namespace. Consider other options such as an underscore at the end, likeThis_ or the also popular m_ prefix, m_likeThis. Or no prefix/suffix at all.

• printf is cool, I like it ;). But this is C++ land, so you should give std::cout the preference. If you do use printf though, #include <cstdio> and call it using the std:: namespace: std::printf("Hello");.

There are probably more aspect and points to note. Hopefully other reviewers will expand on this list.

Answer 2

There is at least one place where you may have problems with raw pointers. It has to do with exception safety and the piece of code I am talking about is the method addVertex (but it also applies to addAndGetVertex):

void Graph::addVertex(int data) {
 Vertex* node = new Vertex();
 node->data = data;
 node->edgeList.clear();
 VerticesList::const_iterator iter = _verticesList.insert(_verticesList.end(), node);
 _dataVertexMap.insert(std::make_pair(data, iter));
}

Here, you are allocating memory for a Vertex, then you try to add it at the end of _verticesList. When inserting an element in an std::list, a new node should be allocated. Unless otherwise specified, std::list uses std::allocator to allocate new memory, which is based on new and delete. In other words, if there is no more free memory to allocate for the new node, new will throw an std::bad_alloc exception and insert will rethrow the exception. In addVertex, if insert throws, then the newly allocated Vertex (node) will not be freed. This is a memory leak, and so your method fails to provide the basic exception safety (also known as no-leak guarantee).

If you use a smart pointer to allocate the memory, then when insert throws, your method won't catch the exception, but the destructors of the automatic variables of the method will be called. Therefore, the destructor of the smart pointer will be called and node will be safely deallocated.

• technophile: Nice point. Thanks. Small correction though, that I _verticesList is a std::list, however your point applies to that as well in case default allocator is used.
• Morwenn: @singhalmanik Right. I am so used to "vector everywhere" that I didn't even check twice. I will fix that, thanks :)