Ir al contenido
Base de conocimiento

Análisis de dependencias y detección de ciclos

Esta página explica cómo determina Askalot qué ítems del cuestionario dependen de cuáles, para que se evalúen en un orden coherente, y cómo detecta las dependencias circulares que harían imposible la evaluación. El orden que se calcula aquí es también el que recorren las comprobaciones basadas en recorridos de Validación integral. El tratamiento formal de la verificación a la que este análisis sirve de base figura en el artículo revisado por pares presentado en ICAI 2026 (13th International Conference on Applied Informatics), actas, págs. 227–243, doi:10.17048/icai.2026.227.

Saber qué ítems dependen de cuáles es necesario para tres cosas:

  1. Orden de evaluación: un ítem se evalúa después de los ítems de los que depende
  2. Detección de ciclos: las dependencias circulares impiden la navegación sobre la marcha
  3. Análisis de cobertura: saber qué respuestas afectan a qué ítems posteriores

Las dependencias forman un grafo dirigido cuyos nodos son los ítems: una flecha de un ítem a otro significa que el segundo depende del primero. Un camino en este grafo es una cadena de ítems distintos, cada uno unido al siguiente por una flecha. Un ítem aislado cuenta como un camino de longitud cero.

El grafo de dependencias registra cómo fluyen los datos desde la respuesta de un ítem hasta las condiciones de otro, tanto directamente como a través de variables intermedias calculadas en bloques de código. Se construye en tres etapas.

Etapa 1: construir el grafo de flujo de datos

Sección titulada «Etapa 1: construir el grafo de flujo de datos»

El análisis estático de las precondiciones, las poscondiciones y los bloques de código produce un grafo intermedio cuyos nodos son tanto ítems como variables (respuestas de ítems y variables intermedias). Sus flechas son:

  • Responder un ítem asigna su respuesta: ítem → respuesta
  • Código que asigna una respuesta a una variable, o actualiza una variable a partir de una respuesta: respuesta → variable
  • Una variable usada en la precondición o la poscondición de un ítem: variable → ítem
  • Una respuesta usada directamente en la precondición o la poscondición de un ítem: respuesta → ítem

Etapa 2: calcular las dependencias entre ítems

Sección titulada «Etapa 2: calcular las dependencias entre ítems»

A partir del grafo de flujo de datos, el grafo de dependencias de ítems conserva solo los ítems. Un ítem depende de otro exactamente cuando el grafo de flujo de datos tiene un camino del segundo ítem al primero a través de cualquier número de variables. Así se capturan las dependencias que pasan por variables intermedias: si la respuesta de un ítem atraviesa varias variables antes de llegar a la condición de otro ítem, el segundo ítem depende del primero.

Ejemplo general: un código que asigna una variable a partir de la respuesta de un ítem, le suma después la respuesta de un segundo ítem y, por último, lee la variable en las precondiciones de otros dos ítems hace que esos dos ítems dependan de los dos primeros.

Etapa 3: ordenación topológica (algoritmo de Kahn)

Sección titulada «Etapa 3: ordenación topológica (algoritmo de Kahn)»

Un orden de evaluación válido es un orden topológico del grafo de dependencias: cada ítem va después de todos los ítems de los que depende. Askalot lo calcula con el algoritmo de Kahn:

  1. Empezar por los ítems que no dependen de nada.
  2. Tomar repetidamente uno de esos ítems, añadirlo al orden y eliminar sus flechas salientes. Todo ítem que se quede sin flechas entrantes pasa a estar disponible.
  3. Si quedan flechas cuando no hay ningún ítem disponible, el grafo tiene un ciclo; si no, el orden está completo.

En el orden resultante, cuando se llega a un ítem, todas las variables que lee su precondición ya se han asignado.

Un cuestionario no tiene ciclos cuando su grafo de dependencias es un grafo dirigido acíclico: no existe ninguna cadena de dos o más ítems distintos en la que cada uno dependa del siguiente y el último dependa del primero.

En lugar de detenerse en la primera dependencia circular, el validador continúa para que los diseñadores vean más de un problema en cada ejecución. Cada vez que el algoritmo de Kahn se bloquea, aísla un ciclo entre los ítems bloqueados, lo notifica, rompe una sola arista para superarlo y reanuda el proceso. Así muestra un ciclo representativo de cada bloqueo independiente del grafo, no solo del primero.

Cuando varios ciclos se solapan porque comparten una arista, romper esa arista compartida puede resolver más de un bloqueo a la vez, de modo que el informe enumera los ciclos suficientes para explicar cada bloqueo en lugar de enumerar todos los bucles distintos.

Cuando el algoritmo de Kahn se bloquea (todos los ítems restantes tienen un grado de entrada distinto de cero), se repite el siguiente proceso hasta procesar todos los ítems:

  1. Encontrar un ciclo entre los ítems bloqueados mediante una búsqueda en profundidad
  2. Notificar el ciclo al diseñador con la cadena completa de ítems
  3. Romper la arista de retroceso (la que va del último al primer ítem en el orden del archivo) para que el algoritmo pueda reanudarse
  4. Continuar el algoritmo de Kahn con los ítems restantes

Así se obtiene un orden de evaluación completo incluso cuando hay ciclos: los miembros de un ciclo se ordenan según su orden original en el archivo. Aunque el orden es aproximado (las dependencias rotas son errores de diseño reales), permite al validador seguir analizando el resto del cuestionario en lugar de detenerse en el primer ciclo.

Los contadores se leen en el orden del archivo, no como ciclos

Sección titulada «Los contadores se leen en el orden del archivo, no como ciclos»

Un contador que varios ítems actualizan y además leen en sus precondiciones (o en las de su bloque) parece circular si una variable se trata como un único valor: cada ítem esperaría a todos los demás. Askalot lee ese contador, un acumulador, en el orden del archivo: una precondición ve las actualizaciones de los ítems anteriores en el archivo, y el propio bloque de código de un ítem se ejecuta después de sus propias condiciones. Por tanto, la arista de un lector a un escritor posterior no es una dependencia, de modo que el ejemplo de partida (tras el tercer «No», omitir el resto del bloque) no tiene ningún ciclo, y el validador verifica su condición en cada posición.

Una variable solo cuenta como acumulador donde un ítem la lee y la escribe y esa lectura sería circular de otro modo. Una vez que una variable es un acumulador, cada lector ve los escritores anteriores en el archivo, de modo que su orden en la entrevista sigue el del archivo. Un cuestionario sin ningún acumulador de este tipo conserva su orden de dependencias sin cambios, y dos ítems condicionados cada uno a lo que solo escribe el otro, o a las respuestas del otro, siguen siendo un ciclo notificado.

Análisis de dependencias con tipos complejos

Sección titulada «Análisis de dependencias con tipos complejos»

La misma construcción se aplica a los grupos de preguntas y a las matrices. Consulte Tipos complejos para más detalles.

  • Un ítem depende de un grupo de preguntas o de una matriz cuando su precondición lee cualquier componente de la respuesta de ese ítem
  • En un grupo de preguntas, una referencia a cualquiera de sus respuestas crea la dependencia
  • En una matriz, una referencia a cualquiera de sus celdas crea la dependencia

El análisis de dependencias garantiza que los cuestionarios puedan evaluarse en un orden coherente y detecta los errores de diseño en los que las dependencias circulares harían imposible la navegación.