Rekursionsgrenze erreicht und Segmentierungsfehler

Question

Ich weiß, dass diese Art von Fragen sehr oft gestellt wurden und keiner von ihnen hat mir geholfen.

In dem Problem unten, versuche ich, starke verbundene Komponenten eines gerichteten Graphen mit einer riesigen Größe zu implementieren. Hier ist mein Code.

import os 
import sys 
os.system('cls') 
sys.setrecursionlimit(22764) 

from itertools import groupby 
from collections import defaultdict 

## Reading the data in adjacency list form 
data = open("data.txt", 'r') 
G = defaultdict(list) 

for line in data: 
    lst = [int(s) for s in line.split()] 
    G[lst[0]].append(lst[1]) 


print 'Graph has been read!' 



def rev_graph(): 
    revG = defaultdict(list) 
    data = open("data.txt", 'r')  


    for line in data: 
     lst = [ int(s) for s in line.split() ] 
     revG[ lst[1] ].append(lst[0]) 

    print 'Graph has been reversed!' 
    return revG 


class Track(object): 
    """Keeps track of the current time, current source, component leader, 
    finish time of each node and the explored nodes.""" 

    def __init__(self): 
     self.current_time = 0 
     self.current_source = None 
     self.leader = {} 
     self.finish_time = {} 
     self.explored = set() 


def dfs(graph_dict, node, track): 
    """Inner loop explores all nodes in a SCC. Graph represented as a dict, 
    {tail node: [head nodes]}. Depth first search runs recrusively and keeps 
    track of the parameters""" 

    # print 'In Recursion node is ' + str(node) 
    track.explored.add(node) 
    track.leader[node] = track.current_source 
    for head in graph_dict[node]: 


     if head not in track.explored: 
       dfs(graph_dict, head, track) 

    track.current_time += 1 

    track.finish_time[node] = track.current_time 


def dfs_loop(graph_dict, nodes, track): 
    """Outter loop checks out all SCCs. Current source node changes when one 
    SCC inner loop finishes.""" 

    for node in nodes: 

     if node not in track.explored: 


      track.current_source = node 
      dfs(graph_dict, node, track) 


def scc(graph, nodes): 
    """First runs dfs_loop on reversed graph with nodes in decreasing order, 
    then runs dfs_loop on orignial graph with nodes in decreasing finish 
    time order(obatined from firt run). Return a dict of {leader: SCC}.""" 

    out = defaultdict(list) 
    track = Track() 

    reverse_graph = rev_graph() 


    global G 
    G = None 

    dfs_loop(reverse_graph, nodes, track) ## changes here 

    sorted_nodes = sorted(track.finish_time, 
          key=track.finish_time.get, reverse=True) 

    # print sorted_nodes 
    track.current_time = 0 
    track.current_source = None 
    track.explored = set() 

    reverse_graph = None 


    dfs_loop(graph, sorted_nodes, track) 
    for lead, vertex in groupby(sorted(track.leader, key=track.leader.get), 
           key=track.leader.get): 
     out[lead] = list(vertex) 
    return out 


maxNode = max(G.keys()) 
revNodes = list(reversed(range(1, (maxNode + 1)))) 

ans = scc(G, revNodes) 
print 'naman' 
print ans 

Jetzt, an dieser Rekursion Grenze, bekomme ich Segmentation Fault (Core Dumped) -Fehler. Unterhalb dieses Limits bekomme ich den Fehler 'maximale Rekursionstiefe überschritten in cmp'.

Ich füge auch die Datendatei an. Hier ist die link.

Answer 1

Rakete1111 gab Ihnen das Grundprinzip: Verwenden Sie keine Rekursion dafür. Sie können problemlos globale Listen von erkundeten und wartenden Knoten verwalten. Wie dem auch sei, Sie haben viel Aufwand betrieben, um diese Methoden zu umgehen.

Wenn Sie einen kleinen Versuch haben, dies schnell zum Laufen zu bringen, beginnen Sie mit Spur ein globales. Im Moment übergibst du eine einzigartige Instanz deine Traversalroutinen - bei jedem Aufruf musst du eine lokale Kopie instanziieren, die eine Menge Speicher verbraucht.

Außerdem verursacht jeder Anruf eine relativ hohe Speicherbelastung, da Sie Ihre Statuslisten auf die nächste Anrufstufe herunterlassen. Wenn Sie Ihre Rekursionen durch Schleifen mit der Aufschrift "while list not empty" ersetzen, können Sie eine Menge Speicher und all diese rekursiven Aufrufe speichern. Können Sie das selbst entspannen? Veröffentlichen Sie einen Kommentar, wenn Sie Hilfe zum Programmieren benötigen.