拓扑-网络连通性算法.doc

网络连通性算法网络定义节点与支路的集合，该集合中的节点与支路的连接关系可通过一节点-节点关联矩阵A充分表达：A=aijnn i,j=1,2,n式中：aij=n网络节点数连通性算法理论算法：称矩阵A为网络一级连通矩阵，A2为二级连通矩阵，An-1为n-1级连通矩阵。A2=AA=a2ijnn i,j=1,2,n式中：a2ij=k=1,2,n，ki,jAn-1= =an-1ijnn i,j=1,2,n式中：an-1ij=矩阵An-1的每一线性无关的行或列中“1”元素对应的节点均处于同一连通子集中。实际算法：若矩阵A第i（i=1,2,n）行元素与第j（j=i+1,i+2,n）行元素中第k列元素aik和ajk同为“1”，则第j行中的其它“1”元素均填入第i行的相应列中。结果矩阵A第i行中所有“1”元素对应的节点处于同一连通子集中。数据定义Nc元件数Nd节点数NOD（Nc,3）每个元件的节点编号i、j、kKND（Nc）每个元件的种类（断路器、隔离开关、母线、线路、变压器）CNT（Nc）每个开关元件的分、合状态（逻辑型，例如：合为“真”，分为“假”）NDS0（Nd）每个节点初始所在连通子集编号NDS（Nd）每个节点所在连通子集编号NCT0（Nc）每个元件初始所在连通子集编号NCT（Nc）每个元件所在连通子集编号NST（Ns，3）每个原始连通子集内子集号，子集内节点数，子集内首位节点号Ns最大可能连通子集数RA（Nd）节点关联矩阵第i行，逻辑型RB（Nd）节点关联矩阵第j行，逻辑型检验第k0个连通子集的连通性子程序CNTS(k0)初始化IND=NST(k0,3) 取第k0个连通子集的首位节点号N=0连通子集数置0LOOP1 l=1，Ndl从1至Nd循环IF (NDS0（l）=k0)， NDS（l）=0第k0个连通子集的节点l的子集号临时置0END LOOP1连通性检验大循环10NSUM=1节点关联矩阵“真”元素计数置为1LOOP1 l=1，Ndl从1至Nd循环 RA(l)=FALSE第k0个连通子集中第IND行第l列元素置为“假”END LOOP1RA(IND)=TRUE节点关联矩阵第IND行对角元素置1M=1节点关联矩阵第IND行 “真”元素计数置为1形成节点关联矩阵的第IND行RALOOP1 l=1,Ncl从1至Nc循环 IF(NCT0(l)=k0)，THEN如果元件l属于初始连通子集k0，则 IF(KND(l)开关or (KND(l)=开关and CNT(l)=合)，THEN I=NOD(l,1) J=NOD(l,2) K=NOD(l,3)取元件l的各端节点号 IF(I=IND)，THEN如果节点号I等于节点号IND，则 IF(J0 and JI)，THEN如果节点号J不等于0和I，则RA(J)=TRUE关联矩阵第IND行第J列元素置为“真”M=M+1关联矩阵第IND行“真”元素计数+1 END IF IF(K0 and KI and KJ)，THEN如果节点号K不等于0和I和J，则RA(K)=TRUE关联矩阵第IND行第K列元素置为“真”M=M+1关联矩阵第IND行“真”元素计数+1 END IF END IF IF(J=IND)，THEN如果节点号J等于节点号IND，则 IF(I0 and IJ)，THEN如果节点号I不等于0和I，则RA(I)=TRUE关联矩阵第IND行第I列元素置为“真”M=M+1关联矩阵第IND行“真”元素计数+1 END IF IF(K0 and KI and KJ)，THEN如果节点号K不等于0和I和J，则RA(K)=TRUE关联矩阵第IND行第K列元素置为“真”M=M+1关联矩阵第IND行“真”元素计数+1 END IF END IF IF(K=IND)，THEN如果节点号K等于节点号IND，则 IF(I0 and IK)，THEN如果节点号I不等于0和K，则RA(I)=TRUE关联矩阵第IND行第I列元素置为“真”M=M+1关联矩阵第IND行“真”元素计数+1 END IF IF(J0 and JI and JK)，THEN如果节点号J不等于0和I和K，则RA(J)=TRUE关联矩阵第IND行第J列元素置为“真”M=M+1关联矩阵第IND行“真”元素计数+1 END IF END IF END IF END IFEND LOOP1将节点连通矩阵第IND+1Nd行与第IND行比较，寻找包含节点IND的连通子集M子集k0节点数且有新“真”元素出现时，循环LOOP1 WHILE(MNST(k0,2) and MNSUM) 当节点ld属于连通子集k0，且关联矩阵第IND行第ld列元素为“假”，且未找到节点ld新连通子集号时，循环 NSUM=M LOOP2 ld=IND+1，Ndld自IND+1至Nd循环 IF (NDS0(ld)=k0 and RA(ld)=FALSE and NDS(ld)=0)，THEN当 LOOP3 l=1，Ndl自1至nd循环 RB(l)=FALSE关联矩阵第ld行第l列元素置为“假” END LOOP3 RB(ld)=TRUE节点关联矩阵第ld行对角元素置1形成节点关联矩阵的第ld行RB LOOP3 l=1，Ncl自1至Nc循环 IF(NCT0(l)=k0)，THEN如果元件l属于原连通子集k0，则IF(KND(l)开关or (KND(l)=开关and CNT(l)=合)，THEN I=NOD(l,1) J=NOD(l,2) K=NOD(l,3)取元件l的各端节点号IF(I=ld)，THEN如果节点号I等于节点号ld，则 IF(J0 and JI)，THEN如果节点号J不等于0和I，则 RB(J)=TRUE关联矩阵第ld行第J列元素置为“真” END IF IF(K0 and KI and KJ)，THEN如果节点号K不等于0和I和J，则 RB(K)=TRUE关联矩阵第ld行第K列元素置为“真” END IFEND IFIF(J=ld)，THEN如果节点号J等于节点号ld，则 IF(I0 and IJ)，THEN如果节点号I不等于0和J，则 RB(I)=TRUE关联矩阵第ld行第I列元素置为“真” END IF IF(K0 and KI and KJ)，THEN如果节点号K不等于0和I和J，则 RB(K)=TRUE关联矩阵第ld行第K列元素置为“真” END IFEND IFIF(K=ld)，THEN如果节点号K等于节点号ld，则 IF(I0 and IK)，THEN如果节点号I不等于0和K，则 RB(I)=TRUE关联矩阵第ld行第I列元素置为“真” END IF IF(J0 and JI and JK)，THEN如果节点号K不等于0和I和J，则 RB(J)=TRUE关联矩阵第ld行第J列元素置为“真” END IFEND IF END IF END IFEND LOOP3如果节点l属于原连通子集k0，且关联矩阵第IND行第l列元素与第ld行第l列元素同为“真”，则LOOP3 l=1，Ndl自1至Nd循环 IF(NDS0(l)=k0 and RA(l) and RB(l)，THEN LOOP4 j=1，Ndjl自1至Nd循环如果第IND行第j列元素为“假”，且ld行第j列元素为“真”，则IF(RA(j)=FALSE and RB(j)=TRUE)，THEN RA(j)=TRUE行IND列j置为“真” M=M+1关联矩阵第IND行“真”元素计数+1END IF END LOOP4 GOTO 20跳出循环3 END LOOP320 END LOOP2END LOOP1N=N+1连通子集计数+1IF(M=NST(k0,2)，THEN如果M=原连通子集k0中节点总数，则 LOOP1 l=1,Ndl自1至Nd循环 IF(NDS0(l)=k0)，NDS(l)=1连通子集k0中节点l的子集号置为1 END LOOP1（子集k0全连通）ELSE否则 LOOP1 l=1,Ndl自1至Nd循环 IF(RA(l)=TRUE)，NDS(l)=N如果RA(l)为“真”，连通子集k0中节 END LOOP1点l的子集号置为N LOOP1 l=IND+1，Ndl自IND+1至Nd循环 IF(NDSO(l)=k0 and NDS(l)=0) THEN如果节点l属原子集k0且无新子集号，则IND=l将寻找下一连通子集的起始节点号置为lGOTO 10返回10，自节点l开始寻找下一连通子集 END IF END LOOP1END IFNST(k0,1)=N将原始连通子集k0内的连通子集数置为NLOOP1 l=1，Ncl自1至Nc循环 IF(NCT0(l)=k0)，THEN如果元件l属于初始连通子集k0，则 IF(KND(l)开关or (KND(l)=开关and CNT(l)=合)，THEN I=NOD(l,1)I=元件l的第一个节点号 IF(I=0)，THEN如果I为0，则 I=NOD(l,2)I=元件l的第二个节点号