% Created 2012-April-2
% Written by Fu Lin
% A random graph example for noise-corrupted leader selection problem 

% Generate 100 nodes randomly distributed in a square of Length x Length units
n = 100;

% load the position data
load position.mat
Length = 1;

% Or generate a new set of position data
% position = Length*rand(n,2);

% radius that determines the neighbors of nodes
r = Length/5;

% draw neighbors and compute the incidence matrix of neighboring nodes
[Eg,idx] = neighbors(n,position,r);

% form the graph Laplacian
L = Eg*Eg';

% kappa is taken as the diagonal of L
kappa = diag(L);

%% Start solving the leader selection problem

kval = 1:1:40;

% pre-allocate memory for data collection
Jlow = zeros(size(kval));
Jup = zeros(size(kval));
LSgreed = zeros(n,length(kval));

for i = 1:length(kval)
    
    Nl = kval(i);
    flag = 1; % for noise-corrupted leader selection formulation
    [Jlow(i),Jup(i),LSgreed(:,i)] = leaders(L,Nl,kappa,flag);
       
end

%% degree-heuristics

[Jdeg,leader_idx_deg] = degree_noise_corrupted_leader(L,kappa,kval(end));

%% Plot results

figure,plot(kval,Jlow,'o-','MarkerSize',12,'LineWidth',2)
hold on
plot(kval,Jup,'ro-','MarkerSize',12,'LineWidth',2)
xlab = xlabel('N_l','interpreter', 'tex');
set(xlab, 'FontName', 'cmmi10', 'FontSize', 20)
hh = get(gcf,'CurrentAxes');
set(hh, 'FontName', 'cmr10', 'FontSize', 18) 
legend('lower bounds','upper bounds')
axis([0.99,kval(end),5,40])

figure,
plot(kval,Jup-Jlow,'dk-','MarkerSize',12,'LineWidth',2)

figure,
hold on;
plot(kval,Jup,'ro-','MarkerSize',12,'LineWidth',2)
plot(kval,Jdeg,'k^-','MarkerSize',12,'LineWidth',2)
xlab = xlabel('N_l','interpreter', 'tex');
set(xlab, 'FontName', 'cmmi10', 'FontSize', 20)
hh = get(gcf,'CurrentAxes');
set(hh, 'FontName', 'cmr10', 'FontSize', 18)    
legend('greedy algorithm','degree heuristics')

%% Plot location of leaders 

pos_leaders = position(LSgreed(:,5)==1,:);
drawleaders(position,idx,pos_leaders)

pos_leaders = position(LSgreed(:,40)==1,:);
drawleaders(position,idx,pos_leaders)

%% Plot location of leaders based on degree heuristics

pos_leaders_deg = position(leader_idx_deg(1:5),:);
drawleaders(position,idx,pos_leaders_deg)

pos_leaders_deg = position(leader_idx_deg(1:40),:);
drawleaders(position,idx,pos_leaders_deg)
