用循环腌制图表

Question

我在 python 中有一个自定义节点类，它内置于一个图形（它是一个字典）中。由于创建它们需要一段时间，因此我想对它们进行腌制，这样我就不必每次运行代码时都重新构建它们。

不幸的是，因为该图有循环，所以 cPickle 达到了最大递归深度：

运行时错误：酸洗对象时超出最大递归深度

这是我的节点对象：

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

我不认为你的图是循环的这一事实是问题——pickle（和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 上进行了测试）

尽管如此，pickle 可能最终会出现非常深的递归还有其他原因，具体取决于数据结构的形状。如果这是真正的问题，那么您也许可以通过以下方式解决它：

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

Answer 3

在这里，这个修改后的节点类仅将对象名称作为节点中的字符串保存，并在您检索节点的“子”或“父”属性时为您提供完整的“节点”对象集。

内部没有循环 - 因此它应该避免无限循环陷阱。您可以实现其他辅助方法来根据需要简化导航。

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”引用的问题是，如果您需要pickle和unpickle不同的图集9假设您确实使用一组节点创建图g1，在另一次运行中，使用另一组节点创建图g2，并且然后，如果您取消选取 g1，然后取消选取 g2，则取消选取 g2 将覆盖 g1 的节点引用）。如果你需要这个工作，请在评论中询问，我可以想出一些东西 - 我能想到的更简单的事情是有一个“图形”类，它将保存所有节点的字典（而不是将其放在 Node 类中） ）