Daniel@0: function draw_dot(adj,varargin);
Daniel@0: %DRAW_DOT   Draw a graph.
Daniel@0: % DRAW_DOT(ADJ) plots the graph ADJ in the current figure window, using 
Daniel@0: % 'neato' to optimize the layout.
Daniel@0: %
Daniel@0: % Optional arguments can be passed as name/value pairs: [default]
Daniel@0: %
Daniel@0: % 'isbox'     - a vector specifying which nodes should be boxed [0]
Daniel@0: % 'rotate'    - rotate the graph so that nodes are vertically aligned [1]
Daniel@0: % 'tolerance' - alignment tolerance for 'rotate' [0.001]
Daniel@0: % 'start'     - a random seed (to select different solutions)
Daniel@0: % 'options'   - a string of command-line options for 'neato' ['']
Daniel@0: % All of the optional arguments to graph_to_dot are also supported, such as
Daniel@0: % 'node_label'.
Daniel@0: %
Daniel@0: % See also GRAPH_TO_DOT.
Daniel@0: %
Daniel@0: % Example:
Daniel@0: % size=15; Adj = rand(size) > .8;
Daniel@0: % Adj2 = triu(Adj,1)+ triu(Adj,1)' + diag(zeros(size,1));
Daniel@0: % draw_dot(Adj2)
Daniel@0: 
Daniel@0: % Original: Leon Peshkin  
Daniel@0: % Modified by Tom Minka
Daniel@0: 
Daniel@0: % minka
Daniel@0: N = size(adj,1);
Daniel@0: unique_labels = cellstr(num2str((1:N)','%-1d'));
Daniel@0: labels = unique_labels;
Daniel@0: isbox = zeros(N,1);
Daniel@0: rotate_flag = 1;
Daniel@0: tolerance = 0.001;
Daniel@0: options = '';
Daniel@0: for i = 1:2:length(varargin)
Daniel@0:   switch varargin{i}
Daniel@0:     case 'node_label', labels = varargin{i+1}; 
Daniel@0:       % replace with unique labels
Daniel@0:       varargin{i+1} = unique_labels;
Daniel@0:     case 'isbox', isbox = varargin{i+1};
Daniel@0:     case 'rotate', rotate_flag = varargin{i+1};
Daniel@0:     case 'tolerance', tolerance = varargin{i+1};
Daniel@0:     case 'start', start = varargin{i+1}; 
Daniel@0:       options = [options ' -Gstart=' num2str(start)];
Daniel@0:     case 'options', options = [options ' ' varargin{i+1}];
Daniel@0:   end
Daniel@0: end
Daniel@0: 
Daniel@0: if ispc, shell = 'dos'; else, shell = 'unix'; end  %  Which OS ?
Daniel@0: 
Daniel@0: cmdline = strcat(shell,'(''neato -V'')');
Daniel@0: status = eval(cmdline);
Daniel@0: %[status, result] = dos('neato -V');  % request version to check NEATO
Daniel@0: if status == 1,  fprintf('Complaining \n'); exit, end
Daniel@0: 
Daniel@0: tmpDOTfile = '_GtDout.dot';            % to be platform independant no use of directories
Daniel@0: tmpLAYOUT  = '_LAYout.dot'; 
Daniel@0: graph_to_dot(adj > 0, 'filename', tmpDOTfile, 'node_label', unique_labels, varargin{:});  % save in file
Daniel@0: 
Daniel@0: cmdline = strcat([shell '(''neato -Tdot ' tmpDOTfile options ' -o ' tmpLAYOUT ''')']); % preserve trailing spaces 
Daniel@0: status = eval(cmdline);         %  get NEATO todo layout
Daniel@0: 
Daniel@0: [adj, permuted_labels, x, y] = dot_to_graph(tmpLAYOUT);  %  load layout 
Daniel@0: delete(tmpLAYOUT); delete(tmpDOTfile);     % clean up temporary files
Daniel@0: 
Daniel@0: % permute the original arguments to match permuted_labels.
Daniel@0: order = [];
Daniel@0: for i = 1:length(permuted_labels)
Daniel@0:   j = strmatch(permuted_labels{i},unique_labels,'exact');
Daniel@0:   order(i) = j(1);
Daniel@0: end
Daniel@0: labels = labels(order);
Daniel@0: isbox = isbox(order);
Daniel@0: if rotate_flag
Daniel@0:   [x,y] = best_rotation(x,y,tolerance);
Daniel@0: end
Daniel@0: 
Daniel@0: figure(1); clf; axis square      %  now plot 
Daniel@0: [x, y, h] = draw_graph(adj>0, labels, isbox, x, y, varargin{:});
Daniel@0: 
Daniel@0: 
Daniel@0: function [x,y] = best_rotation(x,y,h)
Daniel@0: % Rotate the points to maximize the horizontal and vertical alignment.
Daniel@0: % Written by Tom Minka.
Daniel@0: 
Daniel@0: xm = mean(x);
Daniel@0: ym = mean(y);
Daniel@0: xr = max(x)-min(x);
Daniel@0: yr = max(y)-min(y);
Daniel@0: x = (x-xm)/xr;
Daniel@0: y = (y-ym)/yr;
Daniel@0: 
Daniel@0: xy = [x(:) y(:)];
Daniel@0: if 1
Daniel@0:   angle = fminbnd(@rotation_cost,-pi/4,pi/4,[],xy,h);
Daniel@0: else
Daniel@0:   angles = linspace(-pi/4,pi/4,40);
Daniel@0:   e = [];
Daniel@0:   for i = 1:length(angles)
Daniel@0:     e(i) = rotation_cost(angles(i),xy,h);
Daniel@0:   end
Daniel@0:   %figure(2)
Daniel@0:   %plot(angles*180/pi,e)
Daniel@0:   angle = angles(argmin(e));
Daniel@0: end
Daniel@0: %angle*180/pi
Daniel@0: c = cos(angle); s = sin(angle);
Daniel@0: xy = xy*[c s; -s c];
Daniel@0: 
Daniel@0: x = xy(:,1)*xr+xm;
Daniel@0: y = xy(:,2)*yr+ym;
Daniel@0: 
Daniel@0: 
Daniel@0: function e = rotation_cost(angle,xy,h)
Daniel@0: % xy is 2-column matrix.
Daniel@0: % e is small if many x's and y's are aligned.
Daniel@0: 
Daniel@0: c = cos(angle); s = sin(angle);
Daniel@0: xy = xy*[c s; -s c];
Daniel@0: dx = sqdist(xy(:,1)',xy(:,1)');
Daniel@0: dy = sqdist(xy(:,2)',xy(:,2)');
Daniel@0: dx = setdiag(dx,Inf);
Daniel@0: dy = setdiag(dy,Inf);
Daniel@0: e = sum(exp(-dx(:)/h))+sum(exp(-dy(:)/h));
Daniel@0: e = -e;