Mercurial > hg > camir-aes2014

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

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first hg version after svn
author wolffd
date Tue, 10 Feb 2015 15:05:51 +0000
parents
children
rev   line source
wolffd@0 1 classdef Randlayout < Abstractlayout
wolffd@0 2 % A greedy, random layout - gives a different layout each time its called.
wolffd@0 3 % Matthew Dunham
wolffd@0 4 % University of British Columbia
wolffd@0 5 % http://www.cs.ubc.ca/~mdunham/
wolffd@0 6
wolffd@0 7 properties
wolffd@0 8 xmin; % The left most point on the graph axis in data units
wolffd@0 9 xmax; % The right most point on the graph axis in data units
wolffd@0 10 ymin; % The bottom most point on the graph axis in data units
wolffd@0 11 ymax; % The top most point on the graph axis in data units
wolffd@0 12 adjMatrix; % The adjacency matrix
wolffd@0 13 maxNodeSize; % The maximum diameter of a node in data units
wolffd@0 14 image; % An image for the button that will lanuch this layout
wolffd@0 15 name; % A unique name for instances of this class
wolffd@0 16 shortDescription; % A description for use in the tooltips
wolffd@0 17 nodeSize; % The calculated node size, call dolayout() before accessing
wolffd@0 18 centers; % The calculated node centers in an n-by-2 matrix
wolffd@0 19 seed; % The seed used to generate the last layout.
wolffd@0 20 end
wolffd@0 21
wolffd@0 22
wolffd@0 23
wolffd@0 24 methods
wolffd@0 25
wolffd@0 26 function obj = Randlayout(name,seed)
wolffd@0 27 % constructor - seed is optional.
wolffd@0 28 if(nargin < 1)
wolffd@0 29 obj.name = 'Randlayout';
wolffd@0 30 else
wolffd@0 31 obj.name = name;
wolffd@0 32 end
wolffd@0 33 if(nargin < 2)
wolffd@0 34 seed = 31;
wolffd@0 35 end
wolffd@0 36 obj.seed = seed;
wolffd@0 37 load glicons
wolffd@0 38 obj.image = icons.random;
wolffd@0 39 obj.shortDescription = 'Random Greedy Layout';
wolffd@0 40
wolffd@0 41 end
wolffd@0 42 end
wolffd@0 43
wolffd@0 44 methods(Access = 'protected')
wolffd@0 45
wolffd@0 46 function calcLayout(obj)
wolffd@0 47 rand('twister',obj.seed); randn('state',obj.seed);
wolffd@0 48 obj.seed = obj.seed + 1;
wolffd@0 49 nnodes = size(obj.adjMatrix,1);
wolffd@0 50 obj.nodeSize = min(obj.maxNodeSize,2*(obj.xmax-obj.xmin)/nnodes);
wolffd@0 51 npoints = 25;
wolffd@0 52 locdist = ones(npoints,npoints);
wolffd@0 53 c = floor(0.4*npoints):ceil(0.6*npoints);
wolffd@0 54 locdist(c,c) = 1.5; % slightly favour the center
wolffd@0 55 locdist = locdist./sum(locdist(:)); % discrete distribution over locations
wolffd@0 56 locations = zeros(nnodes,2); % holds indices into locdist
wolffd@0 57 nsize = ceil(npoints*(obj.nodeSize/2)/(obj.xmax - obj.xmin+obj.nodeSize));
wolffd@0 58 for i=1:nnodes
wolffd@0 59 while(true)
wolffd@0 60 [xcandidate,ycandidate] = obj.sample(locdist);
wolffd@0 61 [valid,locdist] = obj.isfree(xcandidate,ycandidate,locdist,nsize);
wolffd@0 62 if(valid)
wolffd@0 63 locations(i,:) = [xcandidate,ycandidate];
wolffd@0 64 locdist = obj.radiate(locdist,locations,npoints);
wolffd@0 65 break;
wolffd@0 66 end
wolffd@0 67 end
wolffd@0 68 end
wolffd@0 69 nedges = sum(obj.adjMatrix,1) + sum(obj.adjMatrix,2)';
wolffd@0 70 [val,perm] = sort(nedges,'descend');
wolffd@0 71 locations = locations(perm,:);
wolffd@0 72 obj.mapLocationsToAxes(locations,npoints);
wolffd@0 73 end
wolffd@0 74
wolffd@0 75 function mapLocationsToAxes(obj,locations,npoints)
wolffd@0 76 % Map sampled locations on a grid to actual points on the graph
wolffd@0 77 % axes.
wolffd@0 78 xndx = locations(:,1); yndx = locations(:,2);
wolffd@0 79 xmin = obj.xmin + obj.nodeSize/2;
wolffd@0 80 xmax = obj.xmax - obj.nodeSize/2;
wolffd@0 81 ymin = obj.ymin + obj.nodeSize/2;
wolffd@0 82 ymax = obj.ymax - obj.nodeSize/2;
wolffd@0 83 xstep = (xmax - xmin) /npoints;
wolffd@0 84 ystep = (ymax - ymin) /npoints;
wolffd@0 85 xpos = xmin+xstep:xstep:xmax;
wolffd@0 86 ypos = ymin+ystep:ystep:ymax;
wolffd@0 87 obj.centers = [xpos(xndx)',ypos(yndx)'];
wolffd@0 88 end
wolffd@0 89
wolffd@0 90 function [valid,locdist2] = isfree(obj,xcandidate,ycandidate,locdist,nsize)
wolffd@0 91 % Check if the sampled location is valid. Regardless, zero out the
wolffd@0 92 % spot so that we don't sample from here again.
wolffd@0 93 xndx = max(1,xcandidate-nsize):min(xcandidate+nsize,size(locdist,2));
wolffd@0 94 yndx = max(1,ycandidate-nsize):min(ycandidate+nsize,size(locdist,1));
wolffd@0 95 nodeArea = locdist(xndx,yndx);
wolffd@0 96 valid = all(nodeArea(:));
wolffd@0 97 locdist2 = locdist;
wolffd@0 98 locdist2(xndx,yndx) = 0;
wolffd@0 99 locdist2 = locdist2 ./sum(locdist(:));
wolffd@0 100 end
wolffd@0 101
wolffd@0 102 function locdist = radiate(obj,locdist,locations,npoints)
wolffd@0 103 % Update the location probability distribution.
wolffd@0 104 n = nnz(locations(:,1));
wolffd@0 105 loczeros = locdist == 0;
wolffd@0 106 for i=1:n
wolffd@0 107 [x y] = meshgrid(1:npoints,1:npoints);
wolffd@0 108 x = x(:); y = y(:);
wolffd@0 109 dist = sqrt((x-locations(i,1)).^2 + (y-locations(i,2)).^2);
wolffd@0 110 locdist = locdist + reshape(dist,npoints,npoints)';
wolffd@0 111 end
wolffd@0 112 locdist(loczeros) = 0;
wolffd@0 113 locdist = locdist ./sum(locdist(:));
wolffd@0 114 end
wolffd@0 115
wolffd@0 116 function [xndx,yndx] = sample(obj,dist)
wolffd@0 117 % Sample a single value from the non-uniform discrete distribution.
wolffd@0 118 if(isnan(dist(1)))
wolffd@0 119 perm = randperm(size(dist,1));
wolffd@0 120 xndx = perm(1);
wolffd@0 121 yndx = perm(2);
wolffd@0 122 return;
wolffd@0 123 end
wolffd@0 124 r = rand;
wolffd@0 125 cumprob = cumsum(dist(:));
wolffd@0 126 s = sum(r > cumprob(1:end-1)) + 1;
wolffd@0 127 [xndx,yndx] = ind2sub(size(dist),s);
wolffd@0 128 end
wolffd@0 129
wolffd@0 130 end
wolffd@0 131
wolffd@0 132
wolffd@0 133
wolffd@0 134 end