用週期醃一個圖

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) 

第二行是我的遞歸深度錯誤。

除了改變Node的結構之外，有沒有解決方案？

Answer 1

您需要爲pickle準備對象：如果您有一個週期，則需要打破週期並以其他形式存儲此信息。

Pickle使用方法__getstate__準備對象到pickle（它之前調用）和__setstate__來初始化對象。

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

這裏，這個修改節點類只持有對象爲節點串的名字，並給你一個當您檢索節點的「children」或「parents」屬性時，設置完整的「Node」對象。

內部沒有周期 - 所以它應該避免無限循環陷阱。您可以實施其他輔助方法以便輕鬆導航。

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對象引用）。 類寬「all_nodes」參考的問題是，如果您需要醃製和取消不同的圖形集合，請使用一組節點創建圖形g1，在另一個運行中，使用另一組節點創建圖形g2，然後如果你取消g1和後來的g2，取消g2將覆蓋g1）的節點引用。如果你需要這個工作，請在評論中提問，我可以想出一些東西 - 我能想到的最簡單的事情就是擁有一個「圖」類，它將一個字典保存到所有節點（而不是在Node類中） ）

Answer 3

我不認爲你的圖形是循環的事實是問題 - pickle（和cPickle）應該很好地處理循環數據結構。我嘗試以下（與你的節點的定義）和它的工作只是罰款：

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