#!/cygdrive/c/Python25/python.exe
#/usr/bin/python
#################################################################
#
#  Scott Hendrickson
#  scott(at)drskippy(dot)net
#  2008-11-15
#
# This work is licensed under a 
# Creative Commons Attribution-Noncommercial 3.0 United States License
# See http://creativecommons.org/licenses/by-nc/3.0/us/
#
#################################################################

import math, random

class vert:
	def __init__(this, _x, _y):
		this.x = _x
		this.y = _y
		
	def get_coords(this):
		return (this.x, this.y)
		
	def get_dist(this, _v):
		p = _v.get_coords()
		d2 = (this.y - p[1])**2 + (this.x - p[0])**2
		return math.sqrt(d2)
		
	def equal(this, _p):
		(_x,_y) = _p.get_coords()
		if this.x == _x and this.y == _y:
			return True
		else:
			return False
			
	def __repr__(this):
		return ''.join(['(',str(this.x),',',str(this.y),')'])

class edge:
	def __init__(this, _a, _b):
		if _a.get_dist(_b) <= 1:  # for diagonals math.sqrt(2):
			this.a = _a
			this.b = _b
		else:
			assert(False)
		
	def get_verts(this):
		return (this.a, this.b)
		
	def equal(this,_e):
		(v1,v2) = _e.get_verts()
		if ((this.a.equal(v1) and this.b.equal(v2)) or \
			(this.a.equal(v2) and this.b.equal(v1)) ):
			return True
		else:
			return False
			
	def __repr__(this):
		tmp = ''.join(['(',str(this.a),',', str(this.b),')'])
		return str(tmp)

class group:
	def __init__(this, _v):
		this.vert_list = []
		this.add_vert(_v)
		
	def add_vert(this, _v):
		this.vert_list.append(_v)
		
	def get_vert_list(this):
		return this.vert_list
		
	def get_size(this):
		return len(this.vert_list)
		
	def add_from_merge(this, v1):
		this.vert_list += v1

class group_manager:
	def __init__(this, _e):
		this.groups = []  # list of groups
		this.elbyv = _e # map of [edges] by vertex
		
	def add_to_group(this, v):
		matched_groups = []
		if v in this.elbyv: # check for whether vert has any edges
			for g in this.groups: # list groups
				for gv in g.get_vert_list(): # list of verts in group
					for i in this.elbyv[v]: # list of edges in target vert
						(a,b) = i.get_verts()
						if a == gv or b == gv:
							if g not in matched_groups:
								matched_groups.append(g)
		if len(matched_groups) == 0:
			this.groups.append(group(v))
		elif len(matched_groups) == 1:
			matched_groups[0].add_vert(v)
		else:
			matched_groups[0].add_vert(v)
			while len(matched_groups) > 1:
				mg1 = matched_groups.pop()
				this.merge_groups(matched_groups[0], mg1)		
	
	def get_largest_group_size(this):
		max_gs = 0
		for i in this.groups:
			if i.get_size() > max_gs:
				max_gs = i.get_size()
		return max_gs
			
	def merge_groups(this, g1, g2):
		g1.add_from_merge(g2.get_vert_list())
		this.groups.remove(g2)
		
	def span(this, v1, v2):
		#is there a group that connect opposite two verts
		for g in this.groups:
			v1_present = False
			v2_present = False
			for v in g.get_vert_list():
				if v == v1:
					v1_present = True
				if v == v2:
					v2_present = True
			if v1_present and v2_present:
				return True
		return False
			
	def __repr__(this):
		tmp = ''
		for i in this.groups:
			tmp += str(i.get_vert_list()) + '\n'
		return tmp
			

class world:
	def __init__(this,_n):
		this.n = _n
		this.v = [[vert(i,j) for i in range(0,this.n)] for j in range(0,this.n)]
		this.e = []
		
	def add_random_edge(this):
		done = False
		while not done:
			x = random.randrange(0, this.n, 1)
			y = random.randrange(0, this.n, 1)
			dx = random.choice([-1, 0, 1])
			if dx == 0:
				dy = random.choice([-1, 1])
			else:
				dy = 0
			if x + dx < 0 or x + dx >= this.n:
				dx *= -1
			if y + dy < 0 or y + dy >= this.n:
				dy *= -1
			tmp = edge(this.get_vert(x,y),this.get_vert(x+dx, y+dy))
			if not this.edge_exist(tmp):
				this.e.append(tmp)
				done = True
		
	def edge_exist(this,_e):
		for i in this.e:
			if i.equal(_e):
				return True
		return False
		
	def get_vert(this,i,j):
		return this.v[i][j]
		
	def get_edge_list_by_vert(this):
		el = {} # key is vertex, value is list of edge refs
		for e in this.e:  # look at all the edges on record
			(v1, v2) = e.get_verts()
			if v1 in el:
				el[v1].append(e)
			else:
				el[v1] = [e]
			if v2 in el:
				el[v2].append(e)
			else:
				el[v2] = [e]
		return el

	def analyze_groups(this):
		gm = group_manager(this.get_edge_list_by_vert())
		for i in this.v:
			for j in i:
				gm.add_to_group(j)
		m = gm.get_largest_group_size()
		s = gm.span(this.get_vert(0,0), this.get_vert(3,3))
		# print gm
		return m, s

	def edges_repr(this):
		tmp = str(len(this.e)) + ' edges:\n'
		for i in this.e:
			tmp += str(i) + '\n'
		return tmp


if __name__ == '__main__':
	n = 6
	max_edges = 2*(n-1)*n
	sample = 70
	print ''.join(['Edges','\t','Max Group Size'])
	for x in range(2,max_edges):
		sum_m = 0
		for j in range(0,sample):
			r = world(n)
			for i in range(0,x):
				r.add_random_edge()
			# print r.edges_repr()
			(m,s) = r.analyze_groups()
			sum_m += m
		print ''.join([str(float(x)/max_edges),'\t',str(float(sum_m)/(n*n*sample))])