www.gusucode.com > MATLAB,波形簇分类源码程序 > MATLAB,波形簇分类源码程序/indexDunnMod/graph_EMST.m
function [G,dist,connect] = graph_EMST(data,options) % GRAPH_EMST finds the Euclidean Minimum Spanning Tree graph among points % in P dimensions. % Usage: [G,dist,connect] = graph_EMST(data,options) % ------------------------------------------------------------------------- % INPUTS: % data : [n x p] matrix of point coordinates. % options.show : if 0, plot of the graph is not shown [default=0] % ------------------------------------------------------------------------- % 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. % ------------------------------------------------------------------------- % Implementation inspired by: % http://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree %-------------------------------------------------------------------------- % Copyright (C) 2013, Nejc Ilc %-------------------------------------------------------------------------- if nargin < 2 options.show=[]; end if isempty(options) options.show=0; end [N,D]=size(data); % compute Delaunay triangulation % 2-D and 3-D case if D < 4 DT=DelaunayTri(data); else DT=delaunayn(data); end E = edges(DT); nEdges=size(E,1); dist = dist_euclidean(data,data); %create sparse matrix - graph representation C=sparse(E(:,1),E(:,2),ones(nEdges,1),N,N,nEdges); connect=C; G= C+C'; % weight graph by distances G=G.*dist; % graph is undirected, so we can forget half of edges G=tril(G); % compute minimal spanning tree on graph [G] = graphminspantree(G); if (options.show==1) fig=figure(); gplot(G,data,'-k'); hold on; plot(data(:,1),data(:,2),'.k'); axis('equal'); end