distxy(g) -- give g a distance based embedding we attempt to embed g in the plane so that the graph-theoretic distance between vertices matches the eucliden distance. This may also be called distxy(g,D) where D is a distance matrix. (By default D is the standard shortest-path distance, but could be replaced by, say, resistance(g). REQUIRES THE OPTIMIZATION TOOLBOX
0001 function e = distxy(g, D) 0002 % distxy(g) -- give g a distance based embedding 0003 % we attempt to embed g in the plane so that the graph-theoretic distance 0004 % between vertices matches the eucliden distance. 0005 % 0006 % This may also be called distxy(g,D) where D is a distance matrix. (By 0007 % default D is the standard shortest-path distance, but could be replaced 0008 % by, say, resistance(g). 0009 % 0010 % REQUIRES THE OPTIMIZATION TOOLBOX 0011 0012 tic; 0013 n = nv(g); 0014 0015 if nargin ==1 0016 d = dist(g); 0017 else 0018 d = D; 0019 end 0020 0021 [i,j] = find(d==inf); 0022 ni = length(i); 0023 for k=1:ni 0024 d(i(k),j(k)) = n/2; 0025 end 0026 0027 0028 if (hasxy(g)) 0029 xy0 = getxy(g); 0030 else 0031 xy0 = 5*randn(n,2); 0032 end 0033 0034 opts = optimset('MaxIter', 5*n,'Display', 'final'); 0035 0036 [xy,e] = lsqnonlin(@dist_discrep, xy0, [], [], opts); 0037 disp(['Embedding score = ', num2str(e)]) 0038 embed(g,xy); 0039 toc 0040 0041 function dd = dist_discrep(xy) 0042 0043 %divisor = d + eye(n); 0044 dxy = dist_pair(xy); 0045 divisor = real((d+eye(n))); 0046 % divisor = exp(d/4)-0.8; 0047 dd = d - dxy; 0048 dd = dd./divisor; 0049 dd = dd(:); 0050 0051 end 0052 0053 0054 %-------------------------------------------------------- 0055 function D = dist_pair(xy) 0056 % find Euclidean distances between vertices in xy embedding 0057 n = size(xy,1); % get # of rows 0058 c = sum(xy.*xy,2); % norm^2 of rows 0059 Y = c * ones(1,n); 0060 D = Y + Y' - 2*xy*xy'; 0061 D = real(sqrt(D)); 0062 0063 end % end of dist_pair 0064 0065 end % end of distxy