《测试人员的图论.ppt》由会员分享,可在线阅读,更多相关《测试人员的图论.ppt(40页珍藏版)》请在三一办公上搜索。
1、第四章 测试人员的图论,东北大学软件学院,由安博测试空间技术中心http:/,图,东北大学软件学院,图(又叫做线性图)是一种由两个集合定义的抽象数学结构,即一个节点集合和一个构成节点之间连接的边集合。,定义 图G=(V,E)由节点的有限(并且非空)集合V和节点无序对偶集合E组成。V=n1,n2,nm)和 E=el,e2,ep 其中每条边ek=(ni,nj),ni、nj V。,举例,东北大学软件学院,V=nl,n2,n3,n4,n5,n6,n7)E=e1,e2,e3,e4,e5=(nl,n2),(nl,n4),(n3,n4),(n2,n5),(n4,n6),图4-1 有7个节点和5条边的图,节点
2、的度,东北大学软件学院,定义 图中节点的度是以该节点作为端点的边的条数。我们把节点n的度记做deg(n)。,deg(n1)=2 deg(n2)=2 deg(n3)=1 deg(n4)=3 deg(n5)=1 deg(n6)=1 deg(n7)=0,关联矩阵,东北大学软件学院,定义 拥有m个节点和n条边的图G=(V,E)的关联矩阵是一种mn矩阵,其中第i行第j列的元素是1,当且仅当节点i是边j的一个端点,否则该元素是0。,相邻矩阵,东北大学软件学院,定义 拥有m个节点和n条边的图G=(V,E)的相邻矩阵是一种mm矩阵,其中第i行第j列的元素是1,当且仅当节点i和节点j之间存在一条边,否则该元素是
3、0。,路径,东北大学软件学院,定义 路径是一系列的边,对于序列中的任何相邻边对偶ei、ej,边都拥有相同的(节点)端点。路径可以描述为一系列边,也可以描述为一系列节点。一般更常见的是节点序列。,连接性,东北大学软件学院,定义 节点ni和nj是被连接的,当且仅当它们都在同一条路径上。“连接性”是一种图的节点集合上的等价关系。为了说明这一点,可以再复习一遍定义等价关系的三个性质:1连接性是自反的,因为每个节点显然都在到其本身长度为0的路径上。2连接性是对称的,由于如果ni和nj在一条路径上,则nj和ni也在同一条路径上。3连接性是传递的。,组件,东北大学软件学院,定义 图的组件是相连节点的最大集合
4、。等价类中的节点是图的组件。图4-1种的图有两个组件:n1,n2,n3,n4,n5,n6 n7,压缩图,东北大学软件学院,定义 给定图G=(V,E),其压缩图通过用压缩节点替代每个组件构成。给定图的压缩图是惟一的。S1=n1,n2,n3,n4,n5,n6S2=n7,圈数,东北大学软件学院,定义 图G的圈数由V(G)=e n+p给出,其中:e是G中的边数。n是G中的节点数。p是G中的组件数。,有向图,东北大学软件学院,定义 有向图(或框图)D=(V,E)包含:一个节点的有限集合V=(n1,n2,nm),一个边的集合E=是节点ni、njV的一个有序对偶。,有向图例子,东北大学软件学院,V=nl,n
5、2,n3,n4,n5,n6,n7)E=e1,e2,e3,e4,e5=,,图4-2 一个有向图,外度和内度,东北大学软件学院,定义 有向图中节点的内度,是将该节点作为终止节点的不同边的条数。节点n的内度记做indeg(n)有向图中节点的外度,是将该节点作为开始节点的不同边的条数。节点n的外度记做outdeg(n)indeg(n1)=0 Outdeg(n1)=2 indeg(n2)=1 Outdeg(n2)=1 indeg(n3)=0 Outdeg(n3)=1 indeg(n4)=2 Outdeg(n4)=1 indeg(n5)=1 Outdeg(n5)=0 indeg(n6)=1 Outdeg(
6、n6)=0 indeg(n7)=0 Outdeg(n7)=0,节点的类型,东北大学软件学院,定义 内度为0的节点是源节点。外度为0的节点是吸收节点。内度不为0,并且外度不为0的节点是传递节点。,有向图的相邻矩阵,东北大学软件学院,定义 有m个节点的有向图D=(V,E)的相邻矩阵是一种mm矩阵:A=(a(i,j),其中a(i,j)是1,当且仅当从节点i到节点j有一条边,否则该元素为0。,路径和半路径,东北大学软件学院,定义(有向)路径是一系列边,使得对于该序列中的所有相邻边对偶ei,ej来说,第一条边的终止节点是第二条边的初始节点。环路是一个在同一个节点上开始和结束的有向路径。(有向)半路径是一
7、系列边,使得对于该序列中至少有一个相邻边对偶ei,ej来说,第一条边的初始节点是第二条边的初始节点,或第一条边的终止节点是第二条边的终止节点。,可到达性矩阵,东北大学软件学院,定义 有m个节点的有向图D=(V,E)的可达性矩阵是一种mm矩阵R=(r(i,j),其中r(i,j)是1,当且仅当从节点i到节点j有一条路径,否则该元素为0。有向图D的可到达性矩阵可以通过相邻矩阵A计算如下:R=I+A+A2+A3+Ak其中k是D最长路径的长度,I是单位矩阵。,图4-2的可到达性矩阵,东北大学软件学院,n-连接性,东北大学软件学院,定义 有向图中的两个节点ni和nj是:0-连接,当且仅当ni和nj之间没有
8、路径。l-连接,当且仅当ni和nj之间有一条半路径,但是没有路径。2-连接,当且仅当从ni和nj之间有一条路径。3-连接,当且仅当从ni和nj有一条路径,并且从nj到ni有一条路径。,图4-2的连接性,东北大学软件学院,n1和n7是0连接。n2和n6是1连接。n1和n6是2连接。n3和n6是3连接。,强组件,东北大学软件学院,定义 有向图的强组件是3-连接节点的最大集合。,n1,n2,S1,n5,S2,e1,e2,e4,n7,用于测试的图,东北大学软件学院,程序图 有限状态机 Petri网 状态图,程序图,东北大学软件学院,定义 给定一个采用命令式程序设计语言编写的程序,其程序图是一种有向图,
9、其中:1(传统定义)节点是程序语句,边表示控制流(从节点i到节点j有一条边,当且仅当对应节点j的语句可以立即在节点i对应的语句之后执行)。2(经过改进的定义)节点要么是整个语句,要么是语句的一部分,边表示控制流(从节点i到节点j有一条边,当且仅当对应节点j的语句或语句的一部分,可以立即在节点i对应的语句或语句的一部分之后执行)。,结构化程序设计构造的有向图,东北大学软件学院,串行,IF-Then,IF-Then-Else,条件,前测试环路,后测试环路,有限状态机,东北大学软件学院,有限状态机是一种有向图,其中状态是节点,转移是边。源状态和吸收状态是初始节点和终止节点,路径被建模为通路,等等。大
10、多数有限状态机表示方法都要为边(转移)增加信息,以指示转移的原因和作为转移的结果要发生的行动。,用于PIN尝试的有限状态机,东北大学软件学院,Petri网,东北大学软件学院,定义 Petri网是一种双向有向图(P,T,In,Out),其中,P和T是不相交的节点集合,In和Out是边集合,In PT,Out TP。,有标记的Petri网,东北大学软件学院,定义 有标记的Petri网是一种5元组(P,T,In,Out,M),其中(P,T,In,Out)是一个Petri网,M是从地点到正整数的映射集合。,Petri网的标记元组是。,两个基本定义,东北大学软件学院,定义 转移可以在Petri网中发生,
11、如果在其所有输入地点中至少有一个记号。,定义 当触发Petri网一个转移时,要从其每个输入地点删除一个记号,并在其每个删除地点增加一个记号。,两个基本定义,东北大学软件学院,M=,,事件驱动的Petri网,东北大学软件学院,定义 EDPN是一种多向图(P,D,S,In,Out),包括三个节点集合P、D和S,以及两个映射集合In和Out。其中:P是端口事件的集合。D是数据地点的集合。S是转移的集合。In是(PD)S的有序对偶集合。Out是S(PD)的有序对偶集合。,EDPN图,东北大学软件学院,为EDPN做标记,东北大学软件学院,定义 EDPN(P,D,S,In,Out)的一个标记M,是p元组的
12、一个序列M=,其中p=k+n,k和n是集合P和D中的元素个数,p元组中的个体项表示事件或数据地点中的记号个数。,EDPN图中的标记和转移,东北大学软件学院,标记:元组(p3,p4,d5,d6,d7)m1(0,0,1,0,0)m2(1,0,1,0,0)m3(0,0,0,1,0)m4(1,0,0,1,0)m5(0,0,0,0,1)m6(0,1,0,0,1)m7(0,0,0,0,1),转移:元组 描述 m1 无 m2 s7 m3 无 m4 s8 m5 无 m6 s9 m7 无,状态图,东北大学软件学院,Harel使用与方法无关的术语“团点”表示状态图的基本构件块。团点可以像维恩图显示集合包含那样地包含其他团点。团点还可以像在有向图中连接节点一样地通过边连接其他团点。,A,D,B,C,状态图中得初始状态,东北大学软件学院,A,D,B,C,进入子状态的默认入口,东北大学软件学院,A,D,B,C,状态图中的并发状态,东北大学软件学院,A,EF,B,C,D,总结,东北大学软件学院,图 有向图 用于测试的图,包括程序图、有向状态机、Petri网、状态图。,