Storing raw pointers is fine if they are not associated with ownership: as you have noted, if you translate simply to smart pointers they can start being deleted when you don't want (not to mention handling cycles in the graph).

I think a much simpler solution would be to have the Vertex unaware of it's neighbors, and store edge connections in the graph itself. The graph would own a list of Vertex and a list of Edge (= pair of Vertex then, not a single one), and memory management will become simple.

Edit: an idea of implementation:

// Not very useful class as it is, you might as well use T directly in Graph
template<class T> class Vertex
{
public:
    Vertex(const T& payload);
    const T get_datum();
    void set_datum(const T& new_datum);
private:
    T datum; // Confuse use of 2 terms: "datum" vs "payload"
};

template<class T> class Graph
{
public:
    typedef boost::shared_ptr<Vertex<T>> VertexPtr;
    VertexPtr createVertex(const T& new_datum);
    void addEdge(const VertexPtr& v1, const VertexPtr& v2);
private:
    typedef std::pair<VertexPtr, VertexPtr> Edge;
    std::vector<VertexPtr> vertices;
    std::vector<Edge> edges;
};

with:

VertexPtr Graph::createVertex(const T& new_datum)
{
    vertices.push_back(VertexPtr(new Vertex<T>(new_datum)));
}

Storing raw pointers is fine if they are not associated with ownership: as you have noted, if you translate simply to smart pointers they can start being deleted when you don't want (not to mention handling cycles in the graph).

I think a much simpler solution would be to have the Vertex unaware of its neighbors, and store edge connections in the graph itself. The graph would own a list of Vertex and a list of Edge (= pair of Vertex then, not a single one), and memory management will become simple.

An idea of implementation:

// Not very useful class as it is, you might as well use T directly in Graph
template<class T> class Vertex
{
public:
    Vertex(const T& payload);
    const T get_datum();
    void set_datum(const T& new_datum);
private:
    T datum; // Confuse use of 2 terms: "datum" vs "payload"
};

template<class T> class Graph
{
public:
    typedef boost::shared_ptr<Vertex<T>> VertexPtr;
    VertexPtr createVertex(const T& new_datum);
    void addEdge(const VertexPtr& v1, const VertexPtr& v2);
private:
    typedef std::pair<VertexPtr, VertexPtr> Edge;
    std::vector<VertexPtr> vertices;
    std::vector<Edge> edges;
};

with:

VertexPtr Graph::createVertex(const T& new_datum)
{
    vertices.push_back(VertexPtr(new Vertex<T>(new_datum)));
}

Storing raw pointers is fine if they are not associated with ownership: as you have noted, if you translate simply to smart pointers they can start being deleted when you don't want (not to mention handling cycles in the graph).

I think a much simpler solution would be to have the Vertex unaware of it's neighbors, and store edge connections in the graph itself. The graph would own a list of Vertex and a list of Edge (= pair of Vertex then, not a single one), and memory management will become simple.

Storing raw pointers is fine if they are not associated with ownership: as you have noted, if you translate simply to smart pointers they can start being deleted when you don't want (not to mention handling cycles in the graph).

I think a much simpler solution would be to have the Vertex unaware of it's neighbors, and store edge connections in the graph itself. The graph would own a list of Vertex and a list of Edge (= pair of Vertex then, not a single one), and memory management will become simple.

Edit: an idea of implementation:

// Not very useful class as it is, you might as well use T directly in Graph
template<class T> class Vertex
{
public:
    Vertex(const T& payload);
    const T get_datum();
    void set_datum(const T& new_datum);
private:
    T datum; // Confuse use of 2 terms: "datum" vs "payload"
};

template<class T> class Graph
{
public:
    typedef boost::shared_ptr<Vertex<T>> VertexPtr;
    VertexPtr createVertex(const T& new_datum);
    void addEdge(const VertexPtr& v1, const VertexPtr& v2);
private:
    typedef std::pair<VertexPtr, VertexPtr> Edge;
    std::vector<VertexPtr> vertices;
    std::vector<Edge> edges;
};

with:

VertexPtr Graph::createVertex(const T& new_datum)
{
    vertices.push_back(VertexPtr(new Vertex<T>(new_datum)));
}