boost :: serializationで再帰的なグラフ構造を直列化するときにスタックオーバーフローを防ぐ方法は？

Question

私は、ブーストシリアル化ライブラリを使用して大きな（幾何学的な）グラフ構造をシリアル化しようとしています。

私は次のように私の構造がある、ある、隣接リストとしての私のグラフを保存：私のグラフ>で

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

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

は今、10Kは私の問題は、私は（保存）シリアル化するために起動したときにということ、であるノード、グラフが接続されているため、それらのノードのすべてを再帰的に呼び出すことになります。

より正確には、グラフをシリアライズするときは、「ノード」ベクトルの最初のノードをシリアル化することから始めます。そうする間に、第1のノードの「隣接ノード」を直列化する必要がある。第2のノードが含まれる。

したがって、最初のノードのシリアル化を返す前に2番目のノードをシリアル化する必要があります。

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は、ブーストシリアル化の変更を必要としませんが、クライアントコードにonusを置きます。特に、 ネイバーを「外部的に」保存する必要があるため、カプセル化されていないため、サーフェスノードのサブセット の書き込みがより複雑になります。

＃2は、前方参照に遭遇したときに実際のオブジェクトを先読みする必要があり、さらにそれを求める場所を への別のマップにする必要があります。それはブースト シリアライゼーションと互換性がないかもしれません（私はそれについてほとんど知らないと告白します）。

これらの提案はいずれも実装可能ですか？

Answer 1

すでにすべてのノードへのポインタを持つベクトルがあるため、実際のノードデータをシリアル化する代わりに、インデックスを使用してadjacent_nodesベクトルをシリアル化できます。

ノードをシリアル化するときに、thisポインタをインデックスに変換する必要があります。これは、ノードのインデックスをノードに格納することができる場合は最も簡単です。そうでない場合は、右ポインタを見つけるためにnodesを検索する必要があります（このプロセスは、ポインタをインデックスにマップするための何らかの連想型コンテナを作成することによって高速化できます） 。

データを読み込む必要がある場合は、最初のnodesベクトルを空/ダミーノードへのポインタで埋め込むことができます（これはシリアル化されたときに生成されます）。

これが実現できない場合は、ノードのインデックスを一時的な配列にロードしてから、すべてのノードが読み込まれた後でポインタを読み込んでも、ポインタを読み込むことができます。ただし、あなたのファイルの。