Decapado de un gráfico con ciclos

Question

Tengo una clase de nodo personalizada en python que está integrada en un gráfico (que es un diccionario). Dado que estos tardan un tiempo en crearse, me gustaría separarlos para que no tenga que reconstruirlos cada vez que ejecuto mi código.

Por desgracia, porque este gráfico tiene ciclos, cPickle golpea el máximo nivel de recursividad:

RuntimeError: maximum recursion depth exceeded while pickling an object

Esta es mi nodo de objeto:

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(["Name: " + self.name, 
          "\tChildren:" + ", ".join([c.name for c in self.children]), 
          "\tParents:" + ", ".join([p.name for p in self.parents]) 
          ] 
         ) 

Éste es cómo construir mi gráfico:

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

    for line in input: 
     ## Input from text line by line looks like 
     ## source.node -> target.node 
     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 

Entonces en mi principal, tengo

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

y la segunda línea es donde obtengo mi error de profundidad de recursión.

¿Hay alguna solución fuera de cambiar la estructura de Node?

Answer 1

Debe preparar el objeto para el encurtido: si tiene un ciclo, necesita romper los ciclos y almacenar esta información de alguna otra forma.

salmuera métodos de uso __getstate__ para preparar objeto a pickle (que llamar antes) y __setstate__ para inicializar el objeto.

class SomethingPickled(object): 
    ## Compress and uncycle data before pickle. 
    def __getstate__(self): 
     # deep copy object 
     state = self.__dict__.copy() 
     # break cycles 
     state['uncycled'] = self.yourUncycleMethod(state['cycled']) 
     del state['cycle'] 
     # send to pickle 
     return state 

    ## Expand data before unpickle. 
    def __setstate__(self, state): 
     # restore cycles 
     state['cycle'] = self.yourCycleMethod(state['uncycled']) 
     del state['uncycle'] 
     self.__dict__.update(state) 

Estoy seguro de que encontrará idea de cómo romperse y unirse a los ciclos :)

Answer 2

Aquí, esta clase de nodo modificado mantiene sólo los nombres de los objetos como cadenas en un nodo, y se da una establecer con objetos "Nodo" completos cuando recuperas el atributo "niños" o "padres" de un nodo.

Internamente no hay ciclos, por lo que debe evitar la trampa de bucle infinito. Puede implementar métodos auxiliares adicionales para facilitar la navegación como lo desee.

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(["Name: " + self.name, 
          "\tChildren:" + ", ".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 



#example and testing: 

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 

El inconveniente es que mantiene un diccionario clase llamada "all_nodes" donde hay referencias a todos los nodos creados en realidad. (Pickle es lo suficientemente inteligente como para extraer solo este diccionario una vez para un gráfico dado, ya que todos los objetos de nodo hacen referencia a él). El problema con la referencia de toda la clase "all_nodes" es si necesita desengrasar y eliminar diferentes conjuntos de gráficos 9let decir que crea gráficos g1 con un conjunto de nodos, en otra ejecución, crea un gráfico g2 con otro conjunto de nodos, y luego si desglosa g1, y luego g2, la desubicación de g2 anulará las referencias de nodo para g1). Si necesita que esto funcione, pregunte en un comentario y podría encontrar algo. Lo más fácil que puedo pensar es tener una clase de "gráfico" que contenga un diccionario para todos los nodos (en lugar de tenerlo en la clase Nodo)

Answer 3

No creo que el hecho de que su gráfico sea cíclico sea el problema: pickle (y cPickle) deberían manejar estructuras de datos cíclicas muy bien. He intentado lo siguiente (con su definición de nodo) y funcionó muy bien:

>>> 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) 

De hecho, incluso con grandes ciclos que no corrieron en un problema. P.ej., Esto funciona muy bien para mí:

>>> 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 of 100k nodes 
>>> pickle.dumps(cycle) 

(Todo esto fue probado en Python 2.7.1)

Hay otras razones por las que la salmuera podría terminar con la recursividad muy profundo, aunque, dependiendo de la forma de su estructura de datos. Si este es el problema real, entonces es posible que pueda solucionarlo con algo como esto:

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