view toolboxes/graph_visualisation/graphViz4Matlab/layouts/Randlayout.m @ 0:e9a9cd732c1e tip

first hg version after svn

classdef Randlayout < Abstractlayout
% A greedy, random layout - gives a different layout each time its called. 
% Matthew Dunham
% University of British Columbia 
% http://www.cs.ubc.ca/~mdunham/

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