Comment empêcher le débordement de la pile lors de la sérialisation d'une structure de graphe récursive avec boost :: serialization?

Question

J'essaie de sérialiser une grande structure de graphe (géométrique) avec la bibliothèque de sérialisation boost.

-je conserver mon graphique comme une liste de contiguïté, qui est, ma structure est la suivante:

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

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

Maintenant avec> noeuds 10k mon problème est que quand je commence à sérialisation (sauvegarder) mon graphique, il appellera récursivement la sérialisation de tous ces nœuds avant de revenir, puisque le graphe est connecté. Pour plus de précision, lors de la sérialisation du graphique, il commence par sérialiser le premier nœud du vecteur "nœuds". Ce faisant, il doit sérialiser les "noeuds adjacents" des premiers noeuds, par ex. le deuxième noeud est contenu. Par conséquent, il doit sérialiser le deuxième nœud avant de renvoyer la sérialisation du premier nœud et ainsi de suite.

J'ai trouvé this thread à partir de 2010, où quelqu'un a expliqué exactement le même problème. Cependant, ils ne sont pas arrivés à une solution de travail là-bas.

Toute aide serait grandement appréciée.

Ma structure plus en détail:

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; 
    } 

}; 

Edit: Pour ajouter quelques suggestions faites dans le fil mentionné ci-dessus, citant Dominique Devienne:

1) enregistrer tous les nœuds sans leur topologie info sur un premier passage de le vecteur, en enregistrant ainsi tous les pointeurs "suivis" pour eux, puis écrivez les informations de topologie pour chacun, puisque vous ne "recurse" pas, vous seulement écrire un "ref" à un pointeur déjà sérialisé.

2) ont la possibilité d'écrire une « référence faible » à un pointeur, qui ajoute que le pointeur sur le « suivi » carte avec un drapeau spécial disant qu'il n'a pas encore été « vraiment » écrit, de sorte que l'écriture de la topologie d'un nœud qui n'était pas encore écrit s'apparente à des «renvois de références» à ces nœuds voisins. Soit le nœud sera réellement écrit plus tard , ou il ne le sera jamais, et je suppose que la sérialisation devrait gérer ce avec élégance.

# 1 ne nécessite pas de modifications dans la sérialisation boost, mais met le fardeau sur le code client. D'autant plus que vous devez sauvegarder "extérieurement" les voisins , donc il n'est plus bien encapsulé, et l'écriture d'un sous-ensemble des nœuds de la surface devient plus complexe. Il est nécessaire de chercher à l'avance pour lire l'objet réel lors de la rencontre d'une référence vers l'avant, et de plus, une carte séparée à sait où chercher. Cela peut être incompatible avec boost sérialisation (j'avoue être le plus souvent ignorant à ce sujet).

Est-ce que l'une de ces propositions peut être implémentée maintenant?

Answer 1

Puisque vous avez déjà un vecteur avec des pointeurs vers tous vos nœuds, vous pouvez sérialiser le vecteur adjacent_nodes en utilisant des index au lieu de sérialiser les données de nœud réelles.

Vous devez convertir le pointeur this en index lors de la sérialisation d'un noeud. Ceci est plus simple si vous pouvez stocker l'index de noeud dans le noeud, sinon vous devrez chercher nodes pour trouver le bon pointeur (ce processus peut être accéléré en créant une sorte de conteneur associatif pour mapper le pointeur sur l'index) . Lorsque vous avez besoin de lire dans les données, vous pouvez créer votre vecteur initial nodes rempli de pointeurs vers des nœuds vides/factices (qui seront remplis lorsqu'ils sont sérialisés). Si cela n'est pas possible, vous pouvez charger les index de noeud dans un tableau temporaire, puis revenir en arrière et remplir les pointeurs une fois que tous les noeuds ont été lus. Mais vous n'aurez pas à chercher ou à relire des parties de votre fichier.