Description of dist

Home > matgraph > @graph > dist.m

dist

PURPOSE

dist(g,v,w) and dist(g,v) --- find distance(s) between vertices

SYNOPSIS

function d = dist(g,v,w)

DESCRIPTION

 dist(g,v,w) and dist(g,v) --- find distance(s) between vertices
 The form dist(g,v,w) finds the distance between vertices v and w.
 The form dist(g,v) returns a vector distance from v to all other vertices
 in the graph.
 The form dist(g) returns an n-by-n matrix whose ij entry is the distance
 between vertices i and j.

 The code for all pairs shortest distance was written by Michael Kleder
 and found on the Mathwork's MATLAB Central file exchange.

CROSS-REFERENCE INFORMATION

This function calls:

• dist dist(g,v,w) and dist(g,v) --- find distance(s) between vertices
• matrix matrix(g) --- return (a copy of) the adjacency matrix of g
• nv nv(g) --- number of vertices in g

This function is called by:

• diam diam(g) --- return the diameter of g: the length of a longest shortest
• dist dist(g,v,w) and dist(g,v) --- find distance(s) between vertices
• distxy distxy(g) -- give g a distance based embedding
• iso [yn,p] = iso(g,h,options) --- is g isomorphic to h?
• mdsxy mdsxy(g) -- create an embedding based on multidimensional scaling

SUBFUNCTIONS

• function d = alltoall(g)
• function d = onetoall(g,v)

SOURCE CODE

0001 function d = dist(g,v,w)
0002 % dist(g,v,w) and dist(g,v) --- find distance(s) between vertices
0003 % The form dist(g,v,w) finds the distance between vertices v and w.
0004 % The form dist(g,v) returns a vector distance from v to all other vertices
0005 % in the graph.
0006 % The form dist(g) returns an n-by-n matrix whose ij entry is the distance
0007 % between vertices i and j.
0008 %
0009 % The code for all pairs shortest distance was written by Michael Kleder
0010 % and found on the Mathwork's MATLAB Central file exchange.
0011 
0012 
0013 if nargin == 3
0014     dd = dist(g,v);
0015     d = dd(w);
0016     return
0017 end
0018 
0019 n = nv(g);
0020 
0021 
0022 if nargin==1
0023     d = alltoall(g);
0024     return
0025 end
0026 
0027 d = onetoall(g,v);
0028 
0029 
0030 % this subroutine was written by Michael Kleder and was found on The
0031 % Mathwork's MATLAB Central file exchange. I think my new alltoall is
0032 % faster, though.
0033 %
0034 % function B = allspath(A)
0035 % B=full(double(A));
0036 % B(B==0)=Inf;
0037 % C=ones(size(B));
0038 % iter=0;
0039 % while any(C(:))
0040 %     C=B;
0041 %     B=min(B,squeeze(min(repmat(B,[1 1 length(B)])+...
0042 %         repmat(permute(B,[1 3 2]),[1 length(B) 1]),[],1)));
0043 %     C=B-C;
0044 % end
0045 % B(logical(eye(length(B))))=0;
0046 % return
0047 
0048 
0049 % This is my replacement for allspath; I think this is faster for large
0050 % sparse graphs.
0051 function d = alltoall(g)
0052 n = nv(g);
0053 d = zeros(n,n);
0054 for v=1:n
0055     d(:,v) = dist(g,v);
0056 end
0057 return
0058 
0059 
0060 % This is a function that finds the shortest distance from v to all other
0061 % vertices in a graph
0062 function d = onetoall(g,v)
0063 A = double(matrix(g));
0064 n = nv(g);
0065 vec = zeros(n,1);
0066 vec(v) = 1;
0067 d = inf*ones(1,n);
0068 d(v) = 0;
0069 
0070 count = 0;
0071 while true
0072     count = count + 1;
0073     newv = (A*vec + vec)>0;
0074     morev = newv - vec;
0075     if (nnz(morev)==0)
0076         break
0077     end
0078     d(find(morev))=count;
0079     vec = newv;
0080 end
0081 return

---

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