Tovább a tartalomhoz
Tudástár

Függőségelemzés és ciklusfelismerés

Ez az oldal azt mutatja be, hogyan deríti ki az Askalot, hogy a kérdőív elemei közül melyik melyiktől függ, hogy az elemeket következetes sorrendben lehessen kiértékelni, és hogyan ismeri fel azokat a körkörös függőségeket, amelyek lehetetlenné tennék a kiértékelést. Az itt kiszámított sorrendet járják be az Átfogó ellenőrzés útvonalalapú vizsgálatai is. Az erre épülő ellenőrzés formális tárgyalása az ICAI 2026 konferencián (13th International Conference on Applied Informatics) bemutatott, lektorált tanulmányban található, a konferenciakötet 227–243. oldalán, doi:10.17048/icai.2026.227.

Három dologhoz kell tudni, melyik elem melyiktől függ:

  1. Kiértékelési sorrend: a rendszer egy elemet azok után értékel ki, amelyektől függ
  2. Ciklusfelismerés: a körkörös függőségek lehetetlenné teszik a menet közbeni navigációt
  3. Lefedettségelemzés: annak ismerete, hogy mely válaszok mely későbbi elemekre hatnak

A függőségek irányított gráfot alkotnak, amelynek csúcsai az elemek: az egyik elemtől a másikig mutató nyíl azt jelenti, hogy a második az elsőtől függ. Ebben a gráfban az út különböző elemek lánca, amelyben mindegyiket nyíl köti a következőhöz. Egyetlen elem önmagában nulla hosszúságú útnak számít.

A függőségi gráf azt rögzíti, hogyan áramlik az adat az egyik elem válaszától egy másik elem feltételeihez, közvetlenül és a kódblokkokban számított köztes változókon keresztül is. Három lépésben épül fel.

1. lépés: az adatfolyamgráf felépítése

Szekció neve “1. lépés: az adatfolyamgráf felépítése”

Az elő- és utófeltételek, valamint a kódblokkok statikus elemzése egy köztes gráfot eredményez, amelynek csúcsai egyaránt elemek és változók (elemválaszok és köztes változók). A nyilai a következők:

  • Egy elem megválaszolásakor a válasza értéket kap: elem → válasz
  • Kód, amely egy választ változóhoz rendel, vagy egy változót válasz alapján frissít: válasz → változó
  • Egy elem elő- vagy utófeltételében használt változó: változó → elem
  • Egy elem elő- vagy utófeltételében közvetlenül használt válasz: válasz → elem

2. lépés: az elemek közötti függőségek kiszámítása

Szekció neve “2. lépés: az elemek közötti függőségek kiszámítása”

Az adatfolyamgráfból képzett elemfüggőségi gráf csak az elemeket tartja meg. Egy elem pontosan akkor függ egy másiktól, ha az adatfolyamgráfban akárhány változón át vezet út a második elemtől az elsőig. Így a köztes változókon áthaladó függőségek is rögzülnek: ha egy elem válasza több változón halad át, mielőtt egy másik elem feltételéhez érne, a második elem az elsőtől függ.

Általános példa: ha a kód egy elem válaszából beállít egy változót, majd hozzáadja egy második elem válaszát, végül két másik elem előfeltételében olvassa a változót, akkor ez a két elem mindkét első elemtől függ.

3. lépés: topologikus rendezés (Kahn algoritmusa)

Szekció neve “3. lépés: topologikus rendezés (Kahn algoritmusa)”

Az érvényes kiértékelési sorrend a függőségi gráf egy topologikus rendezése: minden elem az összes olyan elem után következik, amelytől függ. Az Askalot Kahn algoritmusával számítja ki:

  1. Az induló elemek azok, amelyek semmitől sem függenek.
  2. Ismételten vegyünk ki egy ilyen elemet, fűzzük a sorrend végére, és töröljük a kimenő nyilait. Minden olyan elem, amelynek nem marad bejövő nyila, ezután maga is kivehető.
  3. Ha még maradnak nyilak, de már egyetlen elem sem vehető ki, a gráfban ciklus van; különben a sorrend teljes.

Az így kapott sorrendben egy elem elérésekor minden változó, amelyet az előfeltétele olvas, már értéket kapott.

Egy kérdőívben nincsenek ciklusok, ha a függőségi gráfja irányított körmentes gráf: nincs két vagy több különböző elemből álló olyan lánc, amelyben mindegyik a következőtől függ, az utolsó pedig az elsőtől.

Minden ciklus jelzése, nem csak az elsőé

Szekció neve “Minden ciklus jelzése, nem csak az elsőé”

A validátor nem áll meg az első körkörös függőségnél, hanem továbbhalad, hogy a tervezők egyetlen futtatásból több problémát is lássanak. Valahányszor Kahn algoritmusa elakad, a beragadt elemek közül elkülönít egy ciklust, jelzi, egyetlen él megszakításával továbblép rajta, majd folytatja. Így a gráf minden független holtpontjára felmutat egy jellemző ciklust – nem csak az elsőre.

Ha több ciklusnak közös éle van, ennek a közös élnek a megszakítása egyszerre több holtpontot is feloldhat, ezért a jelentés annyi ciklust sorol fel, amennyi minden elakadás magyarázatához elegendő, nem pedig minden egyes hurkot.

Amikor Kahn algoritmusa elakad (az összes megmaradt elem bemeneti foka nullánál nagyobb), a következő folyamat ismétlődik, amíg az algoritmus minden elemet fel nem dolgoz:

  1. Egy ciklus megkeresése a beragadt elemek között mélységi kereséssel
  2. A ciklus jelzése a tervezőnek a teljes elemlánccal együtt
  3. A visszafelé mutató él megszakítása (a fájlbeli sorrendben utolsó elemtől az elsőig mutató élé), hogy az algoritmus folytatódhasson
  4. Kahn algoritmusának folytatása a megmaradt elemekkel

Ez ciklusok jelenlétében is teljes kiértékelési sorrendet ad – a ciklus tagjai eredeti fájlbeli sorrendjükben kerülnek egymás után. Bár a sorrend csak közelítő (a megszakított függőségek valódi tervezési hibák), így a validátor nem áll meg az első ciklusnál, hanem a kérdőív többi részét is elemzi.

A számlálókat a rendszer fájlbeli sorrendben olvassa, nem ciklusként

Szekció neve “A számlálókat a rendszer fájlbeli sorrendben olvassa, nem ciklusként”

Az a számláló, amelyet több elem frissít és az előfeltételeikben (vagy a blokkjukéban) olvas is, körkörösnek tűnik, ha a változót egyetlen értékként kezeljük: minden elem az összes többire várna. Az Askalot az ilyen számlálót, az úgynevezett akkumulátort, ehelyett fájlbeli sorrendben olvassa: egy előfeltétel a fájlban előtte álló elemek frissítéseit látja, és egy elem saját kódblokkja a saját feltételei után fut le. Az olvasótól egy későbbi íróig mutató él ezért nem függőség, így a kiinduló példában (a harmadik „Nem” után a blokk hátralévő része kimarad) nincs ciklus, és a validátor minden pozícióban ellenőrzi a feltételt.

Egy változó csak ott számít akkumulátornak, ahol egy elem olvassa és írja is, és ez az olvasás egyébként körkörös volna. Ha egy változó akkumulátor, minden olvasója a fájlban előtte álló írókat látja, így a kitöltés során a sorrendje a fájlt követi. Az ilyen akkumulátor nélküli kérdőív függőségi sorrendje változatlan marad, az a két elem pedig, amelyek mindegyike olyasmitől függ, amit csak a másik ír, vagy amelyek egymás válaszaitól függenek, továbbra is ciklusként jelenik meg a jelentésben.

Függőségelemzés összetett típusokkal

Szekció neve “Függőségelemzés összetett típusokkal”

Ugyanez a felépítés érvényes a kérdéscsoportokra és a mátrixokra. A részleteket az Összetett típusok oldal tartalmazza.

  • Egy elem akkor függ egy kérdéscsoporttól vagy mátrixtól, ha az előfeltétele a válaszának bármelyik összetevőjét olvassa
  • Kérdéscsoport esetén bármelyik válaszára való hivatkozás létrehozza a függőséget
  • Mátrix esetén bármelyik cellájára való hivatkozás létrehozza a függőséget

A függőségelemzés biztosítja, hogy a kérdőívek következetes sorrendben kiértékelhetők legyenek, és felismeri azokat a tervezési hibákat, amelyeknél a körkörös függőségek lehetetlenné tennék a navigációt.