サイクルでグラフをpicklingする

Question

私はグラフに組み込まれたPythonでカスタムノードクラスを持っています（辞書です）。これらは作成に時間がかかるので、コードを実行するたびに再構築する必要がないように、それらを漬けておきたいと思います。

このグラフはサイクルを持っているので、残念ながら、cPickleのが最大の再帰の深さを打つ：

RuntimeError: maximum recursion depth exceeded while pickling an object

これは私のノードオブジェクトです：

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

これは私が私のグラフを構築する方法である：

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 

私のメインでは、私は

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

2行目で再帰深度エラーが発生します。

Nodeの構造を変更する以外に解決策はありますか？

Answer 1

ピクルのオブジェクトを準備する必要があります。サイクルがある場合は、サイクルを中断し、この情報を他の形式で保存する必要があります。オブジェクトを初期化するために、ピクルス（それは前呼び出し）と__setstate__にオブジェクトを準備する

ピクルス使用方法__getstate__。

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) 

私はあなたがどのようにサイクルを打破し、参加する:)

Answer 2

ここでアイデアを見つけるよりも確信している、この修正ノードクラスは、ノード内の文字列などのオブジェクトの名前だけを保持し、あなたに与えますノードの「子」属性または「親」属性のいずれかを取得するときに、完全な「ノード」オブジェクトで設定されます。

内部的にサイクルがないため、無限ループトラップを回避する必要があります。追加の便利な方法を実装して、必要に応じて簡単にナビゲーションを行うことができます。

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 

欠点は、それがすべて実際に作成したノードへの参照がある「all_nodesを」という名前のクラスの辞書を維持することです。 （Pickleは、すべてのNodeオブジェクトによって参照されるため、指定されたグラフに対してこの辞書をpickleするだけで十分です。 クラス全体の "all_nodes"リファレンスの問題は、異なるグラフの集合をpickleしてunpickleする必要がある場合です。9letは、ノードの集合を使ってグラフg1を作成し、別の実行ではノードの集合を使ってグラフg2を作成し、 g1をアンピックルし、後でg2をアンパックすると、g2のunpickleはg1のノード参照を上書きします。これを動作させるために必要な場合は、コメントで尋ねてみてください。何かを考え出すことができます。私が考えることができる簡単なことは、Nodeクラスではなく、すべてのノードに辞書を保持する "グラフ" ）

Answer 3

私は、あなたのグラフが循環しているという事実は問題ではないと思います.picle（とcPickle）は周期的なデータ構造をうまく処理する必要があります。私は次のように（Nodeの定義で）試してみましたが、うまくいきました。

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

確かに、大きなサイクルでも問題に遭遇しませんでした。例えば。、これは私のために正常に動作します：

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

（これは全てのPython 2.7.1でテストされました）

ピクルスがあなたの形状に応じて、しかし非常に深い再帰で終わるかもしれない他の理由があります。データ構造。これが本当の問題であれば、次のように修正することができます：

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