1 function A = Aufgabe4(X, k)
   2 %Aufgabe4 - compute and plot k-nn graph, histogram of node degrees and edge lengths.
   3 %
   4 %usage
   5 %  A = Aufgabe4(X, k)
   6 %
   7 %input
   8 %  X : (2,n)-matrix of column vectors.
   9 %  k : Number of nearest neighbours. 
  10 %
  11 %output
  12 %  A : (n,n)-adjacency matrix, where A_ij == 1 iff vertices i and j are connected.
  13 %
  14 %description
  15 %  Aufgabe4 computes the k-nearest-neighbour graph on the columns in X and plots
  16 %  the histogram of node degrees and edge lengths.
  17 %
  18 %author
  19 %  buenau@cs.tu-berlin.de
  20 
  21 [d, n] = size(X);
  22 
  23 % Compute squared distance matrix.
  24 xx = sum( X .^ 2, 1);
  25 D = repmat(xx, [n 1]) -2*X'*X + repmat(xx', [1 n]);
  26 
  27 % Build adjacency matrix. 
  28 [foo, ii] = sort(D);
  29 A = zeros(n, n);
  30 for i=1:n
  31   A(i,ii(2:k+1, i)) = 1;
  32 end
  33 A = double(A | A');
  34 
  35 % Plot graph.
  36 subplot(3, 1, 1);
  37 plot(X(1,:), X(2,:), 'bo');
  38 hold on;
  39 At = triu(A);
  40 [ii, jj] = find(At);
  41 
  42 for i=1:length(ii)
  43   h = line( [ X(1,ii(i)) X(1,jj(i)) ], [ X(2,ii(i)) X(2,jj(i)) ] );
  44   set(h, 'LineStyle', '--');
  45 end
  46 title('Graph');
  47 
  48 % Histogram of node degrees.
  49 subplot(3, 1, 2);
  50 hist(sum(A, 1));
  51 title('Histogram of degrees');
  52 
  53 % Histogram of edge lengths.
  54 subplot(3, 1, 3);
  55 hist(D(find(At)));
  56 title('Histogram of edge lengths');