Analyse des dépendances et détection des cycles
Cette page explique comment Askalot détermine quels items du questionnaire dépendent de quels autres, afin de les évaluer dans un ordre cohérent, et comment il détecte les dépendances circulaires qui rendraient l’évaluation impossible. L’ordre calculé ici est aussi celui que parcourent les vérifications par chemin décrites dans la Validation complète du questionnaire. Le traitement formel de la vérification qu’il permet figure dans l’article évalué par les pairs présenté à l’ICAI 2026 (13th International Conference on Applied Informatics), actes p. 227–243, doi:10.17048/icai.2026.227.
Présentation
Section intitulée « Présentation »Savoir quels items dépendent de quels autres sert à trois choses :
- Ordre d’évaluation : un item est évalué après les items dont il dépend
- Détection des cycles : les dépendances circulaires rendent impossible la navigation à la volée
- Analyse de couverture : savoir quelles réponses influent sur quels items ultérieurs
Chemin dans le graphe de dépendances
Section intitulée « Chemin dans le graphe de dépendances »Les dépendances forment un graphe orienté dont les nœuds sont les items : une flèche d’un item vers un autre signifie que le second dépend du premier. Un chemin dans ce graphe est une chaîne d’items distincts, chacun relié au suivant par une flèche. Un item isolé compte comme un chemin de longueur nulle.
Construction du graphe de dépendances
Section intitulée « Construction du graphe de dépendances »Le graphe de dépendances décrit comment les données circulent de la réponse d’un item vers les conditions d’un autre item, directement ou par l’intermédiaire de variables calculées dans des blocs de code. Il se construit en trois étapes.
Étape 1 : construire le graphe de flux de données
Section intitulée « Étape 1 : construire le graphe de flux de données »L’analyse statique des préconditions, des postconditions et des blocs de code produit un graphe intermédiaire dont les nœuds sont à la fois des items et des variables (réponses des items et variables intermédiaires). Ses flèches sont les suivantes :
- répondre à un item fixe sa réponse : item → réponse ;
- du code qui affecte une réponse à une variable, ou met à jour une variable à partir d’une réponse : réponse → variable ;
- une variable utilisée dans la précondition ou la postcondition d’un item : variable → item ;
- une réponse utilisée directement dans la précondition ou la postcondition d’un item : réponse → item.
Étape 2 : calculer les dépendances entre items
Section intitulée « Étape 2 : calculer les dépendances entre items »À partir du graphe de flux de données, le graphe de dépendances des items ne conserve que les items. Un item dépend d’un autre si et seulement si le graphe de flux de données comporte un chemin allant du second item au premier, à travers un nombre quelconque de variables. Les dépendances qui passent par des variables intermédiaires sont donc prises en compte : si la réponse d’un item traverse plusieurs variables avant d’atteindre la condition d’un autre item, ce second item dépend du premier.
Exemple général : du code qui initialise une variable avec la réponse d’un item, lui ajoute la réponse d’un deuxième item, puis lit cette variable dans les préconditions de deux autres items rend chacun de ces deux items dépendant des deux premiers.
Étape 3 : ordre topologique (algorithme de Kahn)
Section intitulée « Étape 3 : ordre topologique (algorithme de Kahn) »Un ordre d’évaluation valide est un ordre topologique du graphe de dépendances : chaque item vient après tous les items dont il dépend. Askalot le calcule avec l’algorithme de Kahn :
- Partir des items qui ne dépendent de rien.
- Tant qu’il en reste, prendre l’un de ces items, l’ajouter à l’ordre et supprimer ses flèches sortantes. Tout item qui n’a plus de flèche entrante devient à son tour disponible.
- S’il reste des flèches alors qu’aucun item n’est disponible, le graphe comporte un cycle ; sinon, l’ordre est complet.
Dans l’ordre obtenu, lorsqu’un item est atteint, toutes les variables que lit sa précondition ont déjà été affectées.
Détection des cycles
Section intitulée « Détection des cycles »Un questionnaire est sans cycle lorsque son graphe de dépendances est un graphe orienté acyclique : il n’existe aucune chaîne d’au moins deux items distincts dans laquelle chacun dépend du suivant et le dernier dépend du premier.
Signaler tous les cycles, pas seulement le premier
Section intitulée « Signaler tous les cycles, pas seulement le premier »Au lieu de s’arrêter à la première dépendance circulaire, le validateur poursuit son travail afin que les concepteurs voient plusieurs problèmes à chaque exécution. Chaque fois que l’algorithme de Kahn se bloque, il isole un cycle parmi les items bloqués, le signale, rompt un seul arc pour le dépasser, puis reprend. Il fait ainsi apparaître un cycle représentatif pour chaque blocage indépendant du graphe, et pas seulement pour le premier.
Lorsque plusieurs cycles se chevauchent en partageant un arc, rompre cet arc commun peut lever plusieurs blocages à la fois : le rapport énumère donc assez de cycles pour expliquer chaque blocage, sans pour autant lister chaque boucle distincte.
Lorsque l’algorithme de Kahn se bloque (tous les items restants ont un degré entrant non nul), le processus suivant se répète jusqu’à ce que tous les items soient traités :
- Trouver un cycle parmi les items bloqués, par un parcours en profondeur
- Signaler le cycle au concepteur avec la chaîne complète des items
- Rompre l’arc arrière (l’arc qui va du dernier au premier item dans l’ordre du fichier) pour permettre à l’algorithme de reprendre
- Poursuivre l’algorithme de Kahn avec les items restants
On obtient ainsi un ordre d’évaluation complet même en présence de cycles : les membres d’un cycle sont linéarisés dans leur ordre d’origine dans le fichier. L’ordre n’est qu’approximatif (les dépendances rompues sont de véritables erreurs de conception), mais il permet au validateur de poursuivre l’analyse du reste du questionnaire au lieu de s’arrêter au premier cycle.
Les compteurs se lisent dans l’ordre du fichier, pas comme des cycles
Section intitulée « Les compteurs se lisent dans l’ordre du fichier, pas comme des cycles »Un compteur que plusieurs items mettent à jour et lisent aussi dans leurs préconditions (ou dans celles de leur bloc) paraît circulaire si l’on traite une variable comme une valeur unique : chaque item attendrait tous les autres. Askalot lit plutôt un tel compteur, un accumulateur, dans l’ordre du fichier : une précondition voit les mises à jour des items qui la précèdent dans le fichier, et le bloc de code propre à un item s’exécute après ses propres conditions. L’arc qui va d’un lecteur vers un rédacteur ultérieur n’est donc pas une dépendance : l’exemple de départ (après le troisième « Non », sauter le reste du bloc) ne comporte aucun cycle, et le validateur vérifie sa condition à chaque position.
Une variable n’est considérée comme un accumulateur que là où un item la lit et l’écrit à la fois, et où cette lecture serait sinon circulaire. Dès qu’une variable est un accumulateur, chacun de ses lecteurs voit les rédacteurs qui le précèdent dans le fichier, si bien que son ordre dans l’entretien suit le fichier. Un questionnaire sans accumulateur de ce type conserve son ordre de dépendances inchangé, et deux items conditionnés chacun par ce que seul l’autre écrit, ou par leurs réponses mutuelles, restent un cycle signalé.
Analyse des dépendances avec les types complexes
Section intitulée « Analyse des dépendances avec les types complexes »La même construction s’applique aux groupes de questions et aux matrices. Voir Extension aux types d’items vecteur et matrice pour plus de détails.
- Un item dépend d’un groupe de questions ou d’une matrice lorsque sa précondition lit une composante quelconque de la réponse de cet item
- Pour un groupe de questions, une référence à l’une quelconque de ses réponses crée la dépendance
- Pour une matrice, une référence à l’une quelconque de ses cellules crée la dépendance
L’analyse des dépendances garantit que les questionnaires peuvent être évalués dans un ordre cohérent et détecte les erreurs de conception dans lesquelles des dépendances circulaires rendraient la navigation impossible.
Pour aller plus loin
Section intitulée « Pour aller plus loin »- Analyse de questionnaires : fondements - Définitions et notation
- Préconditions et postconditions - Atteignabilité et classification des contraintes
- Extension aux types d’items vecteur et matrice - Extensions aux items vecteur et matrice, avec dépendances au niveau des composantes
- Validation complète du questionnaire - Relation entre les vérifications par item et les vérifications globales