2
\$\begingroup\$

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);
    }
  }
}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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 :) \$\endgroup\$ – anthr Apr 5 '15 at 18:38
2
\$\begingroup\$

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];}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.