Daniel@0: classdef Randlayout < Abstractlayout Daniel@0: % A greedy, random layout - gives a different layout each time its called. Daniel@0: % Matthew Dunham Daniel@0: % University of British Columbia Daniel@0: % http://www.cs.ubc.ca/~mdunham/ Daniel@0: Daniel@0: properties Daniel@0: xmin; % The left most point on the graph axis in data units Daniel@0: xmax; % The right most point on the graph axis in data units Daniel@0: ymin; % The bottom most point on the graph axis in data units Daniel@0: ymax; % The top most point on the graph axis in data units Daniel@0: adjMatrix; % The adjacency matrix Daniel@0: maxNodeSize; % The maximum diameter of a node in data units Daniel@0: image; % An image for the button that will lanuch this layout Daniel@0: name; % A unique name for instances of this class Daniel@0: shortDescription; % A description for use in the tooltips Daniel@0: nodeSize; % The calculated node size, call dolayout() before accessing Daniel@0: centers; % The calculated node centers in an n-by-2 matrix Daniel@0: seed; % The seed used to generate the last layout. Daniel@0: end Daniel@0: Daniel@0: Daniel@0: Daniel@0: methods Daniel@0: Daniel@0: function obj = Randlayout(name,seed) Daniel@0: % constructor - seed is optional. Daniel@0: if(nargin < 1) Daniel@0: obj.name = 'Randlayout'; Daniel@0: else Daniel@0: obj.name = name; Daniel@0: end Daniel@0: if(nargin < 2) Daniel@0: seed = 31; Daniel@0: end Daniel@0: obj.seed = seed; Daniel@0: load glicons Daniel@0: obj.image = icons.random; Daniel@0: obj.shortDescription = 'Random Greedy Layout'; Daniel@0: Daniel@0: end Daniel@0: end Daniel@0: Daniel@0: methods(Access = 'protected') Daniel@0: Daniel@0: function calcLayout(obj) Daniel@0: rand('twister',obj.seed); randn('state',obj.seed); Daniel@0: obj.seed = obj.seed + 1; Daniel@0: nnodes = size(obj.adjMatrix,1); Daniel@0: obj.nodeSize = min(obj.maxNodeSize,2*(obj.xmax-obj.xmin)/nnodes); Daniel@0: npoints = 25; Daniel@0: locdist = ones(npoints,npoints); Daniel@0: c = floor(0.4*npoints):ceil(0.6*npoints); Daniel@0: locdist(c,c) = 1.5; % slightly favour the center Daniel@0: locdist = locdist./sum(locdist(:)); % discrete distribution over locations Daniel@0: locations = zeros(nnodes,2); % holds indices into locdist Daniel@0: nsize = ceil(npoints*(obj.nodeSize/2)/(obj.xmax - obj.xmin+obj.nodeSize)); Daniel@0: for i=1:nnodes Daniel@0: while(true) Daniel@0: [xcandidate,ycandidate] = obj.sample(locdist); Daniel@0: [valid,locdist] = obj.isfree(xcandidate,ycandidate,locdist,nsize); Daniel@0: if(valid) Daniel@0: locations(i,:) = [xcandidate,ycandidate]; Daniel@0: locdist = obj.radiate(locdist,locations,npoints); Daniel@0: break; Daniel@0: end Daniel@0: end Daniel@0: end Daniel@0: nedges = sum(obj.adjMatrix,1) + sum(obj.adjMatrix,2)'; Daniel@0: [val,perm] = sort(nedges,'descend'); Daniel@0: locations = locations(perm,:); Daniel@0: obj.mapLocationsToAxes(locations,npoints); Daniel@0: end Daniel@0: Daniel@0: function mapLocationsToAxes(obj,locations,npoints) Daniel@0: % Map sampled locations on a grid to actual points on the graph Daniel@0: % axes. Daniel@0: xndx = locations(:,1); yndx = locations(:,2); Daniel@0: xmin = obj.xmin + obj.nodeSize/2; Daniel@0: xmax = obj.xmax - obj.nodeSize/2; Daniel@0: ymin = obj.ymin + obj.nodeSize/2; Daniel@0: ymax = obj.ymax - obj.nodeSize/2; Daniel@0: xstep = (xmax - xmin) /npoints; Daniel@0: ystep = (ymax - ymin) /npoints; Daniel@0: xpos = xmin+xstep:xstep:xmax; Daniel@0: ypos = ymin+ystep:ystep:ymax; Daniel@0: obj.centers = [xpos(xndx)',ypos(yndx)']; Daniel@0: end Daniel@0: Daniel@0: function [valid,locdist2] = isfree(obj,xcandidate,ycandidate,locdist,nsize) Daniel@0: % Check if the sampled location is valid. Regardless, zero out the Daniel@0: % spot so that we don't sample from here again. Daniel@0: xndx = max(1,xcandidate-nsize):min(xcandidate+nsize,size(locdist,2)); Daniel@0: yndx = max(1,ycandidate-nsize):min(ycandidate+nsize,size(locdist,1)); Daniel@0: nodeArea = locdist(xndx,yndx); Daniel@0: valid = all(nodeArea(:)); Daniel@0: locdist2 = locdist; Daniel@0: locdist2(xndx,yndx) = 0; Daniel@0: locdist2 = locdist2 ./sum(locdist(:)); Daniel@0: end Daniel@0: Daniel@0: function locdist = radiate(obj,locdist,locations,npoints) Daniel@0: % Update the location probability distribution. Daniel@0: n = nnz(locations(:,1)); Daniel@0: loczeros = locdist == 0; Daniel@0: for i=1:n Daniel@0: [x y] = meshgrid(1:npoints,1:npoints); Daniel@0: x = x(:); y = y(:); Daniel@0: dist = sqrt((x-locations(i,1)).^2 + (y-locations(i,2)).^2); Daniel@0: locdist = locdist + reshape(dist,npoints,npoints)'; Daniel@0: end Daniel@0: locdist(loczeros) = 0; Daniel@0: locdist = locdist ./sum(locdist(:)); Daniel@0: end Daniel@0: Daniel@0: function [xndx,yndx] = sample(obj,dist) Daniel@0: % Sample a single value from the non-uniform discrete distribution. Daniel@0: if(isnan(dist(1))) Daniel@0: perm = randperm(size(dist,1)); Daniel@0: xndx = perm(1); Daniel@0: yndx = perm(2); Daniel@0: return; Daniel@0: end Daniel@0: r = rand; Daniel@0: cumprob = cumsum(dist(:)); Daniel@0: s = sum(r > cumprob(1:end-1)) + 1; Daniel@0: [xndx,yndx] = ind2sub(size(dist),s); Daniel@0: end Daniel@0: Daniel@0: end Daniel@0: Daniel@0: Daniel@0: Daniel@0: end