title: Boost serialization with recursive data structure ends up in stack overflow
body: <p><strong>Problem</strong></p>
  <p>I'm having trouble using Boost Serialization library with a recursive data structure. More precisely, I want to serialize a matrix which is represented by nodes containing a value, and where each node has access to its neighbors (top,bottom,left,right). In order to access a node, each entry point is stored in a <code>vector</code> (that is the first and the last node of each row and and each column) . Here is the <code>Node</code> class :</p>
  <pre><code>class Node
  {
  private:
      int v;
      Node* left; 
      Node* right;
      Node* top;
      Node* bottom;
  
  public:
      Node() : v(rand() % 100), left(NULL), right(NULL), top(NULL), bottom(NULL)
      {
  
      }
  
      //Potential memory leak but that's not the topic
      void setLeft(Node* toSet) { left = toSet; }
      void setRight(Node* toSet) { right = toSet; }
      void setTop(Node* toSet) { top = toSet; }
      void setBottom(Node* toSet) { bottom = toSet; }
  
      Node* gLeft() { return left; }
      Node* gRight() { return right; }
      Node* gTop() { return top; }
      Node* gBottom() { return bottom; }
  
      int gValue() { return v; }
  
      template&lt;class Archive&gt;
      void serialize(Archive&amp; ar, const unsigned int version)
      {
          ar&amp; v;
          ar&amp; left;
          ar&amp; right;
          ar&amp; top;
          ar&amp; bottom;
      }
  };
  </code></pre>
  <p>Here is the <code>Matrix</code> class, with a <code>generateValues()</code> function for this example :</p>
  <pre><code>class Matrix
  {
  private:
      int m, n;
      std::vector&lt;Node*&gt; firstNodesPerRow;
      std::vector&lt;Node*&gt; lastNodesPerRow;
      std::vector&lt;Node*&gt; firstNodesPerCol;
      std::vector&lt;Node*&gt; lastNodesPerCol;
  public:
      Matrix(int m, int n) : 
          m(m), n(n),
          firstNodesPerRow(m, NULL), lastNodesPerRow(m,NULL),
          firstNodesPerCol(n, NULL),lastNodesPerCol(n, NULL)
      {
          
      }
  
      void generateValues()
      {
          for (int i = 0; i &lt; m; i++)
          {
              for (int j = 0; j &lt; n; j++)
              {
                  Node* toWrite = new Node();
                  if (i &gt; 0)
                  {
                      toWrite-&gt;setTop(lastNodesPerCol.at(j));
                      lastNodesPerCol.at(j)-&gt;setBottom(toWrite);
                      lastNodesPerCol.at(j) = toWrite;
                  }
                  else
                  {
                      firstNodesPerCol.at(j) = toWrite;
                      lastNodesPerCol.at(j) = toWrite;
                  }
                  if (j &gt; 0)
                  {
                      toWrite-&gt;setLeft(lastNodesPerRow.at(i));
                      lastNodesPerRow.at(i)-&gt;setRight(toWrite);
                      lastNodesPerRow.at(i) = toWrite;
                  }
                  else
                  {
                      firstNodesPerRow.at(i) = toWrite;
                      lastNodesPerRow.at(i) = toWrite;
                  }
              }
          }
      }
  
      template&lt;class Archive&gt;
      void serialize(Archive&amp; ar, const unsigned int version)
      {
          ar&amp; m;
          ar&amp; n;
          ar&amp; firstNodesPerRow;
          ar&amp; firstNodesPerCol;
          ar&amp; lastNodesPerRow;
          ar&amp; lastNodesPerCol;
      }
  };
  </code></pre>
  <p>So what I want to achieve is serializing and deserializing a <code>Matrix</code>. Here is my <code>main</code> function :</p>
  <pre><code>#include &lt;cstdlib&gt;
  #include &lt;sstream&gt;
  #include &lt;vector&gt;
  #include &lt;boost/archive/text_oarchive.hpp&gt;
  #include &lt;boost/archive/text_iarchive.hpp&gt;
  #include &lt;boost/serialization/vector.hpp&gt;
  
  int main(int argc, char* argv[])
  {
      int m = 10; int n = 10;
      Matrix toSerialize(m,n);
      toSerialize.generateValues();
  
      /*
          1) Serialize
      */
      std::ostringstream oss;
      boost::archive::text_oarchive oa(oss);
      oa &lt;&lt; toSerialize;
  
      std::string serialiazedData = oss.str();
  
      /*
          2) Deserialize
      */
      Matrix result(m,n);
      std::stringstream serializedDataStream(serialiazedData);
      boost::archive::text_iarchive ia(serializedDataStream);
      ia &gt;&gt; result;
  
      return EXIT_SUCCESS;
  }
  </code></pre>
  <p>The problem is the following : given a sufficiently large value <code>m</code> or <code>n</code>, <code>main</code> ends up with a <code>stack-overflow</code> exception. I know that's it's coming from the <code>serialize</code> method of <code>Node</code>, because in order to serialize a node, it needs to serialize the neighbors and so on... I found <a href="https://stackoverflow.com/questions/42117697/how-to-prevent-stack-overflow-when-serializing-a-recursive-graph-structure-with">this topic</a> which seems to be exactly the same question. The answer is interesting as a starting point but I'm having trouble to implement it because it's not sufficiently precise. What I understand is that to solve my problem, I need to :</p>
  <ol>
  <li>serialize the nodes in an iterative way, so that when it comes to the neighboors, the objects are already serialized and there is no <code>stack-overflow</code>;</li>
  <li>serialize the topology, which is represented in my case through the pointers <code>top,bottom,right,left</code> of <code>Node</code></li>
  </ol>
  <p>I'm having trouble to actually implement this solution, because the only way I can imagine to do point 1 implies to remove the serialization of <code>top,bottom,right,left</code> in the <code>serialize</code> method of <code>Node</code>, but then I can't achieve point 2?</p>
  <p>Edit : I made a diagram of a matrix to help reading. Note that there is not necessarily <code>m x n</code> nodes in a <code>m x n</code> matrix.</p>
  <p><a href="https://i.stack.imgur.com/LVLUE.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/LVLUE.png" alt="Matrix example" /></a></p>
  <p>Edit 2 : The solution I had in mind (not working, ends up with a stack-overflow when deserializing).</p>
  <pre><code>//Class Node
  template&lt;class Archive&gt;
  void serialize(Archive&amp; ar, const unsigned int version)
  {
      ar&amp; v;
  }
  
  //Class Matrix
  template&lt;class Archive&gt;
  void serialize(Archive&amp; ar, const unsigned int version)
  {
      ar&amp; m;
      ar&amp; n;
  
      for (int i = 0; i &lt; m; i++)
      {
          Node* current = firstNodesPerRow.at(i);
          while (1)
          {
              if (current == NULL) { break; }
              ar&amp; current;
              current = current-&gt;gRight();
          }
      }
  
      ar&amp; firstNodesPerRow;
      ar&amp; firstNodesPerCol;
      ar&amp; lastNodesPerRow;
      ar&amp; lastNodesPerCol;
  }
  </code></pre>
  <hr />
  <p><strong>Solution</strong></p>
  <p>The explanation of the solution is given in the post marked as the answer. Here is an implementation of this solution :</p>
  <pre><code>// class Node
  template&lt;class Archive&gt;
  void serialize(Archive&amp; ar, const unsigned int version)
  {
      ar&amp; v;
  }
  
  // some buffer struct
  struct Neighbors
  {
      Node* top;
      Node* bottom;
      Node* left;
      Node* right;
  
      template &lt;typename Archive&gt;
      void serialize(Archive&amp; ar, const unsigned int version)
      {
          ar&amp; top;
          ar&amp; bottom;
          ar&amp; left;
          ar&amp; right;
      }
  };
  
  //class Matrix
  template&lt;class Archive&gt;
  void save(Archive&amp; ar, const unsigned int version) const
  {
      std::map&lt;Node*, Neighbors&gt; neighborsPerNode;
  
      for (int i = 0; i &lt; m; i++)
      {
          Node* current = firstNodesPerRow.at(i);
          while (1)
          {
              if (current == NULL) { break; }
              neighborsPerNode[current] = {
                  current-&gt;gTop(),
                  current-&gt;gBottom(),
                  current-&gt;gLeft(),
                  current-&gt;gRight(),
              };
              current = current-&gt;gRight();
          }
      }
  
      ar&amp; neighborsPerNode;
  
      ar&amp; m;
      ar&amp; n;
  
      ar&amp; firstNodesPerRow;
      ar&amp; firstNodesPerCol;
      ar&amp; lastNodesPerRow;
      ar&amp; lastNodesPerCol;
  }
  template&lt;class Archive&gt;
  void load(Archive&amp; ar, const unsigned int version)
  {
      // Warning ALL the nodes are browsed 2 times :
      //  1 - to deserialize neighborsPerNode (below)
      //  2 - in the for loop, to create the links between the nodes
      
      std::map&lt;Node*, Neighbors&gt; neighborsPerNode;
      ar&amp; neighborsPerNode;
  
      ar&amp; m;
      ar&amp; n;
  
      ar&amp; firstNodesPerRow;
      ar&amp; firstNodesPerCol;
      ar&amp; lastNodesPerRow;
      ar&amp; lastNodesPerCol;
  
      for (int i = 0; i &lt; m; i++)
      {
          Node* current = firstNodesPerRow.at(i);
          while (1)
          {
              if (current == NULL) { break; }
              Neighbors myNeighbors = neighborsPerNode.at(current);
              current-&gt;setTop(myNeighbors.top);
              current-&gt;setBottom(myNeighbors.bottom);
              current-&gt;setLeft(myNeighbors.left);
              current-&gt;setRight(myNeighbors.right);
              current = current-&gt;gRight();    
          }
      }
  }
  BOOST_SERIALIZATION_SPLIT_MEMBER()
  </code></pre>