Graph adjacency list implementation in C++

Question

I have been playing around with an adjacency list implementation of a graph class, on which I'd like to be able to run a build and test several graph algorithms. The code I have below works and I have been able to implement BFS, DFS, Dijkstra and Prim's algorithms, but I'm not very satisfied with it and would very much appreciate criticism.

One of the key problems that I can see is that the neighbours of a node are private and therefore to traverse them inside a function (i.e. Dijkstra) I need to make this function a friend of the node class. I suspect that I should implement smart pointers to solve this but before I do this I'd like to consider other suggestions (maybe custom iterators?).

I also think there is a problem with how the nodes are being initialised, as I would prefer not having to call setKey in the graph::addNode function.

The node class:

class node{
 public:
  node() {}
  node(int k) : key(k){}
  void addNeighbour(int k, int weight = 1){    
    if (this->key == k) return;
    neighbours.push_back(std::make_pair(k,weight));
  }
  inline int getKey() const {return key;}
  inline void setKey(const int k){key = k;}

  void display() const{    
    for (std::list<std::pair<int,int> >::const_iterator it = neighbours.begin(); it != neighbours.end(); ++it){
      std::pair<int,int> entry = *it;
      std::cout << entry.first << " ";
    }
    std::cout << std::endl;
  }

  friend void bfs(graph &g, int src);
  friend graph prim(graph &g);
  friend void dijkstra(graph &lg, int src);
 private:
  std::list<std::pair<int, int> > neighbours;  //first element in pair corresponds to vertex key, second to the edge weight between them
  int key;
};

The graph class:

class graph{
 public:
  graph(const int sz) : size(sz), 
                        nodes(sz, node()),
                        directed(false) {}
  void addNode(int key, const std::vector<std::pair<int,int> > &input);
  void display() const;
  node &operator[](const int i){return nodes[i];}
  inline int getSize() const {return size;}
 private:
  std::vector<node> nodes;
  int size;
  bool directed;
};

void graph::addNode(const int key, const std::vector<std::pair<int,int> > &input){

  nodes[key].setKey(key);
  for (std::vector<std::pair<int,int> >::const_iterator it = input.begin(); it != input.end(); ++it){
    std::pair<int,int> entry = *it;
    nodes[key].addNeighbour(entry.first, entry.second);
    if (!directed){
      nodes[entry.first].addNeighbour(key, entry.second);
    }
  }
}

Answer 1

Overall, it seems good. One problem that I find here though is the lack of vertical spacing at some places. This is very subjective, I agree, but adding a blank line to separate unrelated things can improved readability. I once read somewhere that code should be split into "paragraphs". That's an interesting thought to keep in mind. Giving an example, this is one possible way I would space the method graph::addNode():

void graph::addNode(const int key, const std::vector<std::pair<int,int> > &input) {

    nodes[key].setKey(key);

    for (std::vector<std::pair<int,int> >::const_iterator it = input.begin(); it != input.end(); ++it) {

        std::pair<int,int> entry = *it;
        nodes[key].addNeighbour(entry.first, entry.second);

        if (!directed) {
            nodes[entry.first].addNeighbour(key, entry.second);
        }
    }
}

---

Another minor point, but you don't need to add inline to a method when it is already defined directly inside the class body. In such case, adding the keyword is just unnecessary verbosity.

---

Huge lines like in those for loops:

for (std::list<std::pair<int,int> >::const_iterator it = neighbours.begin(); it != neighbours.end(); ++it)

Can be greatly simplified using auto or range-based for, if you have access to C++11. Failing that, I'd suggest that you typedef your list type to avoid having to replicate std::list<std::pair<int,int> > so many times (remember the DRY principle).

typedef std::list<std::pair<int, int> > ListType;

---

And as for the search algorithms, you didn't provide any implementation for them, but I don't see a reason why they shouldn't be members of graph. Personally, I don't see much purpose for a node to exist on its own without a graph, so I would make node a private inner class of graph and make all of its members public. Node seems like an implementation detail to me. Your interface apparently deals in terms of ints only.

Answer 2

Initialize key in the default constructor of Node

Instead of

node() {}

I would use

node() : key(0) {}

Change node::display() to an operator<< function

Instead of

void display() const{  ... }

I would use:

friend std::ostream& operator<<(std::ostream&, node const& n) { ... }

That would allow you change where the data of a node is written to. You don't have to hard code std::cout as the output stream.

Change graph::display() to an operator<< function

Same rationale as for node::display.

Remove redundant use of inline

When functions are defined inside the body of a class, they are inline automatically. Use of inline in the following lines is redundant. It doesn't buy you anything. It only clutters the code.

inline int getKey() const {return key;}
inline void setKey(const int k){key = k;}

I could remove them and use:

int getKey() const {return key;}
void setKey(const int k){key = k;}

A similar change can be made to graph::getSize()

Removed unnecessary use of const

In the function node::setKey, the argument type is const int. The const in that type has no benefits. I would change it to:

void setKey(int k){key = k;}

Similar changes can be made to the following functions in graph:

graph(const int sz) {...}

and

node &operator[](const int i){return nodes[i];}