Description of distxy

Home > matgraph > @graph > distxy.m

distxy

PURPOSE

distxy(g) -- give g a distance based embedding

SYNOPSIS

function e = distxy(g, D)

DESCRIPTION

 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

CROSS-REFERENCE INFORMATION

This function calls:

• dist dist(g,v,w) and dist(g,v) --- find distance(s) between vertices
• embed embed --- create an embedding for a graph
• getxy getxy(g) --- give g's embedding (or [] if g doesn't have one)
• hasxy hasxy(g) --- determine if an embedding has been created for g
• nv nv(g) --- number of vertices in g
• size size(g) --- returns [nv,ne] for the graph

This function is called by:

SUBFUNCTIONS

• function dd = dist_discrep(xy)
• function D = dist_pair(xy)

SOURCE CODE

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

---

Generated on Thu 13-Mar-2008 14:23:52 by m2html © 2003