2009年第 5期 商丘职业技术学院学报 V01．8，N0．5
第 8卷(总第44期) JOURNAL OF SHANGQIU VOCATIONAL AND TECHNICAL COLLEGE Oct．，2009
文章编号：1671—8127(2009)05—0029一o4
基于超图的软件进化模型
李喜英
(郑州市电子信息工程学校，河南 郑州450007)
摘 要：原型法在开发大型软件系统、理解其开发和进化过程方面是最好方法，但由于不同系统的开发环境和
过程不同，很多形式模型在实现中都有技术上的困难．用基于超图的软件进化模型表示和研究有多维分层结构的
复杂软件的进化过程，可以有效地帮助开发者描述、理解和控制软件的进化过程．经开发多媒体系统的实践证明，
这一模型在需求多变的软件开发中进行软件进化控制效果良好．
关键词 ：软件进化；超图；进化路径；多媒体系统
中图分类号：TN91 文献标识码：A
软件开发的根本目标是满足用户需求和始终如一地维持产品的运行 J¨．原型法是开发复杂的大型软件
系统、理解大型软件系统开发和改进过程的最好方法 』．由于开发环境和过程有不同的问题域，一些形式模
型在实现上都有技术上的困难．然而，采用面向对象方法的软件进化模型在描述软件进程过程、跟踪进化历
史 J、探讨软件对象之间的依赖关系等方面却很有成效，且可成功实现可重用的软件进化组件的检索 ．
迄今为止，已经公布了许多与软件进化过程形式化研究相关的成果，其中包含面向对象软件进化、借助
计算机辅助原型的软件进化、进化的数据图表模型及控制系统、进化超图模型 ¨等等．本文介绍了最新的
一 个基于数学定义的，用于表现和探索复杂的、层次化的、多维结构的软件进化的超图形式模型．
与原型法结合的超图模型可以提高开发多媒体系统和虚拟现实系统的效率，改进指令系统、控制系统、
通信和智能系统(C3I)等的开发．推荐的这一模型可以帮助开发者描述和理解软件开发过程、跟踪和记录软
件开发历史、控制和管理软件进化任务、分析软件需求、构建计算机辅助软件进化系统．
1 超图模型
超图模型是用一张超图表示软件进化的历史和软件开发中即将采用的方案．超图采用了超边，是对有
向图一般概念的推广，即超图中可以存在多输入和多输出结点．超图是一个有向无环图，具体可采用如下定
义进行描述．
1．1 超图
若一个(有向)图定义为元组 H=(N，E，I，0)其中：N为一个结点集合；E为一个超边(简称为边)集合；
是为各超边提供输入集合的函数；是为各超边提供输出集合的函数；在超图中，路径表示一个结点和超边均
可以被跟踪的进化历史．
1。2 路 径
令 H：(N，E，I，0)为一超图，从节点 n到 n 的路径可表示为由k条(k>0)条超边构成的e ⋯e 的边序
列与 nl⋯nk+l l的节点序列，即在令 n：nl且 n =n⋯ 时，对 i=1，2，⋯，k有ni∈I(e1)且 ni+l∈0(e。)．
软件进化中的追溯问题可以用超图中的路径表示．通过进化路径，后继子图相对于其前各子图来讲均
是可达的．
1．3 对于结点集 R，结。羔集合 N可达
当且仅当到每一个结点 n(n∈N)都存在有从若干 n (n ∈R)的一条路径，则对于结点集 R，结点集合 N
可达。
对于结点集 R，超图H=(N，E，I，0)可达，即当且仅当对于从结点集 R，超图H中结点集N是可达的．超
收稿日期：2009—06—10
作者简介：李喜英(1973一 )，女，河南郑州人，郑州市电子信息工程学校讲师，硕士，主要从事通信工程研究
· 29·
2009正 商丘职业技术学院学报
图 H的根结点由满足对于结点来讲，超图 H可达．
如图1中，超图H为从另一超图 R可达．总存在从超图 R中某些元素可通过一条路径可达超图H中的
任一元素．由此可得，n 。为超图 H的根结点，而 n 是超图H的叶子结点
2 软件进化形式
叨 ④
．-一④
图 1 超图 R到超图 H可达
在进化超图模型中，软件进化元素和步骤分别采用节点和边进行定义 ]．元素属性和步骤都要进行记
录和标志．
2．1 进化超 图
进化超图 H=(N，E，I，0)是带标记的有向无环图，其中函数标记 LN：N—c与 L ：E—A．
该图满足如下假设 ：
(1)N中元素是软件进化元素的唯一标志；
(2)E中元素是软件进化步骤的唯一标志；
(3)函数 I、O给出各软件进化步骤的输入和输出，比如 O(e)n0(e )≠0蕴含 e=e ．
(4)函数 L 标志来自集合 c的带有元素属性的任一结点，包含软件进化元素的相应版本．
(5)函数 L 标志带有来自于集合A的步骤属性的任一条边，包含当前软件进化步骤的状态，如A={s，
d}．A (即是 A中每一元素都有形式(s，a )或(d，a )，其中a ∈A ．标志 s的边被称为一步，标志 d的一个
元素被称为一个分解．
由于可对超边进行细化，进化超图成为一个多层结构．事实上，超边是一个多层结构的进化步骤．只要
当顶层进化超图被细化为若干个元子进化超图，顶层软件进化步骤也同时被细化为若干个元子软件进化步
骤．上述工作可采用如下定义为：
2．2 顶层软件进化步骤
设 H=(N，E，I，O)是一张软件进化超图，对于某一超边 e∈E，当且仅当e无父进化步骤，则 e为顶层进
化步骤．
2．3 元子进化步骤
设 H=(N，E，I，0)是一张软件进化超图，对某一超边 e∈E，当且仅当e不能被扩展成一个步骤且它的
输出集最多含一个元素，则 e被称为元子进化步骤．
2．4 顶层进化超 图
设 H=(N，E，I，O)是一张软件进化超图，若其中每一条边均代表一个顶层进化步骤，则该超图为顶层进
化超图．
2．5 元子进化超 图
一 个元子进化超图即指进化超图 H=(N，E，I，O)中每一边都是一个元子进化步骤．
3 多媒体超图模型
现在快速原型法和形式进化都已广泛的应用于多媒体系统的用户接 口中．用原型法的超图模型，可以
从交互式的用户接口交互设计、用户接口软件设计的过程中获得软件设计需求．
依据多媒体系统的交互性 、以进化为中心的用户接口设计过程，结合根据基于问题的信息系统(IBIS)模
型改进的过程分析图表模型，我们把多媒体系统进化过程中的软件进化对象分类为软件进化步骤和软件进
· 30·
李喜英：基于超图的软件进化模型 第5期
化元素．
软件进化过程可分为8个步骤：软件原型样本、问题分析、需要分析、详细设计、模块实现、程序集成、软
件产品演示、软件产品执行．软件进化过程中的元素分成 7种类型：评论及校正、发布、需求、细化、模块，程
序，优化．
在顶层进化超图中的每个由一个步骤和一个元素组成的顶层对象，都可以直接或间接的分解为可组成
一 个元子进化超图的元子对象集合，其中包含音频、视频，文本、图像、动画等多媒体对象元素模块，这些元
素又可以集成为多媒体软件组件．集成过程如软件进化超图图2所示，图例说明如下 ．
组件：P一软件原型程序；S一详细设计；c一评价；M一模块；I一问题；O一优化；R一需求；Pd一软件成品
程序
步骤：s—c：软件原型示范；s—M：模块实现；s—I：问题分析；s—P：程序集成；s—R：需求分析；s一0：软
件产品示范；s—S：详细设计；S—Pd：软件产品实现
图 2 多媒体软件进化顶层超 图
图2中采用两个概念：主输入驱动路径(PP)和从输入驱动(sP)．若存在一个输入结点和一个输出结点
分别表示同一组件的两个不同版本，则由超边形成的从输入顶点到输出顶点的路径称为主输入驱动路径．
若存在一个输入顶点和一个输出顶点分别表示不同类型的组件，则由超边形成的从输入顶点到输出顶点的
路径称为从输入驱动路径．
图2中说明了先根据需求 R1．1通过步骤 s—S1．1，s—M1．1和s—P1．1即详细设计 、模块实现、程序集
成三个步骤，设计出多媒体系统最初原型 P1．1；接着对原型 P1。1进行软件原型示范应用评价(S—S1．2，)、
问题分析(s—I1．2)、再需求分析(s—R1．2)等步骤获取新的需求 R1．2，然后进行第二周期的详细设计(s—
S1．2)、模块实现(S—M1．2)、程序集成(S—P1．2)以及最后的产品优化(s—O1．2)和产品实现(s—Pd1．1)，
即可推出软件产品．由于多媒体系统内部软件较为简单，所以本例开发中仅采用了两周期的软件进化，即可
得到较为理想的软件产品．软件产品程序 Pd1．1的开发是通过用于优化的软件产品示例步骤s—O1．1和软
件步骤 s—Pd1．1进行的．
． 利用超图进化模型进行软件开发时，可对顶层进超图中的步骤进行分解，从而使得软件开发过程有更
明确的思路．为表示顶层超图的步骤分解的结果，即子进化超图，须考虑如下细节：由于一个步骤的输入顶
点到来自不同人口，超图中的一个步骤可以用一个多尾的箭头或复合箭头表示．为了支持软件进化过程的
跟踪能力，我们使用复合箭头说明一个步骤的所有路径，即借助复合箭头的表示力反映一个步骤的一个公
共输出结点和不同的路径(主输入驱动路径或从输入驱动路径)．
图3展示了程序集成步骤的细化过程．s—P1．2被细化为5个子步骤，除子步骤 s—P31．2只有从输入
外，其余4个子步骤都有两种类型的输入即主输入和从输入．图3(A)中子程序 P11．1、I：'21．1、P41．1、P51．1
的旧版本是其新版本PI1．2、P21．2、P41．2、P51．2的设计参考，子程序P31．1旧版本未被借鉴，新程序模块
单独开发．图3(B)中的子模块 M11．2和 M31．2是用多媒体编程语言 FLAVOR进行编码的软件模块的，子
模块 M21．2，M41．2和 M51．5则都是多媒体对象，它们均被集成为新的子程序的版本．
· 3l·
2009住 商丘职业技术学院学报
4 结论
(A)
图 3 步骤 s—p1．2的细化
(13)
本文所介绍的采用超图形式的软件进化模型是侧重于专用领域的软件开发结构．因为需求的频繁变
动，软件开发中存在许多形式化方面的困难，但采用基于原型法的超图方式可以解决如软件进化路径的跟
踪、对象管理、过程描述、需要分析等软件进化中的问题．我们的一个简单多媒体系统开发实践验证这一模
型在应用中相当有效．
参考文献：
[1]Luqi and J．A．Goguen，Formal Methods Promises and Problems[J]．IEEE Software，January 1997，PP．73—85．
[2]M．Ham，V．Berzins，and Luqi，Software Evolution via Reusable Architecture[j]．Proceedings of 1999 IEEE Conference and Workshop on Engi．
neefing of Computer—Based Systems，Nashville，Tennessee，March 7—12，PP．11—17．
[3]Luqi，A Graph Model for Software Evolution[J]．IEEE Trans．on Software Engineering，Vo1．16，No．8，August 1990，PP．917—927．
[责任编辑 乐 知]
A Formal M odel for Software Evolution Based on Hypergraph
LI Xi—ying
(Zhengzhou Electronic and Information Engineer School，Zhengzhou 450007，China)
Abstract：A form al method is the best approach for developing large and complex software systems and comprehending their development and evolu—
tion processes，but there are many technical dif? culties in their implement because of the different developing environments and processes of different
software．Representing and exploring complicated hierarchy and multidimensional structure of software evolution with the formal model based on hyperg—
raph，can help developers to describe，understand，and control software evolution pr~edure．Proved by a multimedia systemg development，this model
works well ou the evolution control of software facing varying requirements．
Key words：software evolution；hypergmph；evolution path；multimedia system
· 32·
