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

网络连通性算法
网络定义
节点与支路的集合，该集合中的节点与支路的连接关系可通过一节点-节点关联矩阵A充分表达：
A=[aij]n×n i,j=1,2,…,n
式中：aij=
n—网络节点数
连通性算法
理论算法：
称矩阵A为网络一级连通矩阵，A2为二级连通矩阵，…，An-1为n-1级连通矩阵。
A2=AA=[a2ij]n×n i,j=1,2,…,n
式中：a2ij=
k=1,2,…,n，k≠i,j
……
An-1= =[an-1ij]n×n 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、k
KND（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 连通子集数置0
LOOP1 l=1，Nd l从1至Nd循环
IF (NDS0（l）=k0)， NDS（l）=0 第k0个连通子集的节点l的子集号临时置0
END LOOP1
连通性检验大循环
10 NSUM=1 节点关联矩阵“真”元素计数置为1
LOOP1 l=1，Nd l从1至Nd循环
RA(l)=FALSE 第k0个连通子集中第IND行第l列元素置为“假”
END LOOP1
RA(IND)=TRUE 节点关联矩阵第IND行对角元素置1
M=1 节点关联矩阵第IND行 “真”元素计数置为1
形成节点关联矩阵的第IND行RA
LOOP1 l=1,Nc l从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(J≠0 and J≠I)，THEN 如果节点号J不等于0和I，则
RA(J)=TRUE 关联矩阵第IND行第J列元素置为“真”
M=M+1 关联矩阵第IND行“真”元素计数+1
END IF
IF(K≠0 and K≠I and K≠J)，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(I≠0 and I≠J)，THEN 如果节点号I不等于0和I，则
RA(I)=TRUE 关联矩阵第IND行第I列元素置为“真”
M=M+1 关联矩阵第IND行“真”元素计数+1
END IF
IF(K≠0 and K≠I and K≠J)，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(I≠0 and I≠K)，THEN 如果节点号I不等于0和K，则
RA(I)=TRUE 关联矩阵第IND行第I列元素置为“真”
M=M+1 关联矩阵第IND行“真”元素计数+1
END IF
IF(J≠0 and J≠I and J≠K)，THEN 如果节点号J不等于0和I和K，则
RA(J)=TRUE 关联矩阵第IND行第J列元素置为“真”
M=M+1 关联矩阵第IND行“真”元素计数+1
END IF
END IF
END IF
END IF
END LOOP1
将节点连通矩阵第IND+1~Nd行与第IND行比较，寻找包含节点IND的连通子集
M＜子集k0节点数且有新“真”元素出现时，循环
LOOP1 WHILE(M＜NST(k0,2) and M＞NSUM) 当
节点ld属于连通子集k0，且关联矩阵第IND行第ld列元素为“假”，且未找到节点ld新连通子集号时，循环
NSUM=M
LOOP2 ld=IND+1，Nd ld自IND+1至Nd循环
IF (NDS0(ld)=k0 and RA(ld)=FALSE and NDS(ld)=0)，THEN当
LOOP3 l=1，Nd l自1至nd循环
RB(l)=FALSE 关联矩阵第ld行第l列元素置为“假”
END LOOP3
RB(ld)=TRUE 节点关联矩阵第ld行对角元素置1
形成节点关联矩阵的第ld行RB
LOOP3 l=1，Nc l自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(J≠0 and J≠I)，THEN 如果节点号J不等于0和I，则
RB(J)=TRUE 关联矩阵第ld行第J列元素置为“真”
END IF
IF(K≠0 and K≠I and K≠J)，THEN如果节点号K不等于0和I和J，则
RB(K)=TRUE 关联矩阵第ld行第K列元素置为“真”
END IF
END IF
IF(J=ld)，THEN 如果节点号J等于节点号ld，则
IF(I≠0 and I≠J)，THEN 如果节点号I不等于0和J，则
RB(I)=TRUE 关联矩阵第ld行第I列元素置为“真”
END IF
IF(K≠0 and K≠I and K≠J)，THEN如果节点号K不等于0和I和J，则
RB(K)=TRUE 关联矩阵第ld行第K列元素置为“真”
END IF
END IF
IF(K=ld)，THEN 如果节点号K等于节点号ld，则
IF(I≠0 and I≠K)，THEN 如果节点号I不等于0和K，则
RB(I)=TRUE 关联矩阵第ld行第I列元素置为“真”
END IF
IF(J≠0 and J≠I and J≠K)，THEN如果节点号K不等于0和I和J，则
RB(J)=TRUE 关联矩阵第ld行第J列元素置为“真”
END IF
END IF
END IF
END IF
END LOOP3
如果节点l属于原连通子集k0，且关联矩阵第IND行第l列元素与第ld行第l列元素同为“真”，则
LOOP3 l=1，Nd l自1至Nd循环
IF(NDS0(l)=k0 and RA(l) and RB(l))，THEN
LOOP4 j=1，Nd jl自1至Nd循环
如果第IND行第j列元素为“假”，且ld行第j列元素为“真”，则
IF(RA(j)=FALSE and RB(j)=TRUE)，THEN
RA(j)=TRUE 行IND列j置为“真”
M=M+1 关联矩阵第IND行“真”元素计数+1
END IF
END LOOP4
GOTO 20 跳出循环3
END LOOP3
20 END LOOP2
END LOOP1
N=N+1 连通子集计数+1
IF(M=NST(k0,2))，THEN 如果M=原连通子集k0中节点总数，则
LOOP1 l=1,Nd l自1至Nd循环
IF(NDS0(l)=k0)，NDS(l)=1 连通子集k0中节点l的子集号置为1
END LOOP1 （子集k0全连通）
ELSE 否则
LOOP1 l=1,Nd l自1至Nd循环
IF(RA(l)=TRUE)，NDS(l)=N 如果RA(l)为“真”，连通子集k0中节
END LOOP1 点l的子集号置为N
LOOP1 l=IND+1，Nd l自IND+1至Nd循环
IF(NDSO(l)=k0 and NDS(l)=0) THEN 如果节点l属原子集k0且无新子集号，则
IND=l 将寻找下一连通子集的起始节点号置为l
GOTO 10 返回10，自节点l开始寻找下一连通子集
END IF
END LOOP1
END IF
NST(k0,1)=N 将原始连通子集k0内的连通子集数置为N
LOOP1 l=1，Nc l自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的第二个节点号
IF(I=0)，THEN 如果I为0，则
I=NOD(l,3) I=元件l的第三个节点号
IF(I=0)，THEN 如果I为0，则
30 NCT(l)=0 元件l所在连通子集号为0（孤立元件）
GOTO 40
END IF
END IF
END IF
ELSE
GOTO30
END IF
END IF
NCT(l)=NDS(I) 元件l所在连通子集号为节点I的连通子集号
40 END LOOP1
RETURN
END