Decapaggio di un grafico con cicli

Question

Ho una classe nodo personalizzata in python incorporata in un grafico (che è un dizionario). Dal momento che questi richiedono un po 'di tempo per creare, mi piacerebbe metterli sottosopra in modo da non doverli ricostruire ogni volta che eseguo il mio codice.

Purtroppo, perché questo grafico ha cicli, cPickle colpisce la massima profondità di ricorsione:

RuntimeError: maximum recursion depth exceeded while pickling an object

Questo è il mio oggetto nodo:

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

Questo è come io costruisco il mio grafico:

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 

Quindi nel mio main, ho

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

e la seconda riga è dove ottengo il mio errore di profondità di ricorsione.

Esistono soluzioni che non modificano la struttura del nodo?

Answer 1

È necessario preparare l'oggetto per il sottaceto: se si dispone di un ciclo è necessario interrompere i cicli e memorizzare queste informazioni in qualche altra forma.

Pickle utilizzano metodi __getstate__ per preparare oggetto salamoia (chiamata l'prima) e __setstate__ per inizializzare oggetto.

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) 

Sono sicuro che troverete idea di come rompere e unisciti cicli :)

Answer 2

Ecco, questa classe nodo modificato contiene solo i nomi degli oggetti come stringhe in un nodo, e si dà un impostato con oggetti "Nodo" completi quando si recupera l'attributo "figli" o "genitori" di un nodo.

Internamente non ci sono cicli, quindi dovrebbe evitare la trappola infinita. È possibile implementare ulteriori metodi ausiliari per facilitare la navigazione come si desidera.

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 

Lo svantaggio è che si mantiene un dizionario classe denominata "all_nodes" in cui ci sono i riferimenti a tutti i nodi in realtà create. (Pickle è abbastanza intelligente da mettere sottosopra questo dizionario solo una volta per un dato grafo, dato che è referenziato da tutti gli oggetti Nodo). Il problema con il riferimento di classe "all_nodes" è se è necessario mettere sottosopra e separare diversi gruppi di grafici 9let dice che si creano grafici g1 con un insieme di nodi, in un'altra esecuzione, creare un grafico g2 con un altro insieme di nodi, e quindi se si deseleziona g1, e successivamente g2, l'annullamento di g2 sovrascriverà i riferimenti del nodo per g1). Se hai bisogno che funzioni, chiedi un commento e potrei inventarmi qualcosa - la cosa più facile che posso pensare è avere una classe "graph" che terrà un dizionario per tutti i nodi (invece di averlo nella classe Node)

Answer 3

Non penso che il fatto che il grafico sia ciclico è il problema: pickle (e cPickle) dovrebbero gestire le strutture cicliche dei dati correttamente. Ho provato quanto segue (con la definizione di Node) e ha funzionato bene:

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

In effetti, anche con grandi cicli non ho incontrato un problema. Per esempio., Questo funziona bene per me:

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

(questo è stato testato su Python 2.7.1)

Non ci sono altri motivi per cui salamoia potrebbe finire con molto profondo ricorsione anche se, a seconda della forma del vostro struttura dati. Se questo è il vero problema, allora potresti essere in grado di risolverlo con qualcosa del genere:

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