Circular data dependency destructor

Question

I am now designing my own graph class with adjacency list. I finished most of steps except for the destructor.

This is my Vertex class:

struct Vertex{
public:
    Vertex(){m_name="";}
    Vertex(string name):m_name(name){}
    ~Vertex(){
        cout << "vertex des" << endl;
        for(int i = 0; i < m_edge.size(); i++){
            delete m_edge[i];
            m_edge[i] = nullptr;
        }
    }
    string m_name;
    vector<Edge*> m_edge;
};

This is my Edge class:

struct Edge{
public:
    Edge() : m_head(nullptr), m_tail(nullptr) {m_name="";}
    Edge(string name) : m_name(name), m_head(nullptr), m_tail(nullptr) {}

    ~Edge(){
        cout << "Edge des" << endl;

        delete m_head;
        m_head = nullptr;
        delete m_tail;
        m_tail = nullptr;
    }

   string m_name;

   Vertex* m_head;
   Vertex* m_tail;
};

However, I noticed when destructor is called, both 2 classes actually call each other's destructor so this gives me an infinite loop. Is this design problematic? If not, is there is any way to fix this destructor issue? Thanks!

Answer 1

However, I noticed when destructor is called, both 2 classes actually call each other's destructor so this gives me an infinite loop. Is this design problematic?

Your current design is problematic indeed. Dynamically allocated should only be deleted by their respective owners. Typically, the owner is whoever created the object and typically, there is exactly one owner. If there are more than one object, then the ownership is shared. Shared ownership requires a mechanism - such as reference counting - to track the current number of owners.

Judging by the destuctors, your vertices appear to be "owned" by multiple edges and the edges appear to be owned by multiple vertices. If that wasn't the case, then your graphs would be quite boring. But you haven't implemented any form of ownership tracking.

I recommend using a simpler design where edges don't own vertices nor do vertices own edges. Both of them should be owned by a parent object perhaps called Graph.

Answer 2

Since the question is tagged C++11, you should first use managed pointers. Among managed pointers, weak_ptr can help you break the circular dependency:

#include <vector>
#include <memory>
#include <string>
#include <iostream>

using namespace std;

struct Edge;

struct Vertex{
public:
    Vertex(){m_name="";}
    Vertex(string name):m_name(name){}
    ~Vertex(){
        cout << "vertex des" << endl;
        for(auto e : m_edge)
        {
            if(e->m_head.lock().get() == this)
            {
                e->m_head = nullptr;
            }
            if(e->m_tail.lock().get() == this)
            {
                e->m_tail = nullptr;
            }
        }
    string m_name;
    vector<shared_ptr<Edge>> m_edge;
};

Here your raw pointers were changed for shared_ptrs: no need to call delete on destruction, but you should tell the edges to forget the vertex (see head and tail declaration below).

struct Edge{
public:
    Edge(){m_name="";}
    Edge(string name):m_name(name){}

    ~Edge(){
        cout << "Edge des" << endl;
        // if you're here, this means no vertices points to the edge any more:
        // no need to inform head or tail the edge is destroyed
    }

    void do_something_to_head()
    {
        auto head = m_head.lock();
        if(head)
        {
            head->do_something();
        }
    }

   string m_name;

   weak_ptr<Vertex> m_head;
   weak_ptr<Vertex> m_tail;
};

The raw pointers in the edges are changed for weak_ptr: they are "non-owning" objects pointing to a shared resource. You can't dereference a weak_ptr directly: you must call the method lock which create a temporary shared_ptr to the pointed resource if its exists (thus preventing circular dependency). Usage:

int main()
{
    shared_ptr<Vertex> v1 = make_shared<Vertex>();
    shared_ptr<Vertex> v2 = make_shared<Vertex>();

    // connection should be encapsulated somewhere

    shared_ptr<Edge> e = make_shared<Edge>();

    v1->m_edge.push_back(e);
    e->m_head = v1;

    v2->m_edge.push_back(e);
    e->m_tail = v2;

    return 0;
}