Mise en œuvre de la couverture tous-chemins-indépendants.
Pour atteindre ce niveau de couverture, le testeur va s’attacher à déterminer un ensemble de cas de test permettant d’activer un ensemble de chemins constituant une base de chemins indépendants. Une base de chemins indépendants comprend des chemins linéairement indé- pendants (aucun ne peut s’exprimer comme combinaisons linéaire des autres) qui ensemble permettent de représenter tous les chemins du graphe de flot de contrôle. Le nombre de chemins dans la base est donné par la complexité cyclomatique du graphe (aussi connue sous le nom de mesure de McCabe [McC76]). Ce nombre, noté ν(G) pour un graphe G, est calculé de l’une des deux façons (équivalentes) suivantes :
Pour déterminer que des chemins de contrôle sont linéairement indépendants, il faut vérifier qu’aucun ne peut s’exprimer comme combinaison linéaire des autres. Pour ceci, il faut établir le vecteur de chaque chemin sur la base des arcs du graphe. Les composantes du vecteur d’un chemin sont le nombre de fois que le chemin emprunte l’arc. Les vecteurs ainsi constitués sont linéairement indépendants s’ils vérifient :
$$ ∀(a1,···,an)∈ℕn,(a1v1+···+anvn =0 ⇒ a1 = a2 =···= an =0) $$
On montre facilement que partant d’un ensemble de chemins linéairement indépendants, si l’on ajoute un chemin qui contient un arc qu’il est le seul à couvrir, alors l’ensemble de chemins reste linéairement indépendant. En effet, sur la composante correspondant à l’arc propre au chemin, seul le vecteur du chemin aura une composante non nulle. On aura alors pour cette composante une équation a1·0+···+aivij +···+an·0=0 qui devient aivij =0 donc ai =0.
La construction de l’ensemble de chemins indépendants se fait incrémentalement en commençant par un ensemble de 1 chemin et en ajoutant 1 à 1 les chemins jusqu’à en avoir ν(G), en vérifiant à chaque ajout que l’ensemble reste linéairement indépendant. Ainsi, lors de la construction de l’ensemble de chemins, on s’attache à tenter de préserver la propriété énoncée avant, de sorte que la vérification de l’indépendance linéaire soit la plus aisée le plus longtemps. Pour ce faire, il faut privilégier le chemin le plus court d’abord, c’est-à-dire celui qui couvre le moins d’arcs. Puis, à chaque nouvel ajout, on cherche à produire un chemin couvrant un arc non encore couvert tout en essayant de préserver des arcs non couverts pour les chemins suivants. Malheureusement, il est fréquent que la couverture de tous-les-arcs soit atteinte avant d’avoir intégré suffisamment de chemins indépendants à la base. Il faut alors user d’un peu d’intuition pour produire un chemin et vérifier par résolution du système d’équations de l’indépendance linéaire de l’ensemble.
<aside> ❓ Choisissez parmi les exercices 1 et 2 du TD4, celui qui contient un graphe adapté à l'application d'une stratégie de couverture de tous-chemins-indépendants et produisez les cas de test permettant d'atteindre cette couverture.
</aside>
Parmi ces deux graphes, une différence existe au niveau du nœud b, ce dernier possède deux conditions élémentaires dans la graphe soleil tandis qu’il n’en possède qu’une seule dans le graphe lune. Puisque l’on souhaite obtenir une couverture tous-chemin-indépendant, il faut isoler chaque condition élémentaire.
De sorte a pouvoir calculer le nombre de mcCabe comme dans le cas du graphe suivant :
On va donc choisir le graphe lune.
β1 : abikl "" 3 [] BRAVO
β2 : abijl "" 0 [] echec
β3 : abcijl "bleu" 0 [] echec
β4 : ab(cdefghb)⁴ihl "bleu" 1 ['e','u','l','b'] BRAVO
β5 : abcdefghbcijl "bleu" 1 ['a'] echec