DFS of a large dataset but maximum recursion limit reached

Question

I am doing DFS search using python. I am using networkx library to store the nodes in a graph data structure. The dataset contains 5000000 nodes. Then i converted the stored data into adjacency list using to_dict_to_list() function. Now when i call dfs() function error : maximum recursion depth limit increased. I tried to raise this with sys but same error came. what should i do?

def DFS(graph,start,visited):
        if start not in visited:
            visited.append(start)
            for i in graph[start]:
                print(start, graph[start])
                DFS(graph,i,visited)
        return visited

if __name__=="__main__":
        
    g = nx.DiGraph()
    with open('web-Google.txt', newline = '\n') as files:
        file_1 = csv.reader(files, delimiter='\t')
        for i,line in enumerate(file_1):
            from_node= int(line[0])
            to_node= int(line[1])
            g.add_edge(from_node, to_node)        

    a = nx.to_dict_of_lists(g)
    #print(a)
    b=depth_first_search(a, 0)

Can u all help me???

check https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it — Ulises Bussi, Oct 25 '22 at 16:49
Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. — Community, Oct 25 '22 at 17:58
It is a bad idea to use a recursive DFS algorithm on large graphs - as you found out you may run of memory. Better to use an algorithm based on the stack. Take a look at the second algorithm here https://en.wikipedia.org/wiki/Depth-first_search#Pseudocode — ravenspoint, Oct 25 '22 at 17:59

score 0 · Answer 1 · answered Oct 25 '22 at 22:03

The depth-first search algorithm works by maintaining a stack of nodes. In your implementation, you are using the call stack as your stack, with recursive functions serving as the push and pop operations. This runs into trouble, as you've noticed, on large graphs where the call stack is limited.

Another option is to implement DFS iteratively. An iterative version of DFS maintains an explicit stack, whose size is not limited by the size of the call stack. I would recommend doing some quick searches for "iterative DFS" to find some pseudocode or explicit Python code.

DFS of a large dataset but maximum recursion limit reached

1 Answers1