How to implement a destructor for an n-ary graph node that won't cause a stack overflow?

Question

I'm working on modernizing an older C++ code base that contains a simple graph structure. It originally looked like the following:

struct node_value_t {
   ...
};

struct dag_node  {
  std::vector<dag_node*> children;
  node_value_t value;
};

I want to turn this into a "modern C++" form that uses std::unique_ptr. The node struct now looks like this:

struct dag_node  {
  std::vector<std::unique_ptr<dag_node>> children;
  node_value_t value;
};

Most of the functionality is working. However, when the graph is very large, I get a stack overflow and the process crashes in the destructor of dag_node.

It seems the compiler generated destructor overflows the stack when there's a long chain of children of children.

What is the correct way to implement the destructor so a stack overflow doesn't occur again?

I've tried to implement the solution found here: std::unique_ptr<> as pointer in a node based structure but I'm finding difficulty making the connection between a linked list and an n-ary graph struct.

Answer 1

A Dag Wikipedia: Directed acyclic graph would naturally have multiple nodes which point to the same thing.

If that is the case, then the unique_ptr contract is broken, and the stack overflow is probably expected.

A graph where a node can be pointed to by more than one other node, is not suitable for std::unique_ptr, but you would probably have to use std::shared_ptr.

In most cases, graphs of this type of thing can be managed on the stack. But for very large graphs, special two-phase destruction would need to be done.

In the 2 phase algorithm, you would lock the whole object, and create some container for the nodes which was flat (e.g. std::vector< std::shared_ptr<dag_node> > add the elements during traversal of the dag, and removing elements of the dag_node's vector.

If there is insufficient space for all nodes in the second vector, then the large vector could be purged of any std::shared_ptr<dag_node> where the use_count was 1.