CN102681939A - 一种选取路径的方法及装置 - Google Patents

Abstract

本发明公开了一种选取路径的方法，包括：当确定为目标覆盖元素选取的初始路径为不可达路径，并且确定目标覆盖元素的重选路径为不可达路径时，利用保存的不可达路径为目标覆盖元素选出子路径，若检测出该子路径可达，则确定该子路径为目标覆盖元素的可达路径。本发明还同时公开了一种选取路径的装置，采用本发明能进行路径重选，提高单元测试的覆盖率。

Description

一种选取路径的方法及装置

技术领域

本发明涉及软件测试领域中的单元测试技术，尤其涉及一种选取路径的方法及装置。

背景技术

单元测试是软件测试中最低级别的测试活动，通过使用单元测试技术，能够发现被测试软件中的大部分错误。所述单元测试为通过测试路径来进行测试的方法，具体为：为目标覆盖元素选定测试路径；基于该测试路径生成测试用例，运行测试用例测试单元中的所有元素。

但是，上述方法中为目标覆盖元素选定测试路径后，不再进行路径重选，如此，当初次选取的测试路径为不可达路径时，就会在进行单元测试时无法覆盖测试路径内的所有元素，从而影响单元测试的覆盖率。

可见，现有的单元测试中选取路径的方法，由于没有为目标覆盖元素进行路径重选，导致影响单元测试的覆盖率。

发明内容

有鉴于此，本发明的目的在于提供一种选取路径的方法及装置，能为目标覆盖元素进行路径重选，提高单元测试的覆盖率。

为达到上述目的，本发明的技术方案是这样实现的：

本发明提供了一种选取路径的方法，该方法包括：

当确定为目标覆盖元素选取的初始路径为不可达路径，并且确定目标覆盖元素的重选路径为不可达路径时，利用保存的不可达路径为目标覆盖元素选出子路径，若检测出该子路径可达，则确定该子路径为目标覆盖元素的可达路径。

上述方案中，所述确定为目标覆盖元素选取的初始路径为不可达路径，包括：为目标覆盖元素选取初始路径，检测初始路径是否为不可达路径，如果是，则确定为目标覆盖元素选取的初始路径为不可达路径；否则，确定初始路径作为目标覆盖元素的可达路径。

上述方案中，所述确定为目标覆盖元素选取的初始路径为不可达路径之后，该方法还包括：为目标覆盖元素重选路径，检测重选路径是否为不可达路径，如果是，则确定重选路径为不可达路径；否则，将重选路径作为目标覆盖元素的可达路径。

上述方案中，所述为目标覆盖元素重选路径，包括：

从初始路径中找到判定节点或交换节点作为当前节点，根据所述当前节点选出入口分支；

判断所述入口分支中是否包含目标覆盖元素，如果包含，则选出当前节点到出口节点之间不包括可替换节点的路径片段，将选出的路径片段补充到入口分支得到完整路径作为重选路径；

如果不包含，则判断是否存在不包括可替换位置的路径片段能够覆盖入口分支及目标覆盖元素，如果存在，则将入口分支更新为所述路径片段，选出所述路径片段最后一个节点到出口节点之间的路径片段，将选出的路径片段补充到入口分支得到完整路径作为重选路径；

如果不存在，则判断是否能够根据所述当前节点选出另一条入口分支，如果不能，则继续从初始路径中查找判定节点或交换节点作为当前节点；否则，选出另一条入口分支，继续判断所述入口分支中是否包含目标覆盖元素。

上述方案中，所述利用保存的不可达路径为目标覆盖元素选出子路径，若检测出该子路径可达，则确定该子路径作为目标覆盖元素的可达路径，包括：

从保存的不可达路径中选出不可达路径，利用该不可达路径，得到从该不可达路径中的第一个节点到目标覆盖元素组成的子路径；

检测该子路径是否为不可达路径，如果不是，则确定该子路径作为目标覆盖元素的可达路径，结束处理流程；

否则，判断当前是否仍保存有不可达路径，如果没有，则结束子路径选取，确定无可达路径，结束处理流程；否则，继续从保存的不可达路径中选出不可达路径。

本发明还提供了一种选取路径的装置，该装置包括：路径选取模块、路径检测模块和存储模块；其中，

路径选取模块，用于当确定为目标覆盖元素选取的初始路径为不可达路径，并且确定目标覆盖元素的重选路径为不可达路径时，利用存储模块保存的不可达路径为目标覆盖元素选出子路径，将子路径发送给路径检测模块，以及接收路径检测模块返回的检测结果，若检测结果为该子路径为可达路径，则确定该子路径为目标覆盖元素的可达路径；

路径检测模块，用于接收路径选取模块发来的子路径，检测该子路径是否为不可达路径，向路径选取模块发送检测结果；

存储模块，用于为路径检测模块提供保存的不可达路径。

上述方案中，所述路径选取模块，还用于为目标覆盖元素选取初始路径，将初始路径发送给路径检测模块，以及接收路径检测模块发来的检测结果，如果检测结果为该路径为不可达路径，则确定初始路径为不可达路径，否则，确定初始路径作为目标覆盖元素的可达路径；

相应的，所述路径检测模块，还用于检测路径选取模块发来的初始路径是否为不可达路径，将检测结果发送给路径选取模块。

上述方案中，所述路径选取模块，还用于为目标覆盖元素重选路径，将重选路径发送给路径检测模块，以及接收路径检测模块发来的检测结果，如果检测结果为路径是不可达路径，则确定重选路径为不可达路径，否则，将重选路径作为目标覆盖元素的可达路径；

相应的，所述路径检测模块，还用于检测路径选取模块发来的重选路径是否为不可达路径，将检测结果发送给路径选取模块。

上述方案中，所述路径选取模块，具体用于从初始路径中找到判定节点或交换节点作为当前节点，根据所述当前节点选出入口分支；

判断所述入口分支中是否包含目标覆盖元素，如果包含，则选出当前节点到出口节点之间不包括可替换节点的路径片段，将选出的路径片段补充到入口分支得到完整路径作为重选路径；

如果不包含，则判断是否存在不包括可替换位置的路径片段能够覆盖入口分支及目标覆盖元素，如果存在，则将入口分支更新为所述路径片段，选出所述路径片段最后一个节点到出口节点之间的路径片段，将选出的路径片段补充到入口分支得到完整路径作为重选路径；

如果不存在，则判断是否能够根据所述当前节点选出另一条入口分支，如果不能，则继续从初始路径中查找判定节点或交换节点作为当前节点；否则，选出另一条入口分支，继续判断所述入口分支中是否包含目标覆盖元素。

上述方案中，所述路径选取模块，具体用于从存储模块保存的不可达路径中选出不可达路径，利用不可达路径，得到从该不可达路径中的第一个节点到目标覆盖元素组成的子路径，将子路径发送给路径检测模块，以及接收路径检测模块发来的检测结果，如果检测结果为该路径为可达路径，则确定该子路径为目标覆盖元素的可达路径，结束操作，否则，判断当前存储模块是否仍保存有不可达路径，如果没有，则结束子路径选取，确定无可达路径，结束操作，否则，继续从存储模块保存的不可达路径中选出不可达路径；

相应的，所述路径检测模块，具体用于检测路径选取模块发来的子路径是否为不可达路径，将检测结果返回给路径选取模块。

本发明所提供的选取路径的方法及装置，能当确定为目标覆盖元素选取的初始路径，并且确定重选路径为不可达路径时，为目标覆盖元素选出子路径，若检测出该子路径可达，则确定该子路径为目标覆盖元素的可达路径；如此，通过多次路径重选，增加为目标覆盖元素选出可达路径的机率，从而提高单元测试的覆盖率。

附图说明

图1为本发明选取路径的方法流程示意图；

图2为本发明选取路径的装置的组成结构示意图。

具体实施方式

本发明的基本思想是：当确定为目标覆盖元素选取的初始路径为不可达路径，并且确定目标覆盖元素的重选路径为不可达路径时，利用保存的不可达路径为目标覆盖元素选出子路径，若检测出该子路径可达，则确定该子路径为目标覆盖元素的可达路径。

下面结合附图及具体实施例对本发明再作进一步详细的说明。

本发明提供的一种选取路径的方法，如图1所示，包括以下步骤：

步骤101：为目标覆盖元素选取初始路径，检测初始路径是否为不可达路径，如果是，则执行步骤102；否则，将该初始路径作为目标覆盖元素的可达路径，结束处理流程。

这里，所述目标覆盖元素为：根据实际测试需求，从控制流图中选出的节点；

其中，所述控制流图为：程序语句逻辑执行的图形化显示，其生成及结构均为现有技术，其表示方法可以为四元组(N，E，entry，exit)，其中N为节点的集合，反映程序中的语句；E为向边的集合，反映程序中语句间的控制关系；entry为程序中固定的唯一入口节点；exit为程序中唯一出口节点；所述唯一入口节点和所述唯一出口节点，当入口或出口不唯一的程序，可以采用人工添加一个虚入口或虚出口，将多个入口或出口通过虚边与虚入口或虚出口相连的方式，使程序的入口或出口唯一。

所述选取初始路径的方法为现有技术，这里不做赘述；所述初始路径为含有目标覆盖元素的完整路径；所述完整路径为：起始节点为控制流图入口节点，结束节点为控制流图出口节点的路径。

所述检测初始路径是否为不可达路径可以采用现有技术，包括：按照控制流图中数据流的方向，逐个对选取的初始路径上的节点的各个变量取值范围进行计算，若任意一个节点上的一个或多个变量的取值范围超出预置的门限值，则该节点为初始路径的矛盾节点，将该节点在初始路径上的入边作为矛盾边，将包含有该节点的初始路径作为不可达路径。其中，所述逐个对选取的初始路径上的节点的各个变量取值范围进行计算的方法为现有技术，这里不做赘述。

步骤102：将初始路径中的矛盾节点设置为可替换位置，并设置重选路径的次数为一。

步骤103：为目标覆盖元素重选路径。

本步骤具体为：

步骤1031：从初始路径中的可替换位置开始逆数据流方向查找判定节点或交换节点，若没有找到判定节点或交换节点，则将重选路径的次数设置为重选次数上限，执行步骤105；若找到判定节点或交换节点，则执行步骤1032。

这里，所述重选次数上限为预置的数值，比如，可以根据实际需要预置为5。

步骤1032：将所述判定节点或交换节点设置为当前节点，从以所述当前节点作为尾节点的出边集合中选出一条出边作为入口分支。

这里，所述选出一条出边可以为从出边集合中随意选出，也可以为选出出边集合中排在第一个的出边；其中，所述出边由从控制流图的第一个节点到当前节点之间的多个节点组成；所述出边集合为根据现有技术得出，这里不做赘述。

步骤1033：判断入口分支中是否包含目标覆盖元素，如果有，则执行步骤1036；否则，执行步骤1034。

步骤1034：根据控制流图，判断是否存在路径片段能够覆盖入口分支及目标覆盖元素，如果有，则将入口分支更新为该路径片段，执行步骤1035；否则，执行步骤1037。

这里，所述路径片段为不包括可替换位置的从入口分支尾节点到目标覆盖元素之间的路径。

步骤1035：将当前节点在入口分支中的下一个节点设置为当前节点，判断当前节点是否为目标覆盖元素，如果是，则执行步骤1036；否则，重复执行步骤1035。

步骤1036：根据控制流图，选出当前节点到出口节点之间的路径片段，按照节点顺序，将选出的路径片段补充到入口分支得到的完整路径作为重选路径，执行步骤104。

这里，所述当前节点到出口节点之间的路径片段不包括可替换节点的路径片段。

步骤1037：判断选出的入口分支是否为出边集合中的最后一条出边，如果是，则将当前节点在初始路径中的上一个节点设置为可替换位置，执行步骤1031；否则，从出边集合中选出下一条出边作为入口分支，执行步骤1033。

步骤104：检测该重选路径是否为不可达路径，如果是，则执行步骤105；否则，将该重选路径作为目标覆盖元素的可达路径，结束处理流程。

这里，所述检测该重选路径是否为不可达路径为：按照数据流的方向，逐个对重选路径上的节点的各个变量取值范围进行计算，若任意一个节点上的一个或多个变量的取值范围超出预置的门限值，则检测结果为该重选路径为不可达路径，保存该不可达路径，将重选路径的次数加一；否则，检测结果为该重选路径为可达路径；

其中，所述保存该不可达路径可以为将当前重选路径的次数作为不可达路径的编号，再将不可达路径的各个节点按照数据流的顺序进行保存。

步骤105：判断重选路径的次数是否达到重选次数上限，如果达到，则执行步骤106；否则，返回步骤103。

步骤106：为目标覆盖元素选出子路径，检测子路径是否为不可达路径，若不是，则将该子路径作为目标覆盖元素的可达路径，结束处理流程；否则，确定目标覆盖元素无可达路径。

本步骤具体包括：

步骤1061：从保存的不可达路径中选出一条不可达路径。

这里，所述选出一条不可达路径不可达路径为根据保存的不可达路径对应的编号进行选择，可以按照从小到大的顺序选择。

步骤1062：利用不可达路径，得到从该不可达路径中的第一个节点到目标覆盖元素组成的子路径。

步骤1063：检测子路径是否为不可达路径，如果不是，则选定该子路径作为目标覆盖元素的可达路径，结束处理流程；否则，执行步骤1064。

这里，所述检测子路径是否为不可达路径包括：按照数据流的方向，逐个对子路径上的节点的各个变量取值范围进行计算，若任意一个节点上的一个或多个变量的取值范围超出预置的门限值，则检测结果为该子路径为不可达路径，删除当前选出的不可达路径；否则，检测结果为该重选路径为可达路径。

步骤1064：判断当前是否仍保存有不可达路径，如果没有，则结束子路径选取，确定目标覆盖元素无可达路径，结束处理流程；否则，返回步骤1061。

本发明提供的一种选取路径的装置，如图2所示，包括：路径选取模块21、路径检测模块22和存储模块23；其中，

路径选取模块21，用于当确定为目标覆盖元素选取的初始路径为不可达路径，并且确定目标覆盖元素的重选路径为不可达路径时，利用存储模块23保存的不可达路径为目标覆盖元素选出子路径，将子路径发送给路径检测模块22，以及接收路径检测模块22返回的检测结果，若检测结果为该子路径为可达路径，则确定该子路径为目标覆盖元素的可达路径；

路径检测模块22，用于接收路径选取模块21发来的子路径，检测该子路径是否为不可达路径，向路径选取模块21发送检测结果；

存储模块23，用于为路径检测模块22提供保存的不可达路径。

所述路径选取模块21，还用于为目标覆盖元素选取初始路径，将初始路径发送给路径检测模块22，接收路径检测模块22发来的检测结果，如果检测结果为该路径为不可达路径以及该不可达路径的矛盾节点，则将初始路径中的矛盾节点设置为可替换位置，并设置重选路径的次数为一，否则，确定初始路径为目标覆盖元素的可达路径；相应的，所述路径检测模块22，还用于接收路径选取模块21发来的初始路径，检测接收到的初始路径是否为不可达路径，若是，则将路径中的矛盾节点及该路径为不可达路径作为检测结果返回给路径选取模块21，否则，将该路径为可达路径作为检测结果返回给路径选取模块21。

所述路径检测模块22，具体用于根据数据流的方向，逐个对选取的路径上的节点的各个变量取值范围进行计算，若任意一个节点上的一个或多个变量的取值范围超出预置的门限值，则将路径中的矛盾节点及该路径为不可达路径作为检测结果，否则，将该路径为可达路径作为检测结果。

所述路径选取模块21，具体用于从初始路径中的可替换位置开始逆数据流方向查找判定节点或交换节点，若没有找到判定节点或交换节点，则将重选路径的次数设置为重选次数上限，开始为目标覆盖元素选出子路径；

若找到判定节点或交换节点，则将所述判定节点或交换节点设置为当前节点，从以所述当前节点作为尾节点的出边集合中选出一条出边作为入口分支；判断入口分支中是否包含目标覆盖元素，如果入口分支中包含目标覆盖元素，则根据控制流图，选出当前节点到出口节点之间的路径片段，按照节点顺序，将选出的路径片段补充到入口分支得到的完整路径作为重选路径发送给路径检测模块22；

如果入口分支中不包含目标覆盖元素，则根据控制流图判断是否存在路径片段能够覆盖入口分支及目标覆盖元素，如果有，则将入口分支更新为该路径片段，将当前节点在入口分支中的下一个节点设置为当前节点，判断当前节点是否为目标覆盖元素，如果是，则根据控制流图，选出当前节点到出口节点之间的路径片段，按照节点顺序，将选出的路径片段补充到入口分支得到的完整路径作为重选路径发送给路径检测模块22；

否则，继续将当前节点在入口分支中的下一个节点设置为当前节点，如果控制流图中不存在路径片段能够覆盖入口分支及目标覆盖元素，则判断当前选出的入口分支是否为出边集合中的最后一条出边，如果是，则将当前节点在初始路径中的上一个节点设置为可替换位置，从初始路径中的可替换位置开始逆数据流方向查找判定节点或交换节点，否则，从出边集合中选出下一条出边作为入口分支，判断入口分支中是否包含目标覆盖元素；

相应的，所述路径检测模块22，还用于接收路径选取模块21发来的重选路径，对重选路径进行检测。

所述路径检测模块22，具体用于对重选路径进行检测后，则将路径中的矛盾节点及该路径为不可达路径作为检测结果返回给路径选取模块21，否则，将该路径为可达路径作为检测结果返回给路径选取模块21；相应的，所述路径选取模块21，具体用于接收路径检测模块22发来的检测结果，如果检测结果为该路径为不可达路径，则判断重选路径的次数是否达到重选次数上限，如果检测结果为该路径为可达路径，则确定重选路径作为目标覆盖元素的可达路径。

所述路径检测模块22，具体用于按照数据流的方向，逐个对重选路径上的节点的各个变量取值范围进行计算，若任意一个节点上的一个或多个变量的取值范围超出预置的门限值，则检测结果为该路径为不可达路径，否则，检测结果为该路径为可达路径。

所述路径选取模块21，还用于当收到的检测结果为该路径为不可达路径时，将当前重选路径的次数作为不可达路径的编号，再将不可达路径的各个节点按照数据流的顺序发送给存储模块23进行保存；相应的，所述存储模块23，具体用于将路径检测模块22发来的当前重选路径的次数作为不可达路径的编号，以及将不可达路径的各个节点按照数据流的顺序进行保存。

所述路径选取模块21，还用于判断当前重选路径的次数是否达到预置的重选次数上限，如果达到，则开始为目标覆盖元素选出子路径，否则，为目标覆盖元素重选路径。

所述路径选取模块21，具体用于开始为目标覆盖元素选出子路径后，从存储模块23保存的不可达路径中选出一条不可达路径，并删除存储模块23中存储的该不可达路径的记录，利用不可达路径，得到从该不可达路径中的第一个节点到目标覆盖元素组成的子路径，将给子路径发送给路径检测模块22，以及接收路径检测模块22发来的检测结果，如果检测结果为该路径为可达路径，则将该子路径作为选定的可达路径，结束操作，否则，为目标覆盖元素重新选出子路径；相应的，所述路径检测模块22，具体用于收到路径选取模块21发来的子路径后，检测子路径是否为不可达路径将检测结果发送给路径选取模块21。

所述路径检测模块22，具体用于按照数据流的方向，逐个对子路径上的节点的各个变量取值范围进行计算，若任意一个节点上的一个或多个变量的取值范围超出预置的门限值，则检测结果为该路径为不可达路径，否则，检测结果为该路径为可达路径。

所述路径选取模块21，具体用于开始为目标覆盖元素重新选出子路径时，判断当前存储模块23中是否仍保存有不可达路径，如果没有，则确定目标覆盖元素无可达路径，结束操作，否则，继续从存储模块23保存的不可达路径中选出一条不可达路径，利用不可达路径，得到从该不可达路径中的第一个节点到目标覆盖元素组成的子路径。

上述选取路径的装置可以作为应用软件安装于需要进行单元测试的设备中，比如，可以安装在个人电脑中。

以上所述，仅为本发明的较佳实施例而已，并非用于限定本发明的保护范围。

Claims (10)

1.一种选取路径的方法，其特征在于，该方法包括：

当确定为目标覆盖元素选取的初始路径为不可达路径，并且确定目标覆盖元素的重选路径为不可达路径时，利用保存的不可达路径为目标覆盖元素选出子路径，若检测出该子路径可达，则确定该子路径为目标覆盖元素的可达路径。

2.根据权利要求1所述的方法，其特征在于，所述确定为目标覆盖元素选取的初始路径为不可达路径，包括：为目标覆盖元素选取初始路径，检测初始路径是否为不可达路径，如果是，则确定为目标覆盖元素选取的初始路径为不可达路径；否则，确定初始路径作为目标覆盖元素的可达路径。

3.根据权利要求1或2所述的方法，其特征在于，所述确定为目标覆盖元素选取的初始路径为不可达路径之后，该方法还包括：为目标覆盖元素重选路径，检测重选路径是否为不可达路径，如果是，则确定重选路径为不可达路径；否则，将重选路径作为目标覆盖元素的可达路径。

4.根据权利要求3所述的方法，其特征在于，所述为目标覆盖元素重选路径，包括：

从初始路径中找到判定节点或交换节点作为当前节点，根据所述当前节点选出入口分支；

判断所述入口分支中是否包含目标覆盖元素，如果包含，则选出当前节点到出口节点之间不包括可替换节点的路径片段，将选出的路径片段补充到入口分支得到完整路径作为重选路径；

如果不包含，则判断是否存在不包括可替换位置的路径片段能够覆盖入口分支及目标覆盖元素，如果存在，则将入口分支更新为所述路径片段，选出所述路径片段最后一个节点到出口节点之间的路径片段，将选出的路径片段补充到入口分支得到完整路径作为重选路径；

如果不存在，则判断是否能够根据所述当前节点选出另一条入口分支，如果不能，则继续从初始路径中查找判定节点或交换节点作为当前节点；否则，选出另一条入口分支，继续判断所述入口分支中是否包含目标覆盖元素。

5.根据权利要求1所述的方法，其特征在于，所述利用保存的不可达路径为目标覆盖元素选出子路径，若检测出该子路径可达，则确定该子路径作为目标覆盖元素的可达路径，包括：

从保存的不可达路径中选出不可达路径，利用该不可达路径，得到从该不可达路径中的第一个节点到目标覆盖元素组成的子路径；

检测该子路径是否为不可达路径，如果不是，则确定该子路径作为目标覆盖元素的可达路径，结束处理流程；

否则，判断当前是否仍保存有不可达路径，如果没有，则结束子路径选取，确定无可达路径，结束处理流程；否则，继续从保存的不可达路径中选出不可达路径。

6.一种选取路径的装置，其特征在于，该装置包括：路径选取模块、路径检测模块和存储模块；其中，

路径选取模块，用于当确定为目标覆盖元素选取的初始路径为不可达路径，并且确定目标覆盖元素的重选路径为不可达路径时，利用存储模块保存的不可达路径为目标覆盖元素选出子路径，将子路径发送给路径检测模块，以及接收路径检测模块返回的检测结果，若检测结果为该子路径为可达路径，则确定该子路径为目标覆盖元素的可达路径；

路径检测模块，用于接收路径选取模块发来的子路径，检测该子路径是否为不可达路径，向路径选取模块发送检测结果；

存储模块，用于为路径检测模块提供保存的不可达路径。

7.根据权利要求6所述的装置，其特征在于，

所述路径选取模块，还用于为目标覆盖元素选取初始路径，将初始路径发送给路径检测模块，以及接收路径检测模块发来的检测结果，如果检测结果为该路径为不可达路径，则确定初始路径为不可达路径，否则，确定初始路径作为目标覆盖元素的可达路径；

相应的，所述路径检测模块，还用于检测路径选取模块发来的初始路径是否为不可达路径，将检测结果发送给路径选取模块。

8.根据权利要求7所述的装置，其特征在于，

所述路径选取模块，还用于为目标覆盖元素重选路径，将重选路径发送给路径检测模块，以及接收路径检测模块发来的检测结果，如果检测结果为路径是不可达路径，则确定重选路径为不可达路径，否则，将重选路径作为目标覆盖元素的可达路径；

相应的，所述路径检测模块，还用于检测路径选取模块发来的重选路径是否为不可达路径，将检测结果发送给路径选取模块。

9.根据权利要求8所述的装置，其特征在于，

所述路径选取模块，具体用于从初始路径中找到判定节点或交换节点作为当前节点，根据所述当前节点选出入口分支；

判断所述入口分支中是否包含目标覆盖元素，如果包含，则选出当前节点到出口节点之间不包括可替换节点的路径片段，将选出的路径片段补充到入口分支得到完整路径作为重选路径；

如果不包含，则判断是否存在不包括可替换位置的路径片段能够覆盖入口分支及目标覆盖元素，如果存在，则将入口分支更新为所述路径片段，选出所述路径片段最后一个节点到出口节点之间的路径片段，将选出的路径片段补充到入口分支得到完整路径作为重选路径；

如果不存在，则判断是否能够根据所述当前节点选出另一条入口分支，如果不能，则继续从初始路径中查找判定节点或交换节点作为当前节点；否则，选出另一条入口分支，继续判断所述入口分支中是否包含目标覆盖元素。

10.根据权利要求6所述的装置，其特征在于，

所述路径选取模块，具体用于从存储模块保存的不可达路径中选出不可达路径，利用不可达路径，得到从该不可达路径中的第一个节点到目标覆盖元素组成的子路径，将子路径发送给路径检测模块，以及接收路径检测模块发来的检测结果，如果检测结果为该路径为可达路径，则确定该子路径为目标覆盖元素的可达路径，结束操作，否则，判断当前存储模块是否仍保存有不可达路径，如果没有，则结束子路径选取，确定无可达路径，结束操作，否则，继续从存储模块保存的不可达路径中选出不可达路径；

相应的，所述路径检测模块，具体用于检测路径选取模块发来的子路径是否为不可达路径，将检测结果返回给路径选取模块。

Images