Daniel@0: function [h,Coord,Color,height] = som_dendrogram(Z,varargin)
Daniel@0: 
Daniel@0: %SOM_DENDROGRAM Visualize a dendrogram.
Daniel@0: %
Daniel@0: % [h,Coord,Color,height] = som_dendrogram(Z, [[argID,] value, ...])
Daniel@0: %
Daniel@0: %  Z = som_linkage(sM); 
Daniel@0: %  som_dendrogram(Z); 
Daniel@0: %  som_dendrogram(Z,sM); 
Daniel@0: %  som_dendrogram(Z,'coord',co); 
Daniel@0: %
Daniel@0: %  Input and output arguments ([]'s are optional):
Daniel@0: %   h        (vector) handle to the arc lines
Daniel@0: %   Z        (matrix) size n-1 x 1, the hierarchical cluster matrix
Daniel@0: %                     returned by functions like LINKAGE and SOM_LINKAGE
Daniel@0: %                     n is the number of original data samples.
Daniel@0: %   [argID,  (string) See below. The values which are unambiguous can 
Daniel@0: %    value]  (varies) be given without the preceeding argID.
Daniel@0: %   Coord    (matrix) size 2*n-1 x {1,2}, the coordinates of the
Daniel@0: %                     original data samples and cluster nodes used 
Daniel@0: %                     in the visualization
Daniel@0: %   Color    (matrix) size 2*n-1 x 3, the colors of ...
Daniel@0: %   height   (vector) size 2*n-1 x 1, the heights of ...
Daniel@0: %   
Daniel@0: % Here are the valid argument IDs and corresponding values. The values 
Daniel@0: % which are unambiguous (marked with '*') can be given without the
Daniel@0: % preceeding argID.
Daniel@0: %   'data'  *(struct) map or data struct: many other optional 
Daniel@0: %                     arguments require this 
Daniel@0: %            (matrix) data matrix
Daniel@0: %   'coord'  (matrix) size n x 1 or n x 2, the coordinates of 
Daniel@0: %                     the original data samples either in 1D or 2D
Daniel@0: %            (matrix) size 2*n-1 x {1,2}, the coordinates of both
Daniel@0: %                     original data samples and each cluster
Daniel@0: %           *(string) 'SOM', 'pca#', 'sammon#', or 'cca#': the coordinates
Daniel@0: %                     are calculated using the given data and the 
Daniel@0: %                     required projection algorithm. The '#' at the
Daniel@0: %                     end of projection algorithms refers to the 
Daniel@0: %                     desired output dimension and can be either 1 or 2
Daniel@0: %                     (2 by default). In case of 'SOM', the unit
Daniel@0: %                     coordinates (given by SOM_VIS_COORDS) are used.
Daniel@0: %   'color'  (matrix) size n x 3, the color of the original data samples
Daniel@0: %            (matrix) size 2*n-1 x 3, the colors of both original 
Daniel@0: %                     data samples and each cluster
Daniel@0: %            (string) color specification, e.g. 'r.', used for each node
Daniel@0: %   'height' (vector) size n-1 x 1, the heights used for each cluster
Daniel@0: %            (vector) size 2*n-1 x 1, the heights used for both original
Daniel@0: %                     data samples and each cluster
Daniel@0: %           *(string) 'order', the order of combination determines height
Daniel@0: %                     'depth', the depth at which the combination
Daniel@0: %                     happens determines height
Daniel@0: %   'linecolor' (string) color specification for the arc color, 'k' by default
Daniel@0: %               (vector) size 1 x 3
Daniel@0: %
Daniel@0: % See also SOM_LINKAGE, DENDROGRAM.
Daniel@0: 
Daniel@0: % Copyright (c) 2000 by Juha Vesanto
Daniel@0: % Contributed to SOM Toolbox on June 16th, 2000 by Juha Vesanto
Daniel@0: % http://www.cis.hut.fi/projects/somtoolbox/
Daniel@0:  
Daniel@0: % Version 2.0beta juuso 160600
Daniel@0: 
Daniel@0: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Daniel@0: %% read the arguments
Daniel@0: 
Daniel@0: % Z 
Daniel@0: nd = size(Z,1)+1; 
Daniel@0: nc = size(Z,1); 
Daniel@0: 
Daniel@0: % varargin
Daniel@0: Coordtype = 'natural'; Coord = []; codim = 1; 
Daniel@0: Colortype = 'none'; Color = [];
Daniel@0: height = [zeros(nd,1); Z(:,3)]; 
Daniel@0: M = []; 
Daniel@0: linecol = 'k'; 
Daniel@0: 
Daniel@0: i=1; 
Daniel@0: while i<=length(varargin), 
Daniel@0:   argok = 1; 
Daniel@0:   if ischar(varargin{i}), 
Daniel@0:     switch varargin{i}, 
Daniel@0:      case 'data', i = i + 1; M = varargin{i}; 
Daniel@0:      case 'coord', 
Daniel@0:       i=i+1; 
Daniel@0:       if isnumeric(varargin{i}), Coord = varargin{i}; Coordtype = 'given'; 
Daniel@0:       else 
Daniel@0: 	if strcmp(varargin{i},'SOM'), Coordtype = 'SOM'; 
Daniel@0: 	else Coordtype = 'projection'; Coord = varargin{i}; 
Daniel@0: 	end
Daniel@0:       end
Daniel@0:      case 'color', 
Daniel@0:       i=i+1; 
Daniel@0:       if isempty(varargin{i}), Colortype = 'none'; 
Daniel@0:       elseif ischar(varargin{i}), Colortype = 'colorspec'; Color = varargin{i};
Daniel@0:       else Colortype = 'given'; Color = varargin{i}; 
Daniel@0:       end
Daniel@0:      case 'height', i=i+1; height = varargin{i}; 
Daniel@0:      case 'linecolor', i=i+1; linecol = varargin{i}; 
Daniel@0:      case 'SOM', 
Daniel@0:       Coordtype = 'SOM'; 
Daniel@0:      case {'pca','pca1','pca2','sammon','sammon1','sammon2','cca','cca1','cca2'}, 
Daniel@0:       Coordtype = 'projection'; Coord = varargin{i}; 
Daniel@0:      case {'order','depth'}, height = varargin{i};  
Daniel@0:     end
Daniel@0:   elseif isstruct(varargin{i}), M = varargin{i}; 
Daniel@0:   else
Daniel@0:     argok = 0; 
Daniel@0:   end
Daniel@0:   if ~argok, 
Daniel@0:     disp(['(som_dendrogram) Ignoring invalid argument #' num2str(i+1)]); 
Daniel@0:   end
Daniel@0:   i = i+1; 
Daniel@0: end
Daniel@0: 
Daniel@0: switch Coordtype, 
Daniel@0:  case 'SOM', 
Daniel@0:   if isempty(M) | ~any(strcmp(M.type,{'som_map','som_topol'})) , 
Daniel@0:     error('Cannot determine SOM coordinates without a SOM.'); 
Daniel@0:   end
Daniel@0:   if strcmp(M.type,'som_map'), M = M.topol; end
Daniel@0:  case 'projection', 
Daniel@0:   if isempty(M), error('Cannot do projection without the data.'); end
Daniel@0:   if isstruct(M), 
Daniel@0:     if strcmp(M.type,'som_data'), M = M.data; 
Daniel@0:     elseif strcmp(M.type,'som_map'), M = M.codebook; 
Daniel@0:     end
Daniel@0:   end  
Daniel@0:   if size(M,1) ~= nd, 
Daniel@0:     error('Given data must be equal in length to the number of original data samples.')
Daniel@0:   end    
Daniel@0:  case 'given', 
Daniel@0:   if size(Coord,1) ~= nd & size(Coord,1) ~= nd+nc, 
Daniel@0:     error('Size of given coordinate matrix does not match the cluster hierarchy.');
Daniel@0:   end  
Daniel@0: end
Daniel@0: 
Daniel@0: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Daniel@0: %% initialization
Daniel@0: 
Daniel@0: % Coordinates
Daniel@0: switch Coordtype, 
Daniel@0:  case 'natural', o = leavesorder(Z)'; [dummy,Coord] = sort(o); codim = 1; 
Daniel@0:  case 'SOM', Coord = som_vis_coords(M.lattice,M.msize); codim = 2;   
Daniel@0:  case 'projection', 
Daniel@0:   switch Coord, 
Daniel@0:    case {'pca','pca2'},       Coord = pcaproj(M,2);   codim = 2; 
Daniel@0:    case 'pca1',               Coord = pcaproj(M,1);   codim = 1; 
Daniel@0:    case {'cca','cca2'},       Coord = cca(M,2,20);    codim = 2; 
Daniel@0:    case 'cca1',               Coord = cca(M,1,20);    codim = 1; 
Daniel@0:    case {'sammon','sammon2'}, Coord = sammon(M,2,50); codim = 2; 
Daniel@0:    case 'sammon1',            Coord = sammon(M,1,50); codim = 1; 
Daniel@0:   end
Daniel@0:  case 'given', codim = min(size(Coord,2),2); % nill
Daniel@0: end
Daniel@0: 
Daniel@0: if size(Coord,1) == nd, 
Daniel@0:   Coord = [Coord; zeros(nc,size(Coord,2))]; 
Daniel@0:   for i=(nd+1):(nd+nc), 
Daniel@0:     leaves = leafnodes(Z,i,nd);
Daniel@0:     if any(leaves), Coord(i,:) = mean(Coord(leaves,:),1); else Coord(i,:) = Inf; end
Daniel@0:   end
Daniel@0: end
Daniel@0: 
Daniel@0: % Colors
Daniel@0: switch Colortype, 
Daniel@0:  case 'colorspec', % nill
Daniel@0:  case 'none', Color = ''; 
Daniel@0:  case 'given',
Daniel@0:   if size(Color,1) == nd, 
Daniel@0:     Color = [Color; zeros(nc,3)]; 
Daniel@0:     for i=(nd+1):(nd+nc), 
Daniel@0:       leaves = leafnodes(Z,i,nd);
Daniel@0:       if any(leaves), Color(i,:) = mean(Color(leaves,:),1); 
Daniel@0:       else Color(i,:) = 0.8; 
Daniel@0:       end
Daniel@0:     end
Daniel@0:   end
Daniel@0: end
Daniel@0: 
Daniel@0: % height
Daniel@0: if ischar(height), 
Daniel@0:   switch height, 
Daniel@0:    case 'order', height = [zeros(nd,1); [1:nc]']; 
Daniel@0:    case 'depth', height = nodedepth(Z); height = max(height) - height; 
Daniel@0:   end
Daniel@0: else
Daniel@0:   if length(height)==nc, height = [zeros(nd,1); height]; end
Daniel@0: end
Daniel@0: 
Daniel@0: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Daniel@0: %% draw
Daniel@0: 
Daniel@0: % the arcs
Daniel@0: lfrom = []; lto = []; 
Daniel@0: for i=1:nd+nc, 
Daniel@0:   if i<=nd, ch = [];  
Daniel@0:   elseif ~isfinite(Z(i-nd,3)), ch = []; 
Daniel@0:   else ch = Z(i-nd,1:2)'; 
Daniel@0:   end
Daniel@0:   if any(ch), 
Daniel@0:     lfrom = [lfrom; i*ones(length(ch),1)]; 
Daniel@0:     lto = [lto; ch]; 
Daniel@0:   end
Daniel@0: end
Daniel@0: 
Daniel@0: % the coordinates of the arcs
Daniel@0: if codim == 1, 
Daniel@0:   Lx = [Coord(lfrom), Coord(lto), Coord(lto)];
Daniel@0:   Ly = [height(lfrom), height(lfrom), height(lto)];
Daniel@0:   Lz = []; 
Daniel@0: else
Daniel@0:   Lx = [Coord(lfrom,1), Coord(lto,1), Coord(lto,1)];
Daniel@0:   Ly = [Coord(lfrom,2), Coord(lto,2), Coord(lto,2)];
Daniel@0:   Lz = [height(lfrom), height(lfrom), height(lto)];
Daniel@0: end
Daniel@0: 
Daniel@0: washold = ishold; 
Daniel@0: if ~washold, cla; end
Daniel@0: 
Daniel@0: % plot the lines
Daniel@0: if isempty(Lz), 
Daniel@0:   h = line(Lx',Ly','color',linecol); 
Daniel@0: else 
Daniel@0:   h = line(Lx',Ly',Lz','color',linecol); 
Daniel@0:   if ~washold, view(3); end
Daniel@0:   rotate3d on
Daniel@0: end
Daniel@0: 
Daniel@0: % plot the nodes
Daniel@0: hold on
Daniel@0: switch Colortype, 
Daniel@0:  case 'none', % nill
Daniel@0:  case 'colorspec', 
Daniel@0:   if codim == 1, plot(Coord,height,Color); 
Daniel@0:   else plot3(Coord(:,1), Coord(:,2), height, Color); 
Daniel@0:   end
Daniel@0:  case 'given', 
Daniel@0:   som_grid('rect',[nd+nc 1],'line','none','Coord',[Coord, height],...
Daniel@0: 	   'Markersize',10,'Markercolor',Color);
Daniel@0: end
Daniel@0: if ~washold, hold off, end
Daniel@0: 
Daniel@0: return;
Daniel@0: 
Daniel@0: 
Daniel@0: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Daniel@0: %% subfunctions
Daniel@0: 
Daniel@0: function depth = nodedepth(Z)
Daniel@0: 
Daniel@0:   nd = size(Z,1)+1; 
Daniel@0:   nc = size(Z,1);  
Daniel@0:   depth = zeros(nd+nc,1); 
Daniel@0:   ch = nc+nd-1; 
Daniel@0:   while any(ch), 
Daniel@0:     c  = ch(1); ch = ch(2:end);
Daniel@0:     if c>nd & isfinite(Z(c-nd,3)), 
Daniel@0:       chc = Z(c-nd,1:2); 
Daniel@0:       depth(chc) = depth(c) + 1; 
Daniel@0:       ch = [ch, chc]; 
Daniel@0:     end
Daniel@0:   end
Daniel@0:   return;
Daniel@0: 
Daniel@0: function inds = leafnodes(Z,i,nd)
Daniel@0: 
Daniel@0:   inds = []; 
Daniel@0:   ch = i; 
Daniel@0:   while any(ch), 
Daniel@0:     c  = ch(1); ch = ch(2:end);
Daniel@0:     if c>nd & isfinite(Z(c-nd,3)), ch = [ch, Z(c-nd,1:2)]; end
Daniel@0:     if c<=nd, inds(end+1) = c; end 
Daniel@0:   end
Daniel@0:   return;
Daniel@0: 
Daniel@0: function order = leavesorder(Z)
Daniel@0: 
Daniel@0:   nd = size(Z,1)+1;
Daniel@0:   order = 2*nd-1; 
Daniel@0:   nonleaves = 1; 
Daniel@0:   while any(nonleaves), 
Daniel@0:     j = nonleaves(1); 
Daniel@0:     ch = Z(order(j)-nd,1:2);
Daniel@0:     if j==1, oleft = []; else oleft = order(1:(j-1)); end
Daniel@0:     if j==length(order), oright = []; else oright = order((j+1):length(order)); end
Daniel@0:     order = [oleft, ch, oright];
Daniel@0:     nonleaves = find(order>nd); 
Daniel@0:   end
Daniel@0:   return; 
Daniel@0: 
Daniel@0: 
Daniel@0: