clc;clear all;close all;%初始化
dataSize=13;
rand('state',1);
K=1;
dataFrame=rand(dataSize,2).*0.2;
% plot(dataFrame(:,1)',dataFrame(:,2),'x');
CATEGORY = zeros(dataSize,5);%单个站点状态描述矩阵（4个特征）
categoryId = [1:dataSize]';%有dataSize行
categorySiteMode = rand(dataSize,1)>0.5;%蝴蝶是1，star是0，比例是0.5
categorySiteStatus = zeros(dataSize,1);%是主站还是子站 全零空阵
categoryIfConnect = zeros(dataSize,1);%主站（1）还是子站（0）。。。4
categoryCLASS=zeros(dataSize,1);%所属类别  初始化全零
categoryHS = -1*ones(dataSize,1);
[Id,SiteMode,Class,HorS,Layer...%
    ] = deal(1,2,3,4,5);
CATEGORY(:,Id) = categoryId;%序列号。。。。。。。。。。。。。。。1
CATEGORY(:,SiteMode) = categorySiteMode;%蝴蝶（1） star（0）。。。。2
CATEGORY(:,Class) = categoryCLASS;%分类后所属编号。。。。。。。。。3
CATEGORY(:,HorS) = categoryIfConnect;%主站（1）还是子站（0）。。。4
CATEGORY(:,Layer) = categoryHS;%主站（1）还是子站（0）。。。4
%[序列 蝴蝶 类别 主站]

Output = zeros(dataSize,dataSize);%连接关系网络 1000*1000 

%%
tic
[idx ,C] = kmeans(dataFrame,K);%使用聚类
countClass=zeros(K,1);
CATEGORY(:,Class)=idx';%更新类别属性的列CATEGORY(:,Class)
%%计算每一类的个数填充矩阵countClass
for iii=1:K%数出每一类有几个基站
countClass(iii)=sum(idx==iii);
end
%%
% for kk=1:K
% plot(dataFrame(idx==kk,1),dataFrame(idx==kk,2),'.','MarkerSize',12);
% hold on;
% end
% plot(C(:,1),C(:,2),'kx',...
%     'MarkerSize',12,'LineWidth',3);
% grid on;title '聚类分布图';xlabel('经度/°');ylabel('纬度/°');
%%
 DISCentroidBetweenEach = zeros(length(C),length(dataFrame));%每一个
for i = 1:length(C)
    for j=1:length(dataFrame)
        if CATEGORY(j,Class)==i;
      DISCentroidBetweenEach(i,j)=distance(C(i,1),C(i,2),dataFrame(j,1),dataFrame(j,2));%注意这里用的是聚类中心之间的距离不是主站
        else
            DISCentroidBetweenEach (i,j)=NaN;
        end
    end
end
%%
CentroiIndex=zeros(K,1);
for i=1:K
%     提取每一类中储存着聚类中心坐标  与 其余各个点坐标（包括自己。。自己跟自己肯定最近啊哈哈哈哈）距离的 行矩阵
    a=DISCentroidBetweenEach(i,:);
%     找出其中最小的一个 提取下标，这个就是要的主站身份ID
    [bB iI]=sort(a);
%     把身份ID储存到  CentroiIndex中  
    CentroiIndex(i)=iI(1);
end
%%
% 设定距离阈值
HH=999;% 主站到主站50
HS=999;% 主站到基站20
SS=999;% 基站到基站10

%%
k=1;
Kslice=CATEGORY(find(CATEGORY(:,Class)==k),:);% Kslice有用的是第一列的ID切片
 fromH=CentroiIndex(k);
 toS= Kslice(:,1);
 disFromHtoS=zeros(1,length(toS));
 for F=1:length(toS)
     disFromHtoS(F) = disFromTo(toS(F),CentroiIndex(k),dataFrame );
 end
 [HSdis HsID_temp]=sort(disFromHtoS,'descend');
 temp_slice=Kslice(:,1);
 HsID = temp_slice(HsID_temp);%这个是直接能够灌入距离计算的排序后原始ID  注意，最后一个就是主站自己  验证完毕
for cn=1:8
F= HsID(cn);
[CATEGORY,Output] = connectSite(F, CentroiIndex(k),Output,CATEGORY,1,1);
end

% 企图连接剩下的四个点
box=HsID(9:12);%连接第二层
initSumDIs=0;
Final=zeros(1,4)+1;
for i=1:4
initSumDIs=initSumDIs+(disFromTo(box(1),HsID(4+i),dataFrame ));
end
Rt=[];Ri=[];
%%
SearchCount=0;
[O1 O2 O3 O4]=deal(0);
initO=[O1 O2 O3 O4]
sr=[];
for O1=1:8
    for O2=1:8
             for O3=1:8   
                for O4=1:8%%
                    if O4~=O3&O4~=O2&O4~=O1&O3~=O2&O3~=O1&O2~=O1

currentO=[O1 O2 O3 O4];
for S1=1:4
    for S2=1:4
        
             for S3=1:4
                 
                for S4=1:4
                   

                    if S4~=S3&S4~=S2&S4~=S1&S3~=S2&S3~=S1&S2~=S1
    tempSum=(disFromTo(box(S1),HsID(O1),dataFrame) +disFromTo(box(S2),HsID(O2),dataFrame)+...
        disFromTo(box(S3),HsID(O3),dataFrame)+disFromTo(box(S4),HsID(O4),dataFrame));
    Rt=[Rt tempSum ];
    Ri=[Ri initSumDIs];
    SNow=[S1 S2 S3 S4];
    
    SearchCount=SearchCount+1;
    sr=[sr SearchCount];
    if SearchCount>10000
        break;
    end
                    if (tempSum<initSumDIs)
                    Final=[S1 S2 S3 S4];
                    initSumDIs=tempSum;
                    initO=currentO;
                    SearchCount=0;
                    else
                        continue;
                    end
                    end
                
                end
             end
        end         
    end
end    
%%
end
                
                
             end
        end         
    end
   

%%
for ii=1:4
    [CATEGORY,Output] = connectSite(box(Final(ii)) ,HsID(initO(ii)),Output,CATEGORY,1,1);
end
%%
toc
% G=graph(Output);
% subplot(1,2,1)
% plot(G)
% subplot(1,2,2)
 plot(Rt,'LineWidth',0.05);hold on ;plot(Ri,'LineWidth',2);
legend('尝试','最优');
xlabel('尝试次数');
ylabel('距离代价');
%%
%REF
% hold on 
% scatter(dataFrame(4,1),dataFrame(4,2),'*')

function [CATEGORY,Output] = connectSite(from , to,Output,CATEGORY,Contyp,LayerN)
%输入连接矩阵关系矩阵CONNInput，触发站点编号from，目的站点编号to ，大目录CATEGORY，连接类型HH（2）还是Hs（1）、SS（1）
% 层属性更新变量LayerN
%   Detailed explanation goes here
Output(from,to)=Contyp;
Output(to,from)=Contyp;
CATEGORY(from,5)=LayerN;
CATEGORY(to,5)=LayerN;

end

function [ DIS ] = computeMutualDis(dataFrame,La,Lo)
%要求输入数据框架本体dataFrame，与La,Lo
%  dataFrame用来计算尺寸 La,Lo用来计算距离的实际经纬度
DIS = zeros(length(dataFrame),length(dataFrame));%s
Radius = 6378;
az=0;
[h l] = size(dataFrame);%分别获取数据框架的行（h）列（l）值
for i=1:h
    for j=1:h
        %距离计算arclen是曲线距离,az是直线距离
    [arclen,az] = distance(La(i),Lo(i),La(j),Lo(j),Radius);
    DIS(i,j) = arclen;%更改这个可以实现距离替换
    
    end
end

end

function [ DIS ] = computeMutualDis(dataFrame,La,Lo)
%要求输入数据框架本体dataFrame，与La,Lo
%  dataFrame用来计算尺寸 La,Lo用来计算距离的实际经纬度
DIS = zeros(length(dataFrame),length(dataFrame));%s
Radius = 6378;
az=0;
[h l] = size(dataFrame);%分别获取数据框架的行（h）列（l）值
for i=1:h
    for j=1:h
        %距离计算arclen是曲线距离,az是直线距离
    [arclen,az] = distance(La(i),Lo(i),La(j),Lo(j),Radius);
    DIS(i,j) = arclen;%更改这个可以实现距离替换
    
    end
end

end