The STL library provides many handy containers, but it doesn't include a graph. In practice, however, we often need one.

A few days ago I actually dreamed of writing a graph, and to answer the call of my heart, I wrote one with some basic features, planning to expand it later as needed.

The graph uses vector as its container, stored in adjacency-list form. Its contents are templated, so you can customize and put some exotic types inside.

This way, each node of the graph can be defined as a Node, which includes a position (hard-coded here as a 2D int coordinate) and a templated data field for storing data.

Then the data structure definition looks roughly like this:

C++
class Position {
 public:
  int posX;
  int posY;
  bool operator==(const Position &t) const {
    return ((posX == t.posX) && (posY == t.posY));
  }
};

template <typename T>
class Node {
 public:
  Node(Position p) { pos = p; }
  Position pos;
  T val;
  bool operator==(const Node &t) const { return (pos == t.pos); }
};

Because templates are used, to avoid trouble everything has to be placed in a single header file.

A graph should have basic CRUD operations (facepalm...), so the main graph class definition looks like this:

C++
template <typename T>
class Graph {
 public:
  Graph();
  virtual ~Graph();
  void clear();

  bool set(Position pos, T val);
  bool set(int posX, int posY, T val);
  bool add(Position pos, T val);
  bool add(int posX, int posY, T val);
  bool contains(Position pos);
  bool contains(int posX, int posY);
  bool remove(Position pos);
  bool remove(int posX, int posY);
  bool get(Position pos, T &val);
  bool get(int posX, int posY, T &val);

 private:
  vector<Node<T> > g;
};

Then the test code is as follows:

C++
#include <iostream>

#include "graph.h"

using namespace graphns;
using namespace std;

int main() {
  Graph<int> g;
  g.set(1, 1, 2);
  g.set(1, 3, 4);

  bool st;
  int val = 9;
  st = g.get(1, 1, val);
  cout << "1,1 : " << (st ? val : -1) << endl;
  cout << "1,1 : " << (g.contains(1, 1) ? "contains " : " not contain") << endl;
  st = g.get(1, 3, val);
  cout << "1,3 : " << (st ? val : -1) << endl;
  g.remove(1, 3);
  st = g.get(1, 3, val);
  cout << "1,3 : " << (st ? val : -1) << endl;
  st = g.get(2, 4, val);
  cout << "2,4 : " << (st ? val : -1) << endl;
  return 0;
}

Compile and run; the output is as follows: 

1,1 : 2
1,1 : contains 
1,3 : 4
1,3 : -1
2,4 : -1

Finally, I tried a graph with a lot of nodes and felt that its efficiency wasn't as high as I expected... I'll improve it later.

Also, my favorite BFS and DFS haven't been added yet due to time constraints, so I'll have to get back to them later.