www.gusucode.com > MATLAB,波形簇分类源码程序 > MATLAB,波形簇分类源码程序/indexDunnMod/graph_gabriel.m

    function [G,dist,connect] = graph_gabriel(data,noplot,tol)
% GRAPH_GABRIEL finds the Gabriel connectivity graph among data points.
% Usage: [G,dist,connect] = graph_gabriel(data,noplot,tol)
%--------------------------------------------------------------------------
% INPUTS:
% data   :  [n x p] matrix of point coordinates.
% noplot :  optional boolean flag indicating that plot should be 
%           suppressed [default = 0].  Plot of the Gabriel graph
%           is produced only for p=2.
% tol    :  optional tolerance for squared distance from a third point 
%           to the minimum A-B circle (i.e., that circle on whose 
%           circumference A & B are at opposite points) [default = 1e-6].
%--------------------------------------------------------------------------
% OUTPUTS:
% G       : [n x n] sparse matrix that represents a graph. Nonzero entries 
%           in matrix G represent the weights of the edges.
% dist    : corresponding edge lengths (Euclidean distances);
%           non-connected edge distances are given as zero.
% connect : [n x n] boolean adjacency matrix.
%--------------------------------------------------------------------------
% REFERENCES 
% Gabriel, KR & RR Sokal. 1969. A new statistical approach to geographic 
%   variation analysis.  Syst. Zool. 18:259-278.
%
% Matula, DW & RR Sokal. 1980. Properties of Gabriel graphs relevant to
%   geographic variation research and the clustering of points in the plane.  
%   Geogr. Analysis 12:205-222.
%--------------------------------------------------------------------------
% Copyright RE Strauss, 1/8/99
%   9/7/99 -   changed plot colors for Matlab v5.
%   10/23/02 - remove restriction of p==2;
%              produce plot only for p==2.
%   6/4/03 -   added tolerance to the minimum A-B circle.
%--------------------------------------------------------------------------
  if (nargin < 2) 
	  noplot = []; 
  end;
  if (nargin < 3) 
	  tol = []; 
  end;

  if (isempty(noplot)) 
	  noplot = 0; 
  end;
  if (isempty(tol))    
	  tol = 1e-10; 
  end;
  
  [n,p] = size(data);

  if (n<2)
    error('  GABRIEL: requires at least two points ');
  end;

  connect = zeros(n,n);

  dist = (dist_euclidean(data,data));		 % Faster implementation by Piotr Dollar
  d = dist;
  
  for i = 1:(n-1)                       % Cycle thru all possible pairs of points
    for j = (i+1):n
      dij = d(i,j);
      c = 1;
      for k = 1:n
        if (k~=i && k~=j)
          if (d(i,k)+d(j,k)-tol <= dij)
            c = 0;
          end;
        end;
      end;
      if (c)
        connect(i,j) = 1;
        connect(j,i) = 1;
      else
        dist(i,j) = 0;
        dist(j,i) = 0;
      end;
    end;
  end;

  % form graph format
  G=sparse(tril(dist));
  
  
  if (~noplot && p==2)
    figure;
    plot(data(:,1),data(:,2),'ko');
    putbnds(data(:,1),data(:,2));
    axis('equal');
    hold on;
    for i = 1:(n-1)
      for j = 2:n
        if (connect(i,j))
          plot(data([i j],1),data([i j],2),'k');
        end;
      end;
    end;
    hold off;
  end;

  return;