classification
Title: Recursion bug in deepcopy
Type: behavior Stage:
Components: Library (Lib) Versions: Python 2.5
process
Status: closed Resolution: wont fix
Dependencies: Superseder:
Assigned To: Nosy List: Zeroth, alexandre.vassalotti, facundobatista, gpolo
Priority: normal Keywords:

Created on 2008-06-05 21:03 by Zeroth, last changed 2008-06-21 14:52 by facundobatista. This issue is now closed.

Messages (6)
msg67728 - (view) Author: Tyler Laing (Zeroth) Date: 2008-06-05 21:03
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.
msg67730 - (view) Author: Tyler Laing (Zeroth) Date: 2008-06-05 21:42
Whoops, sorry, correction, when there are 100 vertexes and 500 edges.
msg67731 - (view) Author: Guilherme Polo (gpolo) * (Python committer) Date: 2008-06-05 21:46
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.
msg67732 - (view) Author: Tyler Laing (Zeroth) Date: 2008-06-05 21:55
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
msg67742 - (view) Author: Alexandre Vassalotti (alexandre.vassalotti) * (Python committer) Date: 2008-06-05 23:50
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
msg68497 - (view) Author: Facundo Batista (facundobatista) * (Python committer) Date: 2008-06-21 14:52
Two weeks passed, closing it manually (see
http://mail.python.org/pipermail/python-dev/2008-February/076992.html).
History
Date User Action Args
2008-06-21 14:52:28facundobatistasetstatus: pending -> closed
nosy: + facundobatista
messages: + msg68497
2008-06-06 09:14:06georg.brandlsetstatus: open -> pending
resolution: wont fix
2008-06-05 23:50:19alexandre.vassalottisetnosy: + alexandre.vassalotti
messages: + msg67742
2008-06-05 21:55:57Zerothsetmessages: + msg67732
2008-06-05 21:46:25gpolosetnosy: + gpolo
messages: + msg67731
2008-06-05 21:42:42Zerothsetmessages: + msg67730
2008-06-05 21:03:49Zerothcreate