本文针对 ClearQuest 的状态转移模型设计和实现了基于广度优先遍历算法的最短状态转移动作序列算法。在设计算法的过程中同时证明了基于广度优先遍历算法计算 ClearQuest 状态转移模型中最短状态转移路径的正确性，从而完整的解决了计算 ClearQuest 状态转移模型中最短状态转移路径这一问题。使用本文提供的方法，用户只需输入起始和终止状态就能得到实现状态转移的最短动作序列，同时还能判定两个状态之间是否存在可能的动作转移序列。本方法可广泛用于测试自动化等应用场景中。

CQ 状态转移模型概述：

ClearQuest 是一个工业级的缺陷跟踪和变更管理工具，为了有效的实现缺陷跟踪和变更管理，ClearQuest 定义和实现了一系列概念和机制。在 ClearQuest 的缺陷限跟踪和变更管理模型中，RecordType 和 StateTransition Model 是两个最重要的概念。RecordType 机制可以使用户定义他们想要跟踪和管理的实体，同时，结合定义在相应 RecordType 上的 StateTransition Model，用户就可以利用 ClearQuest 来管理和跟踪这种 RecordType 的实体在某一时刻所处的状态，这样就可以降低用户管理缺陷和变更的脑力负担，有效的控制和管理缺陷和变更。

ClearQuest 同时提供了几套 API，比如基于 BASIC 的 API 和基于 PERL 的 API，这些 API 可以使用户方便的定制 RecordType，并为相应的 RecordType 编写相应的 HOOK。在这个过程中，用户经常需要根据这个 RecordType 的 Transition Model 来计算从一个起始状态到一个终止状态需要执行的动作（Action）序列。

状态转移矩阵定义了某个 RecordType 的变更请求的声明周期。在 ClearQuest 的状态转移模型中有以下约束规则：

1. 要求在相邻的两个状态有且只有一个动作（Action）。
2. ClearQuest 要求在状态转移模型中不能存在孤立的状态，也就是说，不允许有这样一种状态，没有任何 Action 可以到达这个状态。

任何一个 RecordType 的状态转移模型都要满足以上两个约束规则。

图 1 是一个 ClearQuest 中某种 RecordType 的状态转移模型。在 ClearQuest 中，其状态转移模型一般使用状态转移矩阵来存储，如本图所示。在这个状态转移矩阵中可以看出八种不同状态形成一个 8*8 的矩阵，列头表示源状态，行头表示目标状态，矩阵中的元素表示从源状态到目标状态需要进行的 Action. 如果两个状态之间可以转移，则两个状态的交点元素为非空，否则为空。

图 2 是对应于上面状态转移矩阵的状态转移图，从中我们可以看出，这个 RecordType 的状态转移模型是符合 ClearQuest 的状态转移模型的约束规则的。即：不存在孤立状态；每一对源和目标状态之间只有一个 Action。

建模及证明

我们经常面临的问题是，知道初始状态和终止状态，需要求从初始状态到终止状态的状态转移路径，也就是从初始状态到终止状态的所需执行的动作序列；更进一步，求一条从初始状态到终止状态的最短路径。

为此，我们需要首先根据类似于上图的这种状态转移矩阵建立一个可以解决问题的模型，基于这样一种模型，我们可以设计出相应的算法，从而计算出从给定初始状态到终止状态的最短状态转移路径。

我们建模的思路如下：以矩阵中所有状态为节点，所有动作为边，无遗漏的遍历所有的状态和动作，从而能够为这个状态转移模型建立一个层次模型，也就是一棵树。对应于以上状态转移矩阵，其树状模型如图 3 所示：

在这个层次模型中节点的个数等于状态转移矩阵中状态的个数，边的个数等于状态转移矩阵中非空元素的个数，自上而下，每一条边上的两个节点代表源状态和目标状态，这条边就代表从源状态和目标状态需要执行的动作。树中的任何一个分支就代表从一个给定的初始状态到终止状态的状态转移路径。比如从 Open 状态到 Closed 状态，就有两条可能的路径：

Open->InPlan->Verify->Closed 和 Open->InPlan->Closed。二者的状态转移路径分别是：

Approve，Deploy，Close 以及 Approve，Confirm。

基于这个层次模型，我们可以直观的看出，对于给定的起始和终止状态，终止状态在树中所处的层次越高，那么状态转移路径越短。

因此，我们使用广度遍历算法来求出一条从给定的初始状态到终止状态的路径，同时保证终止状态是在遍历过程中第一次搜索到的终止状态（某些状态在树中可能出现不止一次，比如前面例子中的 Closed 状态）。满足这两个条件的起始到终止状态的路径就是一条最短路径。

我们可以用反正法证明这个想法的正确性：

假设给定的初始状态为 A，终止状态为 B，如果满足上面的两个条件的状态转移路径不是最短路径，那么根据广度优先遍历的原理可知，在这个层次模型中存在一个 B 状态位于当前 B 状态的上一层，但是这是不可能的，因为第二个条件保证当前的 B 状态是第一次遇到的 B 状态，如果此 B 状态的上层还有一个 B 状态，则和第二个条件矛盾。因此，基于这个两个条件：一，广度优先遍历；二，保证是第一个遍历到的终止状态；算法求出的是最短状态转移路径。

算法实现

算法可以使用各种编程语言实现，本文中使用 Perl 来实现前面描述的算法。在算法实现过程中，首先要定义几个关键的数据结构。

首先要定义树结构中的节点，节点需要既能表示当前节点代表的状态，又要便于回溯。节点结构定义如下：

struct Vertex => {
state => '$',
previous => '$',
};

其中 State 字段代表状态，previous 字段用来指向当前节点的父节点，以便于找到终止状态后能够回溯，从而找到整个状态转移路径。

由于本算法基于广度优先遍历，因此需要定义个 Queue，这个可以使用 Perl 中的 List 来代替。

最后我们需要一个数据结构在程序中存储状态转移矩阵。由于 CQ API 没有提供程序可直接使用的状态转移矩阵存储结构，因此，我们可以利用 CQ 的其它 API 在程序执行过程中动态生成程序可以使用的状态转移模型存储结构。下面的程序清单就是利用 CQ API 遍历某个具体的 RecordType 的实体的状态转移矩阵生成状态转移模型存储结构的过程。

在我们的实现中，利用 Perl 的关联表来存储这个实体的状态转移关系。

在这个关联表中由源状态和目表状态组成的字符串做 key，这个 key 是唯一的，这一点可以从 CQ 状态转移模型中的约束规则中得到：源状态和目标状态之间只允许有一个 Action。而源状态转移到目标状态 Action 做 Value。构建过程解释如下：

1. 获得当前 $entity 所关联的 $session;
2. 利用获得 $session 变量获得 entity 对应的 $entityDef 对象。一个 EntityDef 对象对应一个 RecordType，RecordType 是 schema 静态存在实体定义，而 EntityDef 对象是 RecordType 在运行时的表现形式，它包含了 ClearQuest 在运行时用来创建 entity 所需信息。
3. 使用 EntityDef 对象的 GetActionDefNames() 的方法获得这个 RecordType 定义的状态转移模型中的所有 Action。
4. 遍历所有 Action，获得这个 Action 的所有源状态及唯一的一个目标状态，以源状态和目标状态的组合作为 Key，Action 名字为 Value，建立关联表。

最终，这个关联表中就存储了我们想要的这个 RecordType 的状态转移模型。构建过程的代码如清单 1 所示。

                
Sub getTransitionMatrix(){
My %matrix;
My $sourceStates;
My $destinationState;
$session=$entity->GetSession(); 
$entityDef=$session->GetEntityDef($entity->GetEntityDefName());
$actionList = $entityDef->GetActionDefNames(); 
foreach $actionName(@$nameList)
{ 

$sourceStates= $entitydef->GetActionSourceStateNames($actionName); 
foreach my $sourceName (@$sourceStates)
{
 $destinationState = $entitydef->GetActionDestStateName ($actionName);
 $matrix{$sourceName.$destinationState} = $actionName;
}

}
return %matrix;
}

利用以上数据结构及基于广度优先遍历的算法可得到算法的伪代码如下：

1. 以用户传入的初始状态为参数建立队列头节点，并加入队列；
2. 从队列中取出一个节点；
3. 如果取出的节点的 state field 是目的状态，执行 3~5；否则执行 6~7；
4. 将布尔变量 find 置为真值，表明已经找到终止状态接点；
5. 计算状态转移序列。方法为从当前找到的最终状态所处节点开始，根据其 previous 字段回溯，直到初始状态所在节点，结束回溯；
6. 遍历状态转移序列。取其 state 字段，将两两相邻的状态组合在一起作为键值到 hash table 中去找相应的 action，将这些 action 保留起来就得到了我们要求的动作序列。
7. 获得当前状态的所有可能的目标状态 ( 子状态 )；
8. 遍历当前节点的所有目标状态，为每个状态建立相应节点，每个节点的 state field 是当前遍历过程中的每个遍历到的目标 state，其 previous field 是队列当前头节点的索引值，这样是为了成功找到最后的目标状态后回溯。将其依次加入队列中；
9. 重复 2~7 步直到队列为空或找到终止状态节点（find 值为真）。

基于以上伪代码的程序实现如下程序清单 2 所示，其中第六步的实现如代码清单 3 所示：

                
sub stateTransformation()
{
my ($from, $to, %stmatrix) = @_;
my @transition = ();
my @queue = ();
my @actionSeq = ();
my @stateSeq = ();
my $state = '';
my $find = 0;
#queue's head
my $front = -1;
#queue's tail
my $rear = 0;
#push the first node that represents the start state to the queue
my $node = Vertex->new();
$node->state($from);
$node->previous(-1);
push(@queue,$node);
#BFS the state transition matrix to get the action sequence
while($front!=$rear&&!$find)
{
$front++;
$state = $queue[$front]->state;
# 到达终止状态
if($state eq $to)
{
$find=1;
my $k=$front;
my $j;
# 如果到达终止状态我们将回溯获得状态转移序列，然后根据状态转移序列计算动 # 作序列 
# 计算状态转移序列
do
{
$j=$k;
unshift(@stateSeq,$queue[$k]->state);
$k=$queue[$k]->previous;
$queue[$j]->previous(-1);
}while($k!=0); 
unshift(@stateSeq,$from);
# 计算动作序列
my $state;
for($state=0;$state<@stateSeq-1;$state++)
{
my $tran = $stateSeq[$state]."->".$stateSeq[$state+1];
my $action = $stmatrix{$tran};
push(@actionSeq,$action);
}
}
# 搜索当前状态的所有子状态
my @transition = getAllNeighbors($state,%stmatrix);
for (my $index = 0;$index < @transition;$index++)
{
$rear++;
$node = Vertex->new();
$node->state($transition[$index]);
$node->previous($front);
push(@queue,$node);
}
}
# 返回计算结果
return @actionSeq;
}

                
sub getAllNeighbors()
{
my ($parentState,%matrix) = @_;
my @neighborState = ();
my @transitionTable = keys(%matrix);
my($key);
foreach $key (@transitionTable)
{
if ($key=~/($parentState)->([a-zA-Z]*)/)
{
push(@neighborState,$2);
}
}
return @neighborState;
}

为了便于读者理解本算法的程序结构，程序的流程图如下所示：

基于以上算法，针对本文所给出的状态转移模型计算从 Open 到 Closed 最短状态转移路径可以得到图中绿色的分支路径，在这个路径中，我们可以看出需要执行两步动作，Approve 和 Confirm。图 5 是程序实际执行的结果：

很明显在图 6 中还存在另外一条分支可以从 Open 到 Closed，也就是图中的红色分支。在这个分支中需要执行三步动作：Approve，Deploy，Close。从这个例子中可以看出本文提供的算法执行得到了我们期望的结果。

总结

本文基于广度优先遍历算法提出并实现了计算 ClearQuest 状态转移模型中最短状态转移路径的方法。这个方法可以作为 CQ API 的一个有益补充，可用于测试自动化等应用中需要计算状态转移路径的场景中。

参考资料

• 访问 developerWorks 上的 Rational ClearQuest 产品专题 了解深入的信息。
• 访问 developerWorks 中国 Rational 软件专区，获得关于 Rational 软件交付平台 (Rational Software Delivery Platform) 产品的技术资料和最佳实践。
• 订阅 developerWorks Rational 专区通讯。关注 developerWorks Rational 的内容。每两周，您将收到关于 Rational Software Delivery Platform 的最新技术资源和最佳实践的更新。
• 订阅 Rational Edge 电子杂志，阅读关于有效软件开发背后的概念的文章。

• 试用 Rational ClearQuest 7.0。试用版下载是免费的，但需要注册。
• 下载 IBM Rational 软件的试用版。

讨论

• 查看 developerWorks 博客 并加入 developerWorks 社区。

组织简介 | 联系我们 |   Copyright 2002 ®  UML软件工程组织 京ICP备10020922号

京公海网安备110108001071号