如何在使用boost :: serialization序列化遞歸圖結構時防止堆棧溢出？

Question

我想用序列化boost序列化庫序列化一個大的（幾何）圖形結構。

我存儲我的圖形作爲鄰接表，就是我的結構如下：

class Node { 
    double x,y; 
    std::vector<Node*> adjacent_nodes; 
    ... 
} 

class Graph { 
    std::vector<Node*> nodes; 
    ... 
} 

與> 10K

現在節點我的問題是，當我開始連載（保存）我的圖，它會在返回之前遞歸調用所有這些節點的序列化，因爲圖形已連接。

更確切地說，當序列化圖形時，它將從序列化「節點」向量中的第一個節點開始。在這樣做時，它需要序列化第一節點的「毗鄰節點」，例如，包含第二個節點。

因此它需要在返回第一個節點的序列化之前序列化第二個節點等等。

我從2010年發現this thread，有人解釋了完全相同的問題。但是，他們並沒有在那裏找到有效的解決方案。

任何幫助將不勝感激。

我的結構的詳細信息：

class Node { 

    double x,y; 
    std::vector<Node*> adjacent_nodes; 

public: 

    inline double get_x() const { return x; } 
    inline double get_y() const { return y; } 
    inline std::vector<Node*> const& get_adjacent_nodes() const { return adjacent_nodes; } 

    Node (double x, double y):x(x),y(y) {} 

    void add_adjacent(Node* other) { 
     adjacent_nodes.push_back(other); 
    } 

private: 

    Node() {} 

    friend class boost::serialization::access; 
    template <class Archive> 
    void serialize(Archive &ar, const unsigned int) { 
    ar & x; 
     ar & y; 
     ar & adjacent_nodes; 
    } 

}; 

class Simple_graph { 

std::vector<Node*> nodes; 

void add_edge(int firstIndex, int secondIndex) { 
    nodes[firstIndex]->add_adjacent(nodes[secondIndex]); 
    nodes[secondIndex]->add_adjacent(nodes[firstIndex]); 
} 

public: 

/* methods to get the distance of points, to read in the nodes, and to generate edges */ 

~Simple_graph() { 
    for (auto node: nodes) { 
     delete node; 
    } 
} 

private: 

    friend class boost::serialization::access; 
    template <class Archive> 
    void serialize(Archive &ar, const unsigned int) { 
    ar & nodes; 
    } 

}; 

編輯：要添加在上面提到的螺紋提出了一些建議，理由是多米尼克Devienne：

1）保存所有的節點沒有他們拓撲信息在第一遍 的向量中，因此記錄下所有的「跟蹤」指針，然後 爲每個寫出拓撲信息，因爲那樣你就不會「遞歸」了，你 只寫一個「ref」到一個已經串行化的指針。

2）必須寫一個「弱引用」爲指針， 這隻會增加指針「跟蹤」的可能性與映射一個特殊的標誌 說是不是「真的」寫的是，這樣寫入尚未寫入的節點的拓撲 類似於對這些相鄰節點的「前向引用」 。要麼這個節點真的會寫在後面 之上，要麼永遠不會，而且我想序列化應該適度地處理那個 。

＃1不需要改變boost序列化，但將責任放在客戶端代碼上。特別是因爲你必須「外部」保存鄰居，所以它不再被封裝，並且編寫表面節點的一個子集 變得更加複雜。

＃2需要在遇到前向參考時提前閱讀實際對象，並且還需要單獨映射到 知道在哪裏尋找它。這可能與序列化不兼容（我承認大多不知道它）。

現在可以執行其中的任何提案嗎？

Answer 1

由於您已經有了一個指向所有節點的向量，所以您可以使用索引序列化adjacent_nodes向量，而不是序列化實際的節點數據。

當序列化節點時，您需要將this指針轉換爲索引。這是最簡單的，如果你可以將節點索引存儲在節點中，否則你必須通過搜索nodes找到正確的指針（這個過程可以通過創建某種關聯容器來將指針映射到索引） 。

當您需要讀取數據時，您可以創建初始的nodes向量，其中填充指向空/虛節點的指針（當它們被序列化時它們將被填充）。

如果這樣做不可行，您可以將節點索引加載到一個臨時數組中，然後返回並在所有節點都讀入後填充指針。但是，您不必搜索或重新讀取任何部件的文件。