%% MST model using PRIM's algorithm
% Initalization
clc; clear all; close all;

%% Data Generation

nSize = 100;

% data1 = floor(rand(100,3)*100);
% save data1.mat data1;

load data1.mat;

%% Distance Calculation

nn = zeros(nSize,nSize);

for i = 1:(nSize-1)
    tempdata1 = data1(i,:);
    
    for j = (i+1):nSize
        tempDistance = 0;
        tempdata2 = data1(j,:);
        
        tempDistance = sqrt((tempdata1(1,1)-tempdata2(1,1))^2+(tempdata1(1,2)-tempdata2(1,2))^2+(tempdata1(1,3)-tempdata2(1,3))^2);
        
        nn(i,j) = tempDistance;
        nn(j,i) = tempDistance;
        
    end
    
end

%% Prim's algorithm

v1 = zeros(1,nSize); v1(1,1) = 1;
v2 = ones(1,nSize); v2(1,1) = 0;

route = []; % MST
count = 0;

for l=1:nSize
    
    if (sum(v2) > 0)
        
        startSite = []; endSite=[];
        for i=1:nSize
            if(v1(1,i) ==1)
                startSite = [startSite; i];
            end
            
            if (v2(1,i)==1)
                endSite = [endSite; i];
            end                
        end
        
        [m1 n1] = size(startSite);
        [m2 n2] = size(endSite);
        
        candidate = [];
        
        for i=1:m1
            for j=1:m2
                candidate = [candidate; startSite(i,1) endSite(j,1) nn(startSite(i,1),endSite(j,1))];
            end
        end
        
        [minVal minIndex] = min(candidate(:,3));
        
        route = [route ; candidate(minIndex(1,1),1) candidate(minIndex(1,1),2)];
        
        v1(1,candidate(minIndex(1,1), 2)) = 1;
        v2(1,candidate(minIndex(1,1),2)) = 0;
        
    end
    
end

%% Plotting
[mmm nnn] = size(route);

figure(1);
hold on;
plot3(data1(:,1),data1(:,2), data1(:,3),'ro');
for i=1:mmm
    tempPlot = [];
    tempPlot = [data1(route(i,1),:); data1(route(i,2),:)];
    plot3(tempPlot(:,1),tempPlot(:,2), tempPlot(:,3),'b-');
end
xlabel('<X axis>');ylabel('<Z axis>');zlabel('<Y axis>');
title('<Minimum Spanning Tree>');
hold off;
grid on;




