ring.m

电网规划中搜索环路的程序,通过给定的网络拓扑结构,判定该网络是否连通,如果连通,判定是否有回路,如果有回路,返回组成改回路的线路集合.

function R=Ring(T)
%算法：
%如果存在回路，则必存在一个子图，是一个环路。环路中所有顶点的度>=2。
%第一步：删除所有度<=1的顶点及相关的边，并将另外与这些边相关的其它顶点的度减一。
%第二步：将度数变为1的顶点排入队列，并从该队列中取出一个顶点重复步骤一。
%        如果最后还有未删除顶点，则存在环，否则没有环。
%        T=[1 2 1 2;4 6 2 9;2 5 3 6;3 6 4 8;3 4 5 4];
V=T;
R=[];
P=[];

n=length(V(:,1));
BW=0*ones(n);
  for i=1:n
    x=V(i,1);y=V(i,2);
    BW(x,y)=1;
    x=V(i,2);y=V(i,1);
    BW(x,y)=1;
end; 
wi=liantong(BW);
if wi==0,R=1;return;end;


r1=V(:,1);r2=V(:,2);
m1=max(r1);m2=max(r2);
if m1>m2, m=m1;end;
if m2>m1, m=m2;end;
for i=1:m
   P(i,1)=i; 
   k1=length(find(V(:,1)==i));k2=length(find(V(:,2)==i));k=k1+k2;
   P(i,2)=k;
end;                                                                       %创建一个P矩阵存储顶点的信息

[a,b]=find(P<=1);                                                          %P是顶点的集合
L=[a,b];k=length(L(:,1));                                                  %L是P当中度小于1的点的坐标
[wa,wb]=find(P(:,2)==0);
w=[wa,wb];
while(rank(w)==0)
    while (k>0)
        t=length(P(:,1));i=1;
        h=[];
        for j=1:t  
            if P(j,2)<=1 h(i)=P(j,1);i=i+1;end;
        end;
        k=length(h);                            %找到P中顶点的度小于等于1的顶点
        for i=1:k
            d=h(i);                             %d中储存真实的顶点
            j=1;
            while(j<=length(V(:,1)))
              if V(j,1)==d 
                  g=V(j,2);V(j,:)=[];if rank(V)==0,break;end;j=j-1;
                  if j==0, j=1;end;
              end;
              if V(j,2)==d 
                  g=V(j,1);V(j,:)=[];if rank(V)==0,break;end;j=j-1;end;
              j=j+1;
            end;                                %搜索V中是否含有
            n=1;
            while(n<=length(P(:,1)))
               if P(n,1)==g P(n,2)=P(n,2)-1;end;
               if P(n,1)==d P(n,:)=[];n=n-1;end;
               n=n+1;
            end;   
        end; 
%对于度小于等于1的顶点,删去V中含有它的支路和P中的这些顶点,并找到与之相连的节点,将这些节点的度减1
    [a,b]=find(P<=1);                           
    L=[a,b];
    if rank(L)>0,k=length(L(:,1));end;
    if rank(L)==0,k=0;end;
%重新统计P中度小于1的顶点，如果还存在这样的节点，则继续循环
    end;
    break;
end;
% if k==0&&rank(P)~=0,R=2;end;  %有环
if k==0&&rank(P)~=0,R=V;end;  %有一个环，V中剩下的支路即为构成环路的支路集合，放入环路集合R
if rank(P)==0&&rank(V)==0,R=3;end;