STL-like graph implementation

Question

I have implemented an STL-like graph class. Could someone review it and tell me things that I could add to it?

File graph.hpp

#include <vector>
#include <list>

using std::vector;
using std::list;

#ifndef GRAPH_IMPL
#define GRAPH_IMPL

namespace graph {
  struct node
  {
    int v,w;
  };

  template<class T, bool digraph>
  class graph;

  template<class T>
  class vertex_impl
  {
    friend class graph<T,true>;
    friend class graph<T,false>;
  private:
    list<node> adj;
    int index;
    T masking;
  public:
    vertex_impl(int index = -1, const T& masking = T()) : index(index), masking(masking){}
    vertex_impl(const vertex_impl& other) : index(other.index), masking(other.masking){}

    typedef typename list<node>::iterator iterator;
    typedef typename list<node>::const_iterator const_iterator;
    typedef typename list<node>::reverse_iterator reverse_iterator;
    typedef typename list<node>::const_reverse_iterator const_reverse_iterator;
    typedef typename list<node>::size_type size_type;

    iterator begin() { return adj.begin(); }
    const_iterator begin() const { return adj.begin(); }

    iterator end() { return adj.end(); }
    const_iterator end() const { return adj.end(); }

    reverse_iterator rbegin() { return adj.rbegin(); }
    const_reverse_iterator rbegin() const { return adj.begin(); }

    reverse_iterator rend() { return adj.rend(); } 
    const_reverse_iterator rend() const { return adj.rend(); }

    size_type degree() const { return adj.size(); }

    int name() const { return index; }
    const T& mask() const { return masking; }
    void set_mask(const T& msk) { masking = msk; }
  };

  template<class T, bool digraph>
  class graph
  {
  private:
    vector<vertex_impl<T> > adj;
    typename vector<vertex_impl<T> >::size_type V,E;
  public:
    typedef vertex_impl<T> vertex;
    typedef typename vector<vertex>::iterator iterator;
    typedef typename vector<vertex>::const_iterator const_iterator;
    typedef typename vector<vertex>::reverse_iterator reverse_iterator;
    typedef typename vector<vertex>::const_reverse_iterator const_reverse_iterator;
    typedef typename vector<vertex>::size_type size_type;

    graph(size_type v) : adj(v), V(v), E(0)
    {
      for(size_type i = 0; i < v; ++i) {
        adj[i].index = i;
      }
    }

    iterator begin() { return adj.begin(); }
    const_iterator begin() const { return adj.begin(); }

    iterator end() { return adj.end(); }
    const_iterator end() const { return adj.end(); }

    reverse_iterator rbegin() { return adj.rbegin(); }
    const_reverse_iterator rbegin() const { return adj.rbegin(); }

    reverse_iterator rend() { return adj.rend(); }
    const_reverse_iterator rend() const { return adj.rend(); }

    void insert(int from, int to, int weight = 1)
    {
      adj[from].adj.push_back((node){to,weight});
      E++;
      if(!digraph)
      adj[to].adj.push_back((node){from,weight});
    }

    void erase(int from, int to)
    {
      for(typename vertex::iterator i = adj[from].begin(); i != adj[from].end();) {
        if(i->v == to) {
          i = adj[from].adj.erase(i);
          E--;
        } else {
          ++i;
        }
      }
      if(!digraph) {
        for(typename vertex::iterator i = adj[to].begin(); i != adj[to].end();) {
          if(i->v == from) {
            i = adj[to].adj.erase(i);
          } else {
            ++i;
          }
        }
      }
    }

    size_type vertices() const { return V; }
    size_type edges() const { return E; }

    vertex& operator[](int i) { return adj[i]; }
    const vertex& operator[](int i) const { return adj[i]; }
  };
}
#endif

File main.cpp

#include <stdio.h>
#include "graph.hpp"

int main()
{
  graph::graph<char*,false> gr(5);
  int m;

  scanf("%d", &m);

  for(int i=0; i<m; ++i) {
    int a,b;
    scanf("%d %d", &a, &b);
    gr.insert(a,b);
  }

  for(graph::graph<char*,false>::size_type i = 0; i < 5; ++i) {
    printf("%d: ", gr[i].name());
    for(graph::graph<char*,false>::vertex::iterator j = gr[i].begin(); j != gr[i].end(); ++j) {
      printf(" %d", j->v);
    }
    printf("\n");
  }

  return 0;
} 

Answer 1

• your node type doesn't seem to be a node, but an edge (or an adjacency relationship, or something). Unless this implementation is based on some literature which describes entries in the adjacency list as nodes, I'd consider renaming it
• I have no idea what mask and masking are supposed to mean. They may be meaningful names in the context where you're using this graph, but it isn't clear that they are in a generic graph. It's just where the user attaches their arbitrary data to each vertex, right? Is it even used?
• the number of vertices is fixed at creation time, and you can only add edges. Is that sensible?
• graph::insert doesn't check whether from and to are valid indices
• what does digraph mean here - directed graph? Because there is another meaning which is totally unrelated. Why not just say "directed"?
• it looks like graph::V is always identical to adj.size() (and is anyway never used), so you can remove it
• vertex_impl is an internal implementation detail, yet you're exposing it. STL containers hide these details (list & tree nodes for example) inside the iterator, and only expose the user data. Is there a useful way of iterating transparently over the graph without exposing this?

Answer 2

The point of the include guards is to prevent multiple inclusion of anything. So always put them at the top of the file:

#include <vector>
#include <list>

#ifndef GRAPH_IMPL
#define GRAPH_IMPL

Because these are not at the top you include vector/list every time. This is just more work that does not need to be done.

Never put using statements in a header file (in global context).

using std::vector;
using std::list;

Anybody that uses your header file now implicitly pulls vector/list into the global namespace. This can have undesirable effects with name resolution. Don't do this in a header file. If you must be lazy then use scope so you are not forcing your requirements onto others. There is always a typedef to make things easier.

Comments (or well named members) would be an idea.

  struct node
  {
    int v,w;
  };

No idea what that will be used for.
If the user of your code library should not be seeing this then it should also be contained inside the private part of a classs so that they don't accidentally use it.

vertex_impl

• Not sure what vertex_impl is for?
• Is it exposed externally?
• What is it implementing (its name contains impl)?
• Why can it have more than two nodes (To me a vertex is an edge that connects two nodes)?
• Why does the constructor not fully initialize the object (index is set externally).
• What is masking for?
• What is index for?

When I build objects that contain containers I abstract the container used:

list<node> adj;

Here I would have gone:

typedef std::list<node>  Container;
Container  adj;

Then I would derive the other iterator types from Container. This means if the code changes there is only one location where the code needs to change.

Having an explicit rbegin() and rend() implies that there is some ordering to the nodes. personally I would leave them out as their does not seem to be any way to logically define the order of traversal of a graph. If the user wants to iterate in the reverse order then can use std::reverse_iterator.

graph

Basically the same comments as vertex_impl