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

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;
}

Answer 2

The short answer to your question, like others answered already, is: yes, calling eachover's destructor is problematic because this will likely result in undefined behavior.

For example, look at this situation:

• A Vertex object v is being deleted,
• which results in deletion of the 1st Edge in member vector m_edge,
• which results in deletion of both m_head and m_tail Vertex,
• assuming one of these is v, then the next loop in v's destructor will try to access data that has been deleted !!!

At best, your program will segfault; at worst... who knows...

Your design is not that bad. Its problem, however, is that you cannot clearly define an ownership (which could help to know who should destroy who).

Indeed, assuming a Vertex can be in relation with several (and at least one) Edge and that an Edge is in relation with exactly two Vertex, then you can consider that an Edge is owned by a pair of Vertex. Not that easy to manage deletion order in that situation...

However, you don't absolutely need an ownership relation to state who should destroy who. As assumed above, an Edge is in relation with exactly two Vertex; if one of them is destroyed, then the Edge should be destroyed too. On the other hand, if an Edge is destroyed, there is no reason to destroy any of the Vertex in relation with it because each can still be in relation with other existing Edge; the single exception to this is when the Vertex has no more relation with any Edge. The code following these rules is the following:

struct Edge;

struct Vertex {
public:
    // ctors unchanged
    ~Vertex();  // implemented below
    void remove_relation(Edge* edge)    // for use by Edge only
    {
        std::vector<Edge*>::iterator it =
            std::find(m_edge.begin(), m_edge.end(), edge);
        if (it != m_edge.end())
             m_edge.erase(it);
        if (m_edge.size() == 0)
            delete this;  // this Vertex can be safely deleted
    }
    string        m_name;
    vector<Edge*> m_edge;
};

struct Edge {
public:
    // ctors unchanged
    ~Edge() {
        // Only have to remove relation with m_head & m_tail
        if (m_head)
            m_head->remove_relation(this);
        if (m_tail)
            m_tail->remove_relation(this);
        std::cout << "deleted Edge " << this << std::endl;
    }
    void delete_from_vertex(Vertex* from)  // for use by Vertex only
    {
        // Prevent from removing relation with the calling Vertex
        if (m_head == from)
            m_head = nullptr;
        else if (m_tail == from)
            m_tail = nullptr;
        else
            assert(false); // Vertex not in relation with this Edge
        delete this;       // finally destroy this Edge
    }
   string  m_name;
   Vertex* m_head;
   Vertex* m_tail;
};

Vertex::~Vertex() {
    for(int i = 0; i < m_edge.size(); i++)
        m_edge[i]->delete_from_vertex(this);    // special destruction
    std::cout << "deleted Vertex " << this << std::endl;
}

Live example

Answer 3

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 4

I think, this is a design issue, because, in graph terms - when you deleting the Edge - you are not supposed to delete its Vertices.

I suppose,

m_head = nullptr;
m_tail = nullptr;

is enough in your example.