Травление графа циклами

Question

У меня есть собственный класс узлов в Python, который встроен в граф (который является словарем).Поскольку для их создания требуется некоторое время, я бы хотел выделить их так, чтобы мне не приходилось восстанавливать их каждый раз, когда я запускаю свой код.

К сожалению, поскольку у этого графа есть циклы, cPickle достигает максимальной рекурсииглубина:

RuntimeError: максимальная глубина рекурсии превышена при выборе объекта

Это мой объект узла:

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)

, а во второй строке я получаю ошибку глубины рекурсии.

Есть ли какие-нибудьрешения за пределами изменения структуры узла?

Answer 1

Я не думаю, что проблема в том, что ваш график циклический, является проблемой - 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 2

Вам нужно подготовить объект для засолки: если у вас есть цикл, вам нужно разбить циклы и сохранить эту информацию в какой-то другой форме.

Pickle использовать методы __getstate__ дляподготовить объект к засолке (он вызывается раньше) и __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 3

Здесь этот модифицированный класс узла содержит только имена объектов в виде строк в узле и предоставляет вам набор с полными объектами "Узел" при извлечении атрибута "children" или "parent" узла .

Внутри нет циклов - поэтому следует избегать ловушек бесконечного цикла. Вы можете реализовать дополнительные вспомогательные методы для упрощения навигации по своему усмотрению.

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" заключается в том, что вам нужно выбирать и снимать различные наборы графов. 9let скажем, что вы создаете графы g1 с набором узлов, в другом прогоне создаете граф g2 с другим набором узлов и затем, если вы откроете g1, а затем g2, удаление g2 переопределит ссылки на узлы для g1). Если вам нужно, чтобы это работало, спросите в комментарии, и я мог бы что-то придумать - проще всего подумать о том, чтобы иметь класс «graph», который будет содержать словарь для всех узлов (вместо того, чтобы иметь его в классе Node )