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.

May be issue itself is not in destructor code, but somewhere else: m_roots is not correct or graph is not really acyclic. That's why @m.s. point is important. — anxieux
m_mom->offsprings - those are your siblings. Ignore the code for a moment. What are you even trying to do?! What are the roots nodes in ` Dag` anyway? The youngest children or the oldest parents? — MSalters
@MSalters m_mom->offsprings are me AND my siblings. roots are all the Nodes that do not have offsprings. So they are the youngest children in a sens. I am merely trying to destroy all Nodes once and once only. — Prolix

anxieux anxieux · Accepted Answer · 2015-06-05T14:37:15

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.)

Error in DAG destructor

3 Answers