[Octave-cvsupdate] SF.net SVN: octave:[11050] trunk/octave-forge/main/statistics/inst/ dendogram.m

[<jpi...@us...>]

Revision: 11050
          http://octave.svn.sourceforge.net/octave/?rev=11050&view=rev
Author:   jpicarbajal
Date:     2012-09-18 22:31:39 +0000 (Tue, 18 Sep 2012)
Log Message:
-----------
statistics:fixing dendogram function. Oder of leafs implemented.

Modified Paths:
--------------
    trunk/octave-forge/main/statistics/inst/dendogram.m

Modified: trunk/octave-forge/main/statistics/inst/dendogram.m
===================================================================
--- trunk/octave-forge/main/statistics/inst/dendogram.m	2012-09-18 21:35:42 UTC (rev 11049)
+++ trunk/octave-forge/main/statistics/inst/dendogram.m	2012-09-18 22:31:39 UTC (rev 11050)
@@ -17,14 +17,12 @@
 %% @deftypefn {Function File} {@var{h} = } dendogram (@var{tree})
 %% Plots a dendogram using the output of function @command{linkage}.
 %%
-%% TODO: This function needs your help to be finished! Leafs must be ordered to
-%%       prevent corssing of edges.
+%% TODO: Return handle to lines to set properties
+%% TODO: Rescale the plot automatically base don data.
+%%
 %% @seealso{linkage}
 %% @end deftypefn
 
-## TODO
-# Order leafs nodes to avoid edge crossing.
-
 function h = dendogram (tree)
 
   [m d] = size (tree);
@@ -38,49 +36,27 @@
   % Vector with the horizontal and vertical position of each cluster
   p = zeros (nc,2);
 
-##### This is an ugly hack and is a partial solution. If you know how to oder
-##### the leafs do it. Please do not copy from dendogram.m of Mathworks!
+  labels = zeros (n,1);
 
-  %% Order the leafs
-  % find which clusters contain th eleafs
-  tf = ismember (tree(:,1:2),1:n);
-  [idx_i,idx_j] = find (tf);
-  ind0 = find(tf(:));
-
-  % Assign a position between 1:n to the leafs according to clustering
-  % I am trying to avoid crossings. Better way? sure!.
-  i = 1;
-  j = 0;
-  while j < n
-
-    % If the current leaf hasn't a position assigned, assign one.
-    if p(tree(idx_i(i),idx_j(i)),1) == 0
-     j+=1;
-     p(tree(idx_i(i),idx_j(i)),1) = j;
+  %% Ordering by depth-first search
+  nodecount = 0;
+  nodes_to_visit = nc+1;
+  while !isempty(nodes_to_visit)
+    currentnode = nodes_to_visit(1);
+    nodes_to_visit(1) = [];
+    if currentnode > n
+      node = currentnode - n;
+      nodes_to_visit = [tree(node,[2 1]) nodes_to_visit];
     end
 
-    % Check if the current cluster has another leaf. If it has and the leaf
-    % doesn't have a position, assign one.
-    next = tree(idx_i(i),setdiff(1:2,idx_j(i)));
-    if next <= n && p(next,1) == 0
-      j+=1;
-      p(next,1) = j;
+    if currentnode <= n && p(currentnode,1) == 0
+      nodecount +=1;
+      p(currentnode,1) = nodecount;
+      labels(nodecount) = currentnode;
     end
 
-    % Find the id of the current cluster and check if any other cluster
-    % that will be merged with this one has a leaf.
-    c_id = idx_i(i) + n;
-    [idx,~] = find (tree(:,1:2)==c_id);
-    idx2 = find (tree(idx,1:2)<=n);
-    if ~isempty (idx2) && p(tree(idx,idx2),1) == 0
-      j+=1;
-      p(tree(idx,idx2),1) = j;
-    end
-    i+=1;
   end
 
-##### End of the hack
-
   % Compute the horizontal position, begin-end
   % and vertical position of all clusters.
   for i = 1:m
@@ -89,9 +65,7 @@
     x(i,1:2) = p(tree(i,1:2),1);
   end
 
-
-
-  clf
+  figure(gcf)
   % plot horizontal lines
   tmp = line (x', tree(:,[3 3])');
 
@@ -102,7 +76,7 @@
   end
 
   xticks = 1:n;
-  xl_txt = arrayfun (@num2str, tree(:,1:2)(ind0),"uniformoutput",false);
+  xl_txt = arrayfun (@num2str, labels,"uniformoutput",false);
   set (gca,"xticklabel",xl_txt,"xtick",xticks);
   axis ([0.5 n+0.5 0 max(tree(:,3))+0.1*min(tree(:,3))]);
 

This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.