function A = Aufgabe4(X, k)
%Aufgabe4 - compute and plot k-nn graph, histogram of node degrees and edge lengths.
%
%usage
%  A = Aufgabe4(X, k)
%
%input
%  X : (2,n)-matrix of column vectors.
%  k : Number of nearest neighbours. 
%
%output
%  A : (n,n)-adjacency matrix, where A_ij == 1 iff vertices i and j are connected.
%
%description
%  Aufgabe4 computes the k-nearest-neighbour graph on the columns in X and plots
%  the histogram of node degrees and edge lengths.
%
%author
%  buenau@cs.tu-berlin.de

[d, n] = size(X);

% Compute squared distance matrix.
xx = sum( X .^ 2, 1);
D = repmat(xx, [n 1]) -2*X'*X + repmat(xx', [1 n]);

% Build adjacency matrix. 
[foo, ii] = sort(D);
A = zeros(n, n);
for i=1:n
  A(i,ii(2:k+1, i)) = 1;
end
A = double(A | A');

% Plot graph.
subplot(3, 1, 1);
plot(X(1,:), X(2,:), 'bo');
hold on;
At = triu(A);
[ii, jj] = find(At);

for i=1:length(ii)
  h = line( [ X(1,ii(i)) X(1,jj(i)) ], [ X(2,ii(i)) X(2,jj(i)) ] );
  set(h, 'LineStyle', '--');
end
title('Graph');

% Histogram of node degrees.
subplot(3, 1, 2);
hist(sum(A, 1));
title('Histogram of degrees');

% Histogram of edge lengths.
subplot(3, 1, 3);
hist(D(find(At)));
title('Histogram of edge lengths');
















