Mise en conserve d'un graphe avec des cycles

Question

J'ai une classe de nœud personnalisée en python qui est intégrée dans un graphe (qui est un dictionnaire). Comme ces nœuds prennent du temps à créer, j'aimerais les pickler afin de ne pas avoir à les reconstruire à chaque fois que j'exécute mon code.

Malheureusement, parce que ce graphe a des cycles, cPickle atteint la profondeur maximale de récursion :

RuntimeError: profondeur maximale de récursion dépassée lors de la mise en conserve d'un objet

Voici mon objet de nœud :

class Node:
    def __init__(self, name):
        self.name = name
        self.uid = 0
        self.parents = set()
        self.children = set()

    def __hash__(self):
        return hash(self.name)

    def __eq__(self, that):
        return self.name == that.name

    def __str__(self):
        return "\n".join(["Nom: " + self.name,
                          "\tEnfants:" + ", ".join([c.name for c in self.children]),
                          "\tParents:" + ", ".join([p.name for p in self.parents])
                          ]
                         )

Voici comment je construis mon graphe :

def buildGraph(input):
    graph = {}
    idToNode = {}

    for line in input:
        ## Entrée du texte ligne par ligne ressemble à
        ## nœud.source -> nœud.cible
        source, arr, target = line.split()
        if source in graph:
            nsource = graph[source]
        else:
            nsource = Node(source)
            nsource.uid = len(graph)
            graph[source] = nsource
            idToNode[nsource.uid] = nsource

        if target in graph:
            ntarget = graph[target]
        else:
            ntarget = Node(target)
            ntarget.uid = len(graph)
            graph[target] = ntarget
            idToNode[ntarget.uid] = ntarget

        nsource.children.add(ntarget)
        ntarget.parents.add(nsource)
    return graph

Ensuite, dans mon programme principal, j'ai

    graph = buildGraph(input_file)
    bo = cPickle.dumps(graph)

et la deuxième ligne est celle où je reçois mon erreur de profondeur de récursion.

Y a-t-il des solutions en dehors de celle de modifier la structure de Node ?

Answer 1

Vous devez préparer l'objet pour la mise en conserve : s'il y a un cycle, vous devez casser le cycle et stocker cette information sous une autre forme.

Pickle utilise les méthodes __getstate__ pour préparer l'objet à la mise en conserve (elle est appelée avant) et __setstate__ pour initialiser l'objet.

class SomethingPickled(object):
    ## Compresser et désenchevêtrer les données avant la mise en conserve.
    def __getstate__(self):
        # copier en profondeur l'objet
        state = self.__dict__.copy()
        # casser les cycles
        state['uncycled'] = self.votreMethodePourDecycler(state['cycled'])
        del state['cycle']
        # envoyer à la mise en conserve
        return state

    ## Élargir les données avant de désérialiser.
    def __setstate__(self, state):
        # restaurer les cycles
        state['cycle'] = self.votreMethodePourRecycler(state['uncycled'])
        del state['uncycle']
        self.__dict__.update(state)

Je suis sûr que vous trouverez une idée pour casser et joindre les cycles :)

Answer 2

Je ne pense pas que le fait que votre graphe soit cyclique soit le problème - pickle (et cPickle) devraient gérer les structures de données cycliques très bien. J'ai essayé ce qui suit (avec votre définition de Node) et cela a très bien fonctionné:

>>> n1 = Node('a')
>>> n2 = Node('b')
>>> n1.parents.add(n2)
>>> n2.parents.add(n1)
>>> n2.children.add(n1)
>>> n1.children.add(n1)

>>> import cPickle as pickle
>>> pickle.dumps(n1)

En effet, même avec de grands cycles, je n'ai pas rencontré de problème. Par exemple, cela fonctionne très bien pour moi:

>>> def node_cycle(n):
...     start_node = prev_node = Node('node0')
...     for i in range(n):
...         node = Node('node%d' % (i+1))
...         node.parents.add(prev_node)
...         prev_node.children.add(node)
...         prev_node = node
...     start_node.parents.add(node)
...     node.children.add(start_node)

>>> cycle = node_cycle(100000) # cycle de 100k nœuds
>>> pickle.dumps(cycle)

(Tout cela a été testé sur Python 2.7.1)

Il y a d'autres raisons pour lesquelles pickle peut se retrouver avec une récursion très profonde, selon la forme de votre structure de données. Si c'est le vrai problème, vous pourrez peut-être le résoudre avec quelque chose comme ceci:

>>> import sys
>>> sys.setrecursionlimit(10000)

Answer 3

Ici, cette classe de noeud modifiée ne contient que les noms des objets sous forme de chaînes dans un noeud, et vous donne un ensemble d'objets "Node" complets lorsque vous récupérez soit l'attribut "children" soit l'attribut "parents" d'un noeud.

En interne, il n'y a pas de cycles - donc cela devrait éviter le piège de la boucle infinie. Vous pouvez implémenter des méthodes auxiliaires supplémentaires pour faciliter la navigation comme vous le souhaitez.

class Node(object):
    all_nodes = {}
    def __new__(cls, name):
        self = object.__new__(cls)
        cls.all_nodes[name] = self
        return self

    def __getstate__(self):
        self.all_nodes = self.__class__.all_nodes
        return self.__dict__

    def __setstate__(self, dct):
        self.__class__.all_nodes = dct["all_nodes"]
        del dct["all_nodes"]
        self.__dict__ = dct

    def __init__(self, name):
        #self.all_nodes = self.__class__.all_nodes
        self.name = name
        self.uid = 0
        self._parents = set()
        self._children = set()

    def __hash__(self):
        return hash(self.name)

    def __eq__(self, that):
        return self.name == that.name

    def __repr__(self):
        return "\n" + "\n".join(["Nom: " + self.name,
                          "\tEnfants:" + ", ".join([c.name for c in self.children]),
                          "\tParents:" + ", ".join([p.name for p in self.parents])
                          ]
                         )
    def get_relations(self, which):
        names = getattr(self, which)
        return set(self.__class__.all_nodes[name] for name in names)
    @property
    def children(self):
        return self.get_relations("_children")
    @property
    def parents(self):
        return self.get_relations("_parents")

    def __contains__(self, item):
        return item.name in self._children

    def add(self, child):
        self._children.add(child.name)
        child._parents.add(self.name)
    connect_child = add

#exemple et test :

from cPickle import loads, dumps

n1 = Node("n1")
n2 = Node("n2")
n3 = Node("n3")

n1.add(n2)
n2.add(n3)
n3.add(n1)

print n1, n2, n3

p1 = dumps(n1)
Node.all_nodes.clear()
p2 = loads(p1)

print p2
print p2.children
print p2.children.pop().children

print Node.all_nodes

L'inconvénient est qu'il maintient un dictionnaire de classe nommé "all_nodes" où il y a des références à tous les noeuds réellement créés. (Pickle est assez intelligent pour ne pickler ce dictionnaire qu'une seule fois pour un graphe donné, car il est référencé par tous les objets Node) . Le problème avec la référence de classe globale "all_nodes" est que si vous avez besoin de pickler et unpickler des ensembles de graphes différents (disons que vous créez des graphes g1 avec un ensemble de noeuds, dans un autre exécution, créez un graphe g2 avec un autre ensemble de noeuds, puis si vous unpicklez g1, et ensuite g2, le unpickling de g2 remplacera les références de noeuds pour g1). Si vous avez besoin que cela fonctionne, demandez dans un commentaire et je pourrais trouver quelque chose - la chose la plus simple à laquelle je peux penser est d'avoir une classe "graph" qui contiendra un dictionnaire de tous les noeuds (au lieu de l'avoir dans la classe Node)