Generic Graph Abstract Data Type Implementation in C++

Question

Today I tried to code up a generic graph abstract data type in C++. Precisely, I implemented the adjacency list data structure for a generic graph type. I think it seems to work with different type according to the test cases I have tried :). Through this post I would like to know what kinds of optimizations can I make to the code to make it more readable, understandable and maintainable and also any kind of performance enhancement pointers are welcomed. The code is as follows for the Graph ADT.

#include<map>
#include<set>
#include<cstdio>
#include<iostream>
#include<iterator>
#include<algorithm>

// this is the structure of a node in our Graph ADT
template<typename T>
struct GraphNode {
   T nodeValue;
   std :: set< GraphNode<T>* > adjacentNodes;
   bool searchPresence(T nodeValue);
};

// this function searches for a node with a specific value if its already present in the adjacency list of "this" node
template<typename T>
bool GraphNode<T> :: searchPresence(T nodeValue) {
   typename std :: set< GraphNode<T>* > :: iterator it;
   for(it = this->adjacentNodes.begin(); it != this->adjacentNodes.end(); ++it) {
      if((*it)->nodeValue == nodeValue)
    return true;
   }

   return false;
}

// this class represents our Graph ADT, which can work irrespective of the data you are working with
template<typename T>
class Graph {
   private:
      int nVertices;
      int nEdges;
      bool isDirected;
      std :: map<T, GraphNode<T>* > adjacencyListMap;

   public:
     Graph();
     Graph(int nVertices, int nEdges, bool isDirected);
         void addEdge(T vertex1, T vertex2);
     void displayGraph();
};

// this is the default constructor for the Graph ADT
template<typename T>
Graph<T> :: Graph() {

   this->nVertices = 0;
   this->nEdges = 0;
   this->isDirected = false;
}

// this is the parameterized constructor for the Graph ADT
template<typename T>
Graph<T> :: Graph(int nVertices, int nEdges, bool isDirected) {

   this->nVertices = nVertices;
   this->nEdges = nEdges;
   this->isDirected = isDirected;
}

// this function is used to add an edge to the Graph ADT
template<typename T>
void Graph<T> :: addEdge(T vertex1, T vertex2) {

   GraphNode<T>* node1 = new GraphNode<T>();
   node1->nodeValue = vertex1;
   GraphNode<T>* node2 = new GraphNode<T>();
   node2->nodeValue = vertex2;

   if(this->adjacencyListMap.find(node1->nodeValue) == this->adjacencyListMap.end()) {
     this->adjacencyListMap.insert(std :: pair< T, GraphNode<T>* >(node1->nodeValue, node1));
   }

   if(!this->adjacencyListMap.find(node1->nodeValue)->second->searchPresence(node2->nodeValue))
     this->adjacencyListMap.find(node1->nodeValue)->second->adjacentNodes.insert(node2);

   if(this->adjacencyListMap.find(node2->nodeValue) == this->adjacencyListMap.end()) {
     this->adjacencyListMap.insert(std :: pair< T, GraphNode<T>* >(node2->nodeValue, node2));
   }

   if(!this->isDirected) {
     if(!this->adjacencyListMap.find(node2->nodeValue)->second->searchPresence(node1->nodeValue))
       this->adjacencyListMap.find(node2->nodeValue)->second->adjacentNodes.insert(node1);
   }
} 

// this function is used to display the graph as an adjacency list
template<typename T>
void Graph<T> :: displayGraph() {

   typename std :: map<T, GraphNode<T>*> :: iterator it;

   for(it = this->adjacencyListMap.begin(); it != this->adjacencyListMap.end(); ++it) {
      std :: cout << (*it).first << " --> ";

      typename std :: set< GraphNode<T>* > :: iterator it1;

      for(it1 = (*it).second->adjacentNodes.begin(); it1 != (*it).second->adjacentNodes.end(); ++it1)
     std :: cout << (*it1)->nodeValue << " -> ";

      std :: cout << std :: endl;
   }
}

int main() {

  bool isDirected;
  int nVertices, nEdges;
  std :: cout << "Please enter the number of vertices you want in the graph : ";
  std :: cin >> nVertices;
  std :: cout << "Please enter the number of edges/connections you have in the graph : ";
  std :: cin >> nEdges;
  std :: cout << "Enter 0 if the graph you want should be undirected and non zero otherwise : ";
  std :: cin >> isDirected;
  std :: cin.ignore();

  Graph<std :: string>* freinds = new Graph<std :: string>(nVertices, nEdges, isDirected);

  for(int i = 0; i < nEdges; ++i) {
     std :: string node1, node2;
     std :: cout << "Edge/Connection #" << i+1 << " - " << std :: endl;
     std :: cout << "node 1 : ";
     std :: cin >> node1;
     std :: cout << "node 2 : ";
     std :: cin >> node2;
     freinds->addEdge(node1,node2);
  }

  std :: cout << "The adjacency list representation of the graph you entered is as follows : " << std :: endl;
  freinds->displayGraph();

  return 0;
}

Answer 1

As mentioned, I'm not sure about the performance aspects. I think if you were to profile it, you could see where the slowdowns were and address them then.

However, I do see some things that I think could make this better. Here are my thoughts.

searchPresence() seems like a convoluted name. How about just find()? Or maybe, since you're not returning the found value, just contains()?

Also, in the same method, rather than manually stepping through all values in the set with an iterator, why not just use std::set::find() to get the element and return true if the result does not equal adjacentNodes.end()? It's less code for you to write and maintain. Something like this:

// this function searches for a node with a specific value if its already 
// present in the adjacency list of "this" node
template<typename T>
bool GraphNode<T> :: contains(T nodeValue) {
    typename std :: set< GraphNode<T>* > :: iterator it;
    it = this->adjacentNodes.find (nodeValue);
    if (it == adjacentNodes.end())
    {
        return false;
    }
    return true;
}

The interface for the Graph template class seems a bit odd to me. It assumes you know up front the number of vertices and edges that you are going to add to the graph. But what if you've been handed some data to arrange into a graph, but haven't done so yet? Maybe you don't know how many edges or vertices you have. Or maybe you're streaming some data in over the network and you want to create the graph on-the-fly as it comes in. So I would define it like this:

// this class represents our Graph ADT, which can work irrespective of the 
// data you are working with
template<typename T>
class Graph {
    private:
        int nVertices;
        int nEdges;
        bool isDirected;
        std :: map<T, GraphNode<T>* > adjacencyListMap;

    public:
        Graph();
        void addEdge(T vertex1, T vertex2);
        void displayGraph();
};

I'd keep the remaining constructor the same. You'll then need to update addEdge() to update the count of vertices and edges:

// this function is used to add an edge to the Graph ADT
template<typename T>
void Graph<T> :: addEdge(T vertex1, T vertex2) {
    this->nEdges += 1;
    ...

Next, it goes on to create 2 new nodes with this:

    GraphNode<T>* node1 = new GraphNode<T>();
    node1->nodeValue = vertex1;
    GraphNode<T>* node2 = new GraphNode<T>();
    node2->nodeValue = vertex2;
    ...

But this is premature. The first if statement is going to insert the above graph node into the graph, but only if it doesn't exist there already. I would hold off on creating it until you know you're actually going to insert it. In fact, the way it's done now is a leak, as if the vertex is already in the graph, the new node never gets deleted! So we'll hold off on creating it until we know we need it below.

I find the rest of the method very difficult to read and reason about. One thing that would help is to change the various multiple dereferences to just be vertex1 and vertex2 where appropriate. But first, I think we need to break down what's happening and break out a few things into separate methods.

The code is attempting to find the node if it already exists and add to it, or create a new one if it doesn't exist. I'd create a method like this:

GraphNode<T>* nodeForVertex(T vertex)
{
    std::map<T, GraphNode<T>*>::iterator it = this->adjacencyListMap.find(vertex);
    GraphNode<T>* result = nil;
    if (it == this->adjacencyListmap.end())
    {
        result = new GraphNode<T>();
        result->nodeValue = vertex;
        // Add the vertex to our map
        this->adjacencyListMap [ vertex ] = result;
        this->nVertices += 1;
    }
    else
    {
        result = it->second;
    }

    return result;
}

Then the entire first if statement in addEdge() becomes:

GraphNode<T>* node1 = this->nodeForVertex(vertex1);

The next if statement can be summed up like this:

if (!node1->contains(node2))
{
    node1->adjacentNodes.insert(node2);
}

But remember that we don't have a node2 yet! So first, we need to do this:

GraphNode<T>* node2 = this->nodeForVertex(vertex2);

Finally, we may also need to put node1 into node2's adjacency list, so...

if ((!this->isDirected) && (!node2->contains(node1)))
{
    node2->adjacentNodes.insert(node1);
}

Putting that all together we get:

// this function is used to add an edge to the Graph ADT
template<typename T>
void Graph<T> :: addEdge(T vertex1, T vertex2) {
    this->nEdges += 1;

    GraphNode<T>* node1 = this->nodeForVertex(vertex1);
    GraphNode<T>* node2 = this->nodeForVertex(vertex2);

    if (!node1->contains(node2))
    {
        node1->adjacentNodes.insert(node2);
    }

    if ((!this->isDirected) && (!node2->contains(node1)))
    {
        node2->adjacentNodes.insert(node1);
    }
}

The displayGraph() method seems pretty straightforward and looks reasonable to me.

Now a tricky question. What happens when these items are destroyed? When you destroy a Graph object, it will destroy the adjacencyListMap. That will call the destructor for each object it contains. The problem is that those objects contain references to each other. So when destroying node X it may attempt to destroy the adjacent node Y. Later node Y will be in the map and attempt to be destroyed again.

There are at least 2 different ways to handle this. You could use some sort of shared pointer instead of just raw pointers in the adjacentNodes set. If you're using C++11 (or is it 14?) there's a std::shared_ptr class that keeps objects reference counted and when the destructor is called, it decrements the reference count, and only deletes it when the ref count is 0. Or, you could write a destructor for GraphNode<T> that removes all the items from the set without deleting them and lets the map destructor delete them. That seems like more work than just using a shared pointer to me, but it's up to you.

Edit: One other thing I notice - you don't need to keep around the number of vertices. The map contains all the vertices, so you can just use this->adjancencyListMap.size() instead of nVertices. Of course, it should probably be a method.