Description of springxy

Home > matgraph > @graph > springxy.m

springxy

PURPOSE

springxy(g) --- find a spring embedding of g

SYNOPSIS

function e=springxy(g)

DESCRIPTION

 springxy(g) --- find a spring embedding of g
 
 This routine is very slow. distxy(g) does a good job and is faster.
 
 REQUIRE THE OPTIMIZATION TOOLBOX

CROSS-REFERENCE INFORMATION

This function calls:

• embed embed --- create an embedding for a graph
• getxy getxy(g) --- give g's embedding (or [] if g doesn't have one)
• has has --- check if the graph has a particular vertex or edge
• hasxy hasxy(g) --- determine if an embedding has been created for g
• isconnected isconnected(g) --- test if g is a connected graph
• nv nv(g) --- number of vertices in g

This function is called by:

SUBFUNCTIONS

• function e = spring_energy(xy,g)
• function evec = spring_energy_vec(xy)

SOURCE CODE

0001 function e=springxy(g)
0002 % springxy(g) --- find a spring embedding of g
0003 %
0004 % This routine is very slow. distxy(g) does a good job and is faster.
0005 %
0006 % REQUIRE THE OPTIMIZATION TOOLBOX
0007 
0008 tic;
0009 n = nv(g);
0010 con = isconnected(g);
0011 
0012 if (hasxy(g))
0013     xy0 = getxy(g);
0014 else
0015     xy0 = 5*randn(n,2);
0016 end
0017 
0018 % opts = optimset('TolX',0.1, 'MaxIter', 50*n,'Display', 'off');
0019 opts = optimset('MaxIter', 10*n,'Display', 'final');
0020 
0021 %[xy,e]= fminsearch(@spring_energy, xy0, opts ,g);
0022 %[xy,e]= fminunc(@spring_energy, xy0, opts ,g);
0023 
0024 [xy,e] = lsqnonlin(@spring_energy_vec, xy0, [], [], opts);
0025 %[xy,e]= fminunc(@spring_energy, xy0, opts ,g);
0026 
0027 embed(g,xy);
0028 toc;
0029 
0030 
0031 function e = spring_energy(xy,g)
0032 
0033 vec = spring_energy_vec(xy);
0034 e = sum(vec.^2);
0035 
0036 end
0037 
0038 function evec = spring_energy_vec(xy)
0039 %n = nv(g);
0040 evec = zeros(n,n);
0041 
0042 for u=1:n-1
0043     for v=u+1:n
0044         d = norm(xy(u,:)-xy(v,:));
0045         if has(g,u,v)
0046             evec(u,v) = d;
0047         end
0048         if ~con
0049             d = min(d,n/2);
0050         end
0051         evec(v,u) = 1/sqrt(d);
0052     end
0053 end
0054 
0055 
0056 end
0057 
0058 
0059 end

---

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