J'essaie d'implémenter l'algorithme de recherche en profondeur en profondeur (DFS) pour les graphes orientés comme décrit dans Cormen et al., Introduction to Algorithms (3rd ed.). Voici ma mise en œuvre jusqu'à présent:Python "RuntimeError: profondeur de récursivité maximale dépassée" en profondeur-première recherche
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
Pour vérifier que cela fonctionne, j'ai pris un exemple de la figure 22.9 du livre:
Après avoir renommé les nœuds un à h1-8, respectivement, j'ai couru le test suivant:
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"])
Ce test réussit, confirmant les SCCs ombrés en gris sur la figure. Pour l'exercice «réel», cependant, j'ai besoin d'utiliser un fichier d'entrée, SCC.txt, qui contient 875,714 lignes représentant des arêtes (comme une paire tête-queue d'entiers), et qui affiche la taille des cinq plus grands SCC. À cette fin, j'ai essayé le test suivant:
@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"])
Cependant, je lance dans un 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 ===========================
J'ai lu sur l'augmentation de sys.setrecursionlimit, mais cela ne semble pas être une pratique recommandée . Autre que je ne sais pas comment je pourrais améliorer le code car il implémente littéralement le pseudo-code donné dans le livre. Des idées sur comment je peux surmonter cette erreur?