Recursion bug in deepcopy #47293

Activity

1. Zeroth commented on Jun 5, 2008

   

   Zerothmannequin

   on Jun 5, 2008

   MannequinAuthor

   More actions

   With the following code:
   class Vertex:
   def __init__(self, type):
   self.type = type
   self.color=-1
   self.edges=[]

   class Edge:
   	def __init__(self, V1, V2):
   		self.vertexes=[V1, V2]
   		V1.edges.append(self)
   		V2.edges.append(self)

   Where the references are cyclic(this is for a research project into
   graph algorithms), and using deepcopy, even on a tiny graph of five
   vertexes and 25 edges causes deepcopy to run into the recursion limit.
   At the very least, it should warn it can't copy the indicated object, as
   the references are cyclic. At the very most, it should be able to handle
   complex cyclic references like this properly.
2. Zeroth

   added

   stdlibStandard Library Python modules in the Lib/ directoryStandard Library Python modules in the Lib/ directory

   type-bugAn unexpected behavior, bug, or errorAn unexpected behavior, bug, or error

   on Jun 5, 2008
3. Zeroth commented on Jun 5, 2008

   

   Zerothmannequin

   on Jun 5, 2008

   MannequinAuthor

   More actions

   Whoops, sorry, correction, when there are 100 vertexes and 500 edges.
4. gpolo commented on Jun 5, 2008

   

   gpolomannequin

   on Jun 5, 2008

   Mannequin

   More actions

   This should have been fixed at 2.2, as long as you change your classes
   to new-style classes. If it still happens, post a sample code using your
   new code that uses new-style classes.
5. Zeroth commented on Jun 5, 2008

   

   Zerothmannequin

   on Jun 5, 2008

   MannequinAuthor

   More actions

   Same problem, even with new-style classes. Here, I'll show the function
   I use to generate the graph as well.

   class Vertex(object):
   	def __init__(self, type):
   		self.type = type
   		self.color=-1
   		self.edges=[]
   		
   
   		
   class Edge(object):
   	def __init__(self, V1, V2):
   		self.vertexes=[V1, V2]
   		V1.edges.append(self)
   		V2.edges.append(self)
   
   def generate(graph={'V':[], 'E':[]}, seed=777, vertexes=5, edges=25):
   	#generates a graph similar to the KEGG pathway database format.
   	# Purpose is for testing algorithms on a smaller scale "predicatible" graph
   	# For that reason, the "random" selections are seeded with a known
   number. This is to be able
   	# to measure efficacy, in that on the same graph, if algorithm A
   performs in half the time, its 
   	# not a characteristic of the graph, but the algorithm.
   	r=random.Random(seed)
   	p=[0, 0, 0, 0]
   	c=0
   	#generate vertices, with a regularly incremented set of numbers, to
   appear like the KEGG pathway database does.
   	while c!=vertexes:
   		#This is ugly, could be done easier in a loop. Fix later.
   		p[3]+=1
   		if p[3]>9:
   			p[3]=0
   			p[2]+=1
   		if p[2]>9:
   			p[2]=0
   			p[1]+=1
   		if p[1]>9:
   			p[1]=0
   			p[0]+=1
   		#we copy the set of numbers, due to the way python passes lists by
   reference, instead of by copy.
   		v=Vertex(p[:])
   		graph['V'].append(v)
   		c+=1
   	
   	
   	v=graph['V']
   	if len(v)!=vertexes:
   		print "Not enough vertices, aborting."
   		return graph
   	c=0
   	#randomly choose two vertices. Could even, randomly, be the same vertex.
   	# Then, connect an edge between them. Just creating the edge by
   implication,
   	# with the vertices passed, connects them all together.
   	while c!=edges:
   		v1=r.choice(v)
   		v2=r.choice(v)
   		graph['E'].append(Edge(v1, v2))
   		c+=1
   	
   	if len(graph['E']) !=edges:
   		print "Not enough edges, aborting."
   	return graph

   And here is how I use it:

   >>import graph, copy
   >>g=graph.generate(vertexes=100, edges=500)
   >>g2=copy.deepcopy(g)

   Thanks for the prompt response, this isn't critical in nature, just
   playing around with the graph, and wanted to alter a copy of it. Ran
   into this bug, thought I should report it. :)

   -Zeroth
6. avassalotti commented on Jun 5, 2008

   

   avassalotti

   on Jun 5, 2008

   Member

   More actions

   Your graph is simply too deep for Python to handle it. The copy module
   (and also the pickle) pushes a new stack frame every time a new
   container object is encountered. Therefore, there is a recursion limit
   to prevent the interpreter from crashing.

   If you want, you can carefully increase the limit by using the function
   sys.setrecursionlimit. Using your example:

   >>> sys.setrecursionlimit(2000)
   >>> g2 = copy.deepcopy(g)
   >>> # no error
7. facundobatista commented on Jun 21, 2008

   

   facundobatista

   on Jun 21, 2008

   Member

   More actions

   Two weeks passed, closing it manually (see
   http://mail.python.org/pipermail/python-dev/2008-February/076992.html).
8. facundobatista

   closed this as completedon Jun 21, 2008
9. ezio-melotti

   transferred this issue fromon Apr 10, 2022