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

Я пытаюсь реализовать алгоритм поиска в глубину (DFS) для ориентированных графов, как описано в Cormen et al., Введение в алгоритмы (3-е изд.). Вот моя реализация до сих пор:

import pytest
from collections import OrderedDict
import copy


class Node(object):
    def __init__(self, color='white', parent=None, d=None, f=None):
        self.color = color
        self.parent = parent
        self.d = d          # Discovery time
        self.f = f          # Finishing time


class Graph(object):
    def __init__(self, edges, node_indices=None):
        self.edges = edges
        self.nodes = self.initialize_nodes(node_indices )
        self.adj = self.initialize_adjacency_list()

    def initialize_nodes(self, node_indices=None):
        if node_indices is None:
            node_indices = sorted(list(set(node for edge in self.edges for node in edge)))
        return OrderedDict([(node_index, Node()) for node_index in node_indices])

    def initialize_adjacency_list(self):
        A = {node: [] for node in self.nodes}
        for edge in self.edges:
            u, v = edge
            A[u].append(v)
        return A

    def dfs(self):
        self.time = 0
        for u, node in self.nodes.items():
            if node.color == 'white':
                self.dfs_visit(u)

    def dfs_visit(self, u):
        self.time += 1
        self.nodes[u].d = self.time
        self.nodes[u].color = 'gray'
        for v in self.adj[u]:
            if self.nodes[v].color == 'white':
                self.nodes[v].parent = u
                self.dfs_visit(v)
        self.nodes[u].color = 'black'
        self.time += 1
        self.nodes[u].f = self.time

    @staticmethod
    def transpose(edges):
        return [(v,u) for (u,v) in edges]

    def strongly_connected_components(self):
        self.dfs()
        finishing_times = {u: node.f for u, node in self.nodes.items()}
        self.__init__(self.transpose(self.edges))
        node_indices = sorted(finishing_times, key=finishing_times.get, reverse=True)
        self.nodes = self.initialize_nodes(node_indices)
        self.dfs()
        return self.trees()

    def trees(self):
        _trees = []
        nodes = copy.deepcopy(self.nodes)
        while nodes:
            for u, node in nodes.items():
                if node.parent is None:
                    _trees.append([u])
                    nodes.pop(u)
                else:
                    for tree in _trees:
                        if node.parent in tree:
                            tree.append(u)
                            nodes.pop(u)
        return _trees

Чтобы проверить, что это работает, я взял пример из рисунка 22.9 книги:

После переименования узлов от А до Ч 1 в 8соответственно я запустил следующий тест:

def test_strongly_connected_components():
    edges = [(1,2), (5,1), (2,5), (5,6), (2,6), (6,7), (7,6), (2,3), (3,7), (3,4), (4,3), (4,8), (7,8), (8,8)]
    graph = Graph(edges)
    assert graph.strongly_connected_components() == [[1, 5, 2], [3, 4], [6, 7], [8]]


if __name__ == "__main__":
    pytest.main([__file__+"::test_strongly_connected_components", "-s"])

Этот тест проходит, подтверждая серые оттенки SCC на рисунке.

Однако для "настоящего" упражнения мне нужно использовать входной файл SCC.txt, который содержит 875 714 строк, представляющих ребра (как пара целых чисел "голова-хвост"), и вывести размер пяти крупнейших SCC. Для этого я попробовал следующий тест:

@pytest.fixture
def edges():
    with open('SCC.txt') as f:
        return [tuple(map(int, line.split())) for line in f.read().splitlines()]

def test_SCC_on_full_graph(edges):
    graph = Graph(edges)
    SCCs = graph.strongly_connected_components()
    print([map(len, SCCs)].sort(reverse=True))      # Read off the size of the largest SCCs


if __name__ == "__main__":
    pytest.main([__file__+"::test_SCC_on_full_graph", "-s"])

Тем не менее, я сталкиваюсь с RuntimeError: maximum recursion depth exceeded in cmp:

_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 

self = <scc.Graph object at 0x103253690>, u = 209099

    def dfs_visit(self, u):
            self.time += 1
            self.nodes[u].d = self.time
            self.nodes[u].color = 'gray'
            for v in self.adj[u]:
>                   if self.nodes[v].color == 'white':
E                   RuntimeError: maximum recursion depth exceeded in cmp

scc.py:53: RuntimeError
========================== 1 failed in 21.79 seconds ===========================

Я читал об увеличении sys.setrecursionlimit, но это не рекомендуемая практика. Кроме того, я не уверен, как я мог бы улучшить код, поскольку он буквально реализует псевдокод, приведенный в книге. Любые идеи о том, как я могу преодолеть эту ошибку?

Источник

2 ответа

Решение

Мне удалось решить проблему с помощью threading библиотека с увеличенным stack_size и предел рекурсии. Вот код решения:

import sys
import pytest
from collections import OrderedDict
import copy
import threading


class Node(object):
    def __init__(self, color='white', parent=None, d=None, f=None):
        self.color = color
        self.parent = parent
        self.d = d          # Discovery time
        self.f = f          # Finishing time


class Graph(object):
    def __init__(self, edges, node_indices=None):
        self.edges = edges
        self.nodes = self.initialize_nodes(node_indices )
        self.adj = self.initialize_adjacency_list()
        self.trees = dict()

    def initialize_nodes(self, node_indices=None):
        if node_indices is None:
            node_indices = sorted(list(set(node for edge in self.edges for node in edge)))
        return OrderedDict([(node_index, Node()) for node_index in node_indices])

    def initialize_adjacency_list(self):
        A = {node: [] for node in self.nodes}
        for edge in self.edges:
            u, v = edge
            A[u].append(v)
        return A

    def dfs(self):
        self.time = 0
        for u, node in self.nodes.items():
            if node.color == 'white':
                self.dfs_visit(u, root=u)

    def dfs_visit(self, u, root=None):
        if u == root:
            self.trees[root] = set()
        self.time += 1
        self.nodes[u].d = self.time
        self.nodes[u].color = 'gray'
        for v in self.adj[u]:
            if self.nodes[v].color == 'white':
                self.nodes[v].parent = u
                self.trees[root].add(v)
                self.dfs_visit(v, root=root)
        self.nodes[u].color = 'black'
        self.time += 1
        self.nodes[u].f = self.time

    @staticmethod
    def transpose(edges):
        return [(v,u) for (u,v) in edges]

    def strongly_connected_components(self):
        self.dfs()
        finishing_times = {u: node.f for u, node in self.nodes.items()}
        self.__init__(self.transpose(self.edges))
        node_indices = sorted(finishing_times, key=finishing_times.get, reverse=True)
        self.nodes = self.initialize_nodes(node_indices)
        self.dfs()

        trees = copy.deepcopy(self.trees)
        for k, v in trees.items():
            v.add(k)
        return trees.values()


@pytest.fixture
def edges():
    with open('SCC.txt') as f:
        return [tuple(map(int, line.split())) for line in f.read().splitlines()]

def SCC_on_full_graph():
    E = edges()
    graph = Graph(E)
    SCCs = graph.strongly_connected_components()

    SCC_sizes = sorted(list(map(len, SCCs)), reverse=True)
    print(SCC_sizes[:5])                            # Read off the size of the 5 largest SCCs


if __name__ == "__main__":
    threading.stack_size(67108864)
    sys.setrecursionlimit(2**20)
    thread = threading.Thread(target=SCC_on_full_graph)
    thread.start()
Источник

DFS должен быть логически DFS, но программно вы можете попробовать обойти.

  1. написание DFS таким образом, что вы можете повторить его с одной из верхних функций, если она достигает предела рекурсии.

  2. Попробуйте использовать многопроцессорность.

PS: Возможно ли, что бесконечная рекурсия происходит для большего набора данных? логическая ошибка, возникающая при использовании большего набора данных. Если у вас есть наборы данных инкрементных размеров, вы также можете определить предел реализации алгоритма в python.

Источник
Другие вопросы по тегам