Error in DAG destructor

Question

I have a Dag class (Directed Acyclic Graph) that contains a vector of raw pointers to objects of the class Node. This vector is called m_roots and consists of all the nodes that do not have offsprings. (But they can have up to two parents) The Node objects form binary trees of sorts. The member attributes of Nodes are:

int m_indiv;
Node * m_dad;
Node * m_mom;
std::vector<Node * > m_offsprings;
int m_generat;

So although the structure is acyclic, I have pointers in both directions. The Dag constructor launches a recurrence that creates the Nodes from a the data contained in a map. Here is the recurrent part:

void Node::recNode(const map<int, pair<int, int> > &mapPed, map<int, Node * > &mapDup, const vector <int> &sampleListe, vector<Node * > &sample)
{

    if (find (sampleListe.begin(), sampleListe.end(), this->m_indiv) != sampleListe.end()) {
        sample.push_back(this);
    }
    pair<int, int> parents;


    if (parents.first!=0) { //0 is a reserved integer for missing data, pointer stay to NULL (nullptr)
        if (mapDup.find(parents.first) == mapDup.end() || !(mapDup[parents.first])) {
            m_dad=new Node(parents.first);
            if (mapDup.find(parents.first) != mapDup.end()) { 
                mapDup[parents.first]=m_dad;
            }
            m_dad->recNode(mapPed, mapDup, sampleListe, sample);
        }
        else {
            m_dad=mapDup[parents.first];
        }
        m_dad->m_offsprings.push_back(this); //add the pointer to this node in the dads list of offspring
    }

    //do the same for the second parent
    if (parents.second!=0) {
        if (mapDup.find(parents.second) == mapDup.end() || !(mapDup[parents.second]) ) {
            m_mom=new Node(parents.second);
            if (mapDup.find(parents.second) != mapDup.end()) {
                mapDup[parents.second]=m_mom;
            }
        m_mom->recNode(mapPed, mapDup, sampleListe, sample);
        }
        else {
            m_mom=mapDup[parents.second];
        }
        m_mom->m_offsprings.push_back(this); //add the pointer to this node in the moms list of offspring
    }

}

My Dag destructor launches the recursive destruction:

Dag::~Dag()
{
    for (int i(0); i<m_roots.size();++i) {
        delete m_roots[i];
    }
}

The Node destructor should be doing the actual destruction:

Node::~Node()        

{
    if(m_dad) {
        Node* dummyD=m_dad;
        for (int i(0); i<m_dad->m_offsprings.size();++i) {
            if (m_dad->m_offsprings[i]) {
                m_dad->m_offsprings[i]->m_dad=nullptr;
            }
        }
        delete dummyD;
    }
    if(m_mom) {
        Node* dummyM=m_mom;
        for (int i(0); i<m_mom->m_offsprings.size();++i) {
            if (m_mom->m_offsprings[i]) {
                m_mom->m_offsprings[i]->m_mom=nullptr;
            }
        }
        delete dummyM;
    }

}

For some reason this is not working: I get a Seg Fault. The corresponding Valgrind error is:

InvalidRead                                     Invalid read of size 8
                                                Call stack:
/usr/include/c++/4.8/bits/stl_vector.h  646     0x411734: Node::~Node()
~/Dag.cpp                               138     0x409E98: Dag::~Dag()
~/main.cpp                              114     0x41062B: main
            Address 0x18 is not stack'd, malloc'd or (recently) free'd

When debugging line per line, it breaks at the line:

for (int i; i<m_dad->m_offsprings.size();++i) {

after the first iteration. (During the first call to ~Dag() and the first call to ~Node()). The i from the for loop where it breaks just changed from 0 to 1. The fact it breaks this early on makes it unlikely that it is a problem of cycles in the Dag... I also have a '__in_charg' function argument which is <optimized out> (despite -O0). I am not sure what it means but it seems that Node* dummyD=m_dad; is not read...

I am looking for the reason why it is not working, the flaw in the logic... I know that it can be done using shared_ptr for the mom and dad and weak_ptr for offsprings.

Note: The nomenclature parent/offspring is somewhat field specific. Here I use it in the "biological" sens: each individual has only one mom and one dad but can have from 0 to n offsprings.

Answer 1

In the Node::~Node() function, seems like this is a one of the m_offsprings. So after the first iteration of the

for (int i(0); i<m_dad->m_offsprings.size();++i) {
    if (m_dad->m_offsprings[i]) {
        m_dad->m_offsprings[i]->m_dad=nullptr;
    }
}

this->m_dad becomes nullptr. After that you are trying to dereference it in m_dad->m_offsprings.size().

To fix this, check that address of the current m_dad's m_offspring is not equal to this. (And same for m_mom.)

Answer 2

Not a direct solution, but I guess even more helpful: If somehow possible, completely get rid of all the mentioned problems by using smart-pointers

Node
{
    int m_indiv;
    Node * m_dad;
    Node * m_mom;
    std::vector<std::shared_ptr<Node> > m_offsprings;
    int m_generat;
}

No, if a node is destructed (--and it is the last one pointing to the offsprings), all offspring destructors automatically get called recursively. So there's no need to write further error-prone code.

Answer 3

m_roots[0] and m_roots[1] share the same dad. When you delete Node m_roots[0], its' dad and mom get deleted, as well as their whole "family". Thus, m_roots[1] becomes an orphan.