import random,sys,math """Random graph generator """ class RandomGraph: def __init__(self,numnodes=12): self.numnodes = numnodes if self.numnodes > 26: print "Maximum number of nodes = 26" self.numnodes = 26 elif self.numnodes < 12: print "Minimum number of nodes = 12" self.numnodes = 12 self.names = ['S', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'R', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'] self.maxRows = math.ceil(math.sqrt(self.numnodes)) self.maxCols = math.ceil(math.sqrt(self.numnodes)) def getCoord(self, i): x= i % self.maxCols y = math.floor(i/self.maxCols) return (x,y) def getIndex(self, x, y): if x<0 or y < 0 or x>=self.maxCols or y>=self.maxRows: return -1 ind = y*self.maxCols + x if ind < self.numnodes: return ind else: return -1 def getAllNgbrs(self, i): (x,y) = self.getCoord(i) ngbrs = [] ngbrsX = [x-1, x, x+1] ngbrsY = [y-1, y, y+1] for nx in ngbrsX: for ny in ngbrsY: if not (nx==x and ny == y): ind = self.getIndex(nx, ny) if ind>=0: ngbrs.append(ind) return ngbrs def checkLinkExists(self, links, a, b): for (c,d) in links: if a==c and b==d: return True if a==d and b==c: return True return False def genGraph(self): NODES = [] LINKS = [] for i in range(self.numnodes): (x,y) = self.getCoord(i) name = self.names[i] NODES.append((name,x,y)) for i in range(self.numnodes): ngbrs = self.getAllNgbrs(i) outdeg = int(random.random()*len(ngbrs)) + 1 sampleNgbrs = random.sample(ngbrs, outdeg) for n1 in sampleNgbrs: n = int(n1) if not self.checkLinkExists(LINKS, self.names[i], self.names[n]): LINKS.append((self.names[i], self.names[n])) return (NODES, LINKS)