C++ design pattern suggestion

Question

I want to do following, I am writing Graph library. I want my class should be template.

template < typename T>
class Graph
{
}

This Graph class works on another class Vertex

How should I design this Vertex class so that any of my team members can use and I do not have to change my implementation in class Graph

Basically I want this Vertex class to provide couple of member function like getWeight, getvisited,setvisited

So as long as client have these function in there class Graph class can be used as it is

Answer 1

Typically a graph class doesn't do much because all the data is in the vertices or edges (depending which is represented by objects — it sounds like you want vertex objects).

So, you might have

template< typename T >
struct Vertex {
    bool visited;
    T data;

    vector< Vertex * > edges;

    size_t getWeight() const { return edges.size(); }

    bool getvisited() const { return visited; }
    void setvisited( bool v ) { visited = v; }
};

You might want the graph glass to own all the vertices, and prevent problems with disconnection or cycles when trying to destroy it.

template< typename T >
struct Graph {
    typedef Vertex< T > vertex_t;
    deque< vertex_t > vertices;

    vertex_t &get_vertex() {
        return * vertices.insert( vertices.end(), vertex_t() );
    }
};

… and make the constructors of Vertex private, and Graph its friend, to make Graph the only way of obtaining vertices.

Answer 2

The following scenarios below may help when defining the Vertex interface. It will give you the ability to define signatures up front so that Graph is able to compile as well as let users extend Vertex for their needs through inheritance (if that is one of your goals).

// Interface only (i.e. pure virtual). The user must implement this method   
// but the signature is defined up front so Graph able to call it.  
class Vertex {
  public:
  virtual int getWeight() = 0;   
};

// Interface with a default implementation (i.e. virtual).  The default 
// implementation is provided by you but the user can override the 
// implementation if needed.
class Vertex {
  public:
  virtual int getWeight();
};

// Interface has a required implementation (i.e. non-virtual).  The user 
// should not override your implementation.
class Vertex {
  public:
  int getWeight();
};