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