need advice with class design

Right now I'm representing a graph as a Graph object, which has a vector of Vertex pointers, each of which represents a vertex of the graph. Each Vertex object also maintains a vector of pointers to Vertex objects to which it is adjacent.

With this setup I can construct graphs, and all is well. However, given a graph, I want to transform the graph by replacing each Vertex with a more complicated object, for example, by replacing each Vertex with an n-gon with n the valence of that vertex. Since these more complicated objects will possess the same position and adjacency information, I'd love to derive these objects from Vertex. But I can't think of a mechanism for making each Vertex object "become" a derived object, since it seems no matter what I do I'll have to tamper with my Vertex pointer vectors, which I don't want to do.

Derive both Vertex and the more complicated objects from a common base class. Then you can declare a vector of pointers to the base class and let polymorphism do its thing.

There are several ways to do this. I would start off simple then work your way up to exactly what you need. Start off by having a simple object that only contains a vertex list of some sort (a vector would do the trick). Then add member functions to add and remove vertices from the list. Afterward you can worry about more complicated tasks such as loading in shapes from a file or making copies of other objects.

Well that's the thing, here's the situation:

Code:

---

class Graph
{
public:
    //Various methods   
private:
    vector<Vertex *> vertices;
};

class Vertex
{
public:
    unsigned int getValence();
    //Various other methods
private:
    vector<Vertex *> adjvertices;
};

---

Now *after* I have a Graph object, I want every Vertex object in that graph to become a Polygon object, where the Polygon constructor takes the valence of the Vertex as a parameter. This Polygon will contain the same adjacency information as the Vertex from which it came. I'd love to be able to do this without touching Graph::vertices or Vertex::adjvertices, by taking advantage of polymorphism, but I'm not sure how I can do this; I'd need something like a Vertex::becomePolygon() method.

well, assuming the Vertice objects were allocated dynamically:

1) allocate a Polygon object with operator new
2) copy the Vertice info to the Polygon
3) delete the Vertice
4) reassign the pointer value at that position in the vector to the new Polygon