# Graph adjacency list implementation in C++

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;
if (!directed){
}
}
}


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;

if (!directed) {
}
}
}


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.

• 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 :) – anthr Apr 5 '15 at 18:38

Initialize key in the default constructor of Node

node() {}


I would use

node() : key(0) {}


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

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