Avoid infinite recursion in destructor

user_6450039 0
Viewed 580

As part of an exercise my university has tasked me with, I have written a small Graph implementation, following this header.

class Node {

private:
    std::string name;
    std::vector<Node*> children;

public:
    Node(const std::string& name="");
    virtual ~Node();

}

When writing code for the destructor ~Node(), I noticed that my implementation fails when the graph contains a cycle. This is my implementation so far, which obviously doesn't work if the graph contains a cycle.

Node::~Node() {
    for (Node* n : children) {
        delete n;
        n = NULL;
    }
    children.clear();
}

I am uncertain as to how I would most elegantly write a destructor that can handle cycles in the graph?

Please note that I was specifically tasked to write a recursive destructor. Thank you for your answers!

c++14 graph recursion destructor c++
3 Answers

Option 1: Choose a representation for the graph where nodes are not owned by other nodes, but rather the graph which would be a distinct object. This way the node destructor doesn't need to do anything. This won't satisfy the requirement of recursion:

struct Graph {
    std::vector<std::unique_ptr<Node>> nodes;
};

Note that if there is no inheritance involved, then you could simply use std::vector<Node>. I assume that there is, due to the usage of virtual desturctor in Node.

Alternatively, you could use another representation for the graph such as adjacency list.

Option 2: Use an algorithm to generate a minimum spanning forest of the graph. Then recursively delete the roots of each spanning tree. You can for example use the Kruskal's algorithm. (Given your representation, it looks like your graph may be connected, in which case there would be only one spaning tree).

user_20793030

One option could be to first create an unordered_set of all the Node*s and then to delete them.

void fill(std::unordered_set<Node*>& to_delete, Node* ptr) {
    // try to insert ptr and return if it was already in the set
    if(not to_delete.emplace(ptr).second) return;

    // swap ptr->children with an empty vector
    std::vector<Node*> tmp;
    std::swap(tmp, ptr->children);

    for(Node* c : tmp)       // loop over the pointers
        fill(to_delete, c);  // fill recursively
}

virtual ~Node() noexcept { // std::terminate if anything should throw
    if(children.empty()) return;          // nothing to do here

    std::unordered_set<Node*> to_delete;  // to collect all the Node*'s
    fill(to_delete, this);                // fill the set recursively
    to_delete.erase(this);                // don't delete "this"

    for(auto c : to_delete)               // delete all - they have no children by now
        delete c;
}

Demo

user_75822470

If your graph is a tree (I assume it since your implementation of destructor is valid only for a tree) and you can store parent of the Node then you can write iterative version which do not require any extra data structure to avoid recursion.

Also learn to use smart pointers.

class Node {

private:
    std::string name;
    std::vector<std::unique_ptr<Node>> children;
    Node* parent;

    void safeCleanClildren();
public:
    Node(std::string name="", Node* parent = nullptr)
        : name{std::move(name)}
    {}

    ~Node() {
       iterativeCleanClildren();
    }

    void addChild(std::string name) {
        children.emplace_back(std::make_unique<Node>(std::move(node), this);
    }
};

void Node::iterativeCleanClildren()
{
    auto p = this;
    while (!p->children.empty()) {
        while (!p->children.empty()) {
            p = p->back().get(); // go as deep as possible
        }
        if (p != this) {
           p = p->parent; // go back to parent
           p->children.pop_back();
        }
    }
}

How this work?

  1. first it finds leaf (right most) in a tree (node which do not have children)
  2. Then goes back to parent node and remove child which was just found p->children.pop_back(); (this destroys unique_ptr of just found leaf).
  3. Then finds again leaf and so on.
  4. This tree clearing continues until root (this) node is reached

This way root node ends with no children at all and since it is iterative implementation overflown is impossible. It doesn't matter how much unbalance this tree is.

user_13874380
Related