from pandas import * import random, math config = { 'random_seed' : 17, 'xExt': [-0.1,1.1] , 'yExt': [-0.1,1.1] , 'densityX' : 40 , 'densityY' : 20 , 'prob_0' : 0.1 , 'prob_3' : 0.075 , 'num_mod_steps' : 10 , 'mod_step_ratio' : 0.1 } def dotproduct(v1, v2): return sum((a*b) for a, b in zip(v1, v2)) def vectorLength(v): return math.sqrt(dotproduct(v, v)) def angleBtwnVectors(v1, v2): dot = dotproduct(v1, v2) det = v1[0]*v2[1] - v1[1]*v2[0] r = math.atan2(det, dot) return r * 180.0 / math.pi def angleViolation(vectorList,maxAllowed): violation = False angleList = [] for i in range(0,len(vectorList)): angleList.append( angleBtwnVectors([1,0],vectorList[i]) ) angleList.sort() angleList.append(angleList[0] + 360.0) for i in range(1,len(angleList)): if abs(angleList[i] - angleList[i-1]) > maxAllowed: violation = True return violation def addVertex(vertices): r = len(vertices['x']) vertices.ix[r,'x'] = 0 vertices.ix[r,'y'] = 0 return r def locateVertex(p,r,vertices): vertices.ix[r,'x'] = p[0] vertices.ix[r,'y'] = p[1] def addEdge(r1,r2,vertices): for c in ['a1','a2','a3','a4','a5']: if not vertices.ix[r1,c] > -1: vertices.ix[r1,c] = r2 break for c in ['a1','a2','a3','a4','a5']: if not vertices.ix[r2,c] > -1: vertices.ix[r2,c] = r1 break pylab.rcParams['figure.figsize'] = (12.0, 12.0) def makeedges(nodes): edges = DataFrame({'x1':[],'y1':[],'x2':[],'y2':[]}) r = 0 for i in range(len(nodes)): for a in ['a1','a2','a3','a4','a5','a6']: if nodes.ix[i,a] > -1 : edges.ix[r,'x1'] = nodes.ix[i,'x'] edges.ix[r,'y1'] = nodes.ix[i,'y'] edges.ix[r,'x2'] = nodes.ix[int(nodes.ix[i,a]),'x'] edges.ix[r,'y2'] = nodes.ix[int(nodes.ix[i,a]),'y'] r += 1 return edges def plotGraph(vertices,dots=True): edges = makeedges(vertices) if dots: p = vertices.plot(kind='scatter',x='x',y='y', xlim=[config['xExt'][0],config['xExt'][1]], ylim=[config['yExt'][0],config['yExt'][1]], color='grey') else: p = vertices.plot(kind='scatter',x='x',y='y', xlim=[config['xExt'][0],config['xExt'][1]], ylim=[config['yExt'][0],config['yExt'][1]], color='white') for i in range(len(edges)): p.plot([edges.ix[i,'x1'],edges.ix[i,'x2']],[edges.ix[i,'y1'],edges.ix[i,'y2']],color='black') return p def graphToJSON(vertices,fileName): verticesOut = DataFrame(vertices) adjacencies = [] for i in range(len(verticesOut['x'])): ve = [] for j in range(1,7): if verticesOut.ix[i,'a'+str(j)] > -1: ve.append( int(verticesOut.ix[i,'a'+str(j)]) ) adjacencies.append(ve) verticesOut['adjacencies'] = adjacencies verticesOut.drop('a1', axis=1, inplace=True) verticesOut.drop('a2', axis=1, inplace=True) verticesOut.drop('a3', axis=1, inplace=True) verticesOut.drop('a4', axis=1, inplace=True) verticesOut.drop('a5', axis=1, inplace=True) verticesOut.drop('a6', axis=1, inplace=True) verticesOut['vertex'] = verticesOut.index json = verticesOut.to_json(orient='records',path_or_buf=fileName) random.seed(config['random_seed']) vertices = DataFrame({'x':[],'y':[], 'a1':[],'a2':[],'a3':[],'a4':[],'a5':[],'a6':[] }) y = 0 densityX = config['densityX'] densityY = config['densityY'] nextLine = range(densityX) for i in range(len(nextLine)): r = addVertex(vertices) for line in range(densityY): currentLine = nextLine nextLine = [] numPointsInLine = len(currentLine) previousNone = False for i in range(numPointsInLine): p = [i/float(numPointsInLine-1),y] locateVertex(p,currentLine[i],vertices) if i > 0: addEdge(currentLine[i-1],currentLine[i],vertices) if line < densityY-1: # push either 0, 1 or 3 new vertices rnd = random.uniform(0,1) if rnd < config['prob_0'] and (not previousNone) and line > 0 and i > 0 and i < (numPointsInLine - 1): # 0 vertices previousNone = True elif rnd < (config['prob_3'] + config['prob_0']) and line < densityY-2: # 3 vertices nv = [] for j in range(3): if j == 0 and previousNone: nv.append(len(vertices['x']) - 1) else: nv.append(addVertex(vertices)) nextLine.append(nv[j]) addEdge(currentLine[i],nv[0],vertices) addEdge(currentLine[i],nv[2],vertices) previousNone = False else: # 1 vertex if previousNone: nv = len(vertices['x']) - 1 else: nv = addVertex(vertices) nextLine.append(nv) addEdge(currentLine[i],nv,vertices) previousNone = False y += 1.0 / float(densityY-1) vertices.head(10) p = plotGraph(vertices) graphToJSON(vertices,'vertices0.json') def angleViolationGrid(i,vertices): violation = False vt = [i] for j in range(1,7): if vertices.ix[i,'a'+str(j)] > -1: vt.append( int(vertices.ix[i,'a'+str(j)]) ) for v in vt: vectorList = [] edgeList = [] for j in range(1,7): if vertices.ix[int(v),'a'+str(j)] > -1: e = vertices.ix[int(v),'a'+str(j)] edgeList.append(e) vectorList.append( [ vertices.ix[int(e),'x'] - vertices.ix[int(v),'x'] , vertices.ix[int(e),'y'] - vertices.ix[int(v),'y'] ] ) if angleViolation(vectorList,180.0): violation = True return violation for k in range(config['num_mod_steps']): for i in range(len(vertices['x'])): if not (vertices.ix[i,'x'] == 0 or vertices.ix[i,'x'] == 1 or vertices.ix[i,'y'] == 0 or vertices.ix[i,'y'] == 1): longestEdge = -1 longestEdgeLength = 0 for j in range(1,7): if vertices.ix[i,'a'+str(j)] > -1: e = vertices.ix[i,'a'+str(j)] length = vectorLength( [ vertices.ix[int(e),'x'] - vertices.ix[i,'x'], vertices.ix[int(e),'y'] - vertices.ix[i,'y'] ] ) if length > longestEdgeLength: longestEdge = e longestEdgeLength = length saveX = vertices.ix[i,'x'] saveY = vertices.ix[i,'y'] deltaX = config['mod_step_ratio'] * ( vertices.ix[int(longestEdge),'x'] - vertices.ix[i,'x'] ) deltaY = config['mod_step_ratio'] * ( vertices.ix[int(longestEdge),'y'] - vertices.ix[i,'y'] ) vertices.ix[i,'x'] = vertices.ix[i,'x'] + deltaX vertices.ix[i,'y'] = vertices.ix[i,'y'] + deltaY if angleViolationGrid(i,vertices): vertices.ix[i,'x'] = saveX vertices.ix[i,'y'] = saveY graphToJSON(vertices,'vertices' + str(k+1) + '.json') p = plotGraph(vertices)