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.

• anthr: Thanks, there was some motivation for these choices. Concerning auto and the whitespace to improve readability: I agree. I opted not to use auto because I wanted to get things correct by hand. I wanted to keep the graph algorithms separate from the graph class because it feels like these should be distinct and this seems to be a more modular way to implement things. It isn't clear to me if this is the correct choice from a design perspective but I think it is. I read that nested classes should be avoided but I don't think I have enough experience to make a strong case for that :)

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];}