我想用序列化boost序列化庫序列化一個大的(幾何)圖形結構。如何在使用boost :: serialization序列化遞歸圖結構時防止堆棧溢出?
我存儲我的圖形作爲鄰接表,就是我的結構如下:
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需要在遇到前向參考時提前閱讀實際對象,並且還需要單獨映射到 知道在哪裏尋找它。這可能與序列化不兼容(我承認大多不知道它)。
現在可以執行其中的任何提案嗎?
謝謝你的回答。您建議在閱讀時創建虛擬節點,然後再填充。我如何將它融入反序列化過程?是否有可能確保新節點將在預定的虛擬位置創建?或者我可以預測,節點將在哪裏創建? – cero
@cero我對boost序列化的細節並不熟悉,所以我不知道在反序列化之前是否可以用'Node *'填充你的向量,或者如果boost一直這樣做。如果是這樣的話,那麼你必須做一些事情,比如我在最後一段中的建議,在那裏你保留了所有相鄰的節點索引,然後返回並在你讀完所有內容時將它們轉換爲指針。如果相鄰節點總是早於'節點'(所以它們已經被反序列化了),那麼你可以引用在這個過程中創建的指針。 – 1201ProgramAlarm
在做了一些更多的研究後,我認爲這確實是如果我堅持使用基於指針的數據結構的唯一方法。在我的情況下,我用指數向量代替了指針向量,而不是複雜的雙向反序列化。 儘管不完全令人滿意,但我認爲你的答案儘可能的接近我所能得到的。謝謝。我會將你的答案標記爲已接受。 – cero