maximum recursion depth exceeded while calling a Python object

[GoogleCodeExporter]

connected_components is using recursion. this causes problems for big 
graphs. sys.getrecusionlimit() gives a value of 1000, which means the graph 
shouldn't have more than 1000 nodes. this can be changed by the user 
however. nevertheless, it would be better if you would program your 
algorithms without recursion.

here's an example that causes the problem:

import pygraph
gr = pygraph.graph()
gr.add_node(0)
for i in range(5000):
    gr.add_node(i+1)
    gr.add_edge(i,i+1)    
pygraph.algorithms.accessibility.connected_components(gr)

Original issue reported on code.google.com by thomas.f...@gmail.com on 23 Feb 2010 at 4:04

[GoogleCodeExporter]

You raised a relevant point. I'd rather avoid this rewriting though. As the the
number of recursive calls is limited by the number of nodes in the graph, we can
raise the recursion limit transparently and then restore it when the algorithm 
finishes.

This should yield the same behaviour as non-recursive implementations (and still
preserve the clarity of the recursive algorithm).

Would this solve the issue for you?

Original comment by pmatiello on 24 Feb 2010 at 11:32

• Changed state: Accepted
• Added labels: Milestone-1.7.0

[GoogleCodeExporter]

I think a non-recursive implementation would be more memory efficient. Even 
better 
would be a fast implementation in C. I already changed the code to a 
non-recursive 
version. You are free to use it if you want:

def connected_components(graph):
    """
    Connected components.

    @attention: Indentification of connected components is meaningful only for non-
directed
    graphs.

    @type  graph: digraph
    @param graph: Graph.

    @rtype:  dictionary
    @return: Pairing that associates each node to its connected component.
    """
    visited = {}
    count = 1

    # For 'each' node not found to belong to a connected component, find its 
connected
    # component.
    for each in graph:
        if (each not in visited):
            dfs(graph, visited, count, each)
            count = count + 1

    return visited

def dfs(graph, visited, count, root):
    """
    Given a starting vertex, root, do a depth-first search.
    """
    to_visit = []  # a list can be used as a stack in Python
    to_visit.append(root) # Start with root
    while len(to_visit) != 0:
        v = to_visit.pop()
        if v not in visited:
            visited[v]=count
            to_visit.extend(graph[v])

Original comment by thomas.f...@gmail.com on 25 Feb 2010 at 4:51

[GoogleCodeExporter]

You are probably right about the memory usage and speedy. Still, this would 
only fix
the issue for this case and we have more recursive stuff, so I think I'm going 
for
the trick I described in comment 1 — it's less work and fits my aesthetic 
bias for
recursion.

Original comment by pmatiello on 3 Mar 2010 at 12:41

[GoogleCodeExporter]

Original comment by pmatiello on 8 Mar 2010 at 11:07

• Changed state: Started

[GoogleCodeExporter]

At the risk of being a contrarian and very later to the party, I preferred the
non-recursive solution to this. I'm still intending to submit some large graph 
code.
The recursive method will simply use up way too much memory even if it is 
clearer to
read. 

Original comment by salimfadhley@gmail.com on 8 Mar 2010 at 11:17

[GoogleCodeExporter]

We have many other recursive DFS implementations around the code, each one of 
them
tailored for a different task. They all must be updated then.

Right now, I'm doing the recursionlimit trick and writing the tests for deep 
graphs.
If someone is willing to change everything to iterative implementations later 
(I'm
not, but I won't oppose either), he will have the tests to help.  But then, this
optimization of recursive algorithms should have a new issue of its own.

Original comment by pmatiello on 8 Mar 2010 at 11:39

[GoogleCodeExporter]

Okay, I guess that will have to come in with the big-graph stuff. There's no 
other
need for it. A depth-first search on a really huge graph might be a silly thing 
to do
anyway.

Original comment by salimfadhley@gmail.com on 8 Mar 2010 at 11:53

[GoogleCodeExporter]

Fixed in r688.

Original comment by pmatiello on 11 Mar 2010 at 1:32

• Changed state: Fixed