
%% Load a graph
load four_clusters

%% Show the graph
gplot(A,xy,'.-'); axis off;

%% Construct the Laplacian
L = laplacian(A);

%% use CVX for the maxcut problem
% This assumes you've already run cvx_setup, or have it on your path
n = size(A,1);
cvx_begin
  variable Y(n,n) symmetric;
  maximize trace(Y*L);
  subject to
    Y == semidefinite(n);
    diag(Y) == ones(n,1);
cvx_end

%% Done!  Remarkably fast too.
cvx_optval/4

%% That shows there should be a pretty good maxcut.  Let's find X
[V D] = eig(Y);
%% Look at the rank
d = diag(D);
plot(diag(D))
%% This matrix has rank that's effectively 5
r = 5;
X = V(:,end-(r-1):end)*diag(sqrt(d(end-(r-1):end)));
norm(X*X' - Y)
%% Are the points on the sphere?
X(1,:)*X(1,:)'
%% Let's look at the first two dimensions of the data
plot(X(:,end),X(:,end-1),'.');
%% They aren't on the sphere!
% That's because the solution is on the sphere of 5 dimensions, not 2!
% But I hope you can see that there are clear "groups" of elements.
z = randn(5,1);
x = sign(X*z)

%% What's the cut?
x'*L*x/4

%% Let's see the set of nodes
gplot(A,xy,'.-'); axis off; hold on; plot(xy(x>0,1),xy(x>0,2),'r.'); hold off;
