comparison 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