[Sq10] McCabe-Überdeckung, Elementarpfade

[Wolfgang Runte]

Hallo SQler,

damit die Vektoren für die McCabe-Überdeckung nicht unnötig lang
werden, solltet Ihr den Kontrollflussgraphen möglichst kompakt halten:

- sequentielle Anweisungen jeweils zu einem Knoten zusammenfassen
- Verzweigungsbedingungen können mit vorhergehenden sequentiellen
  Anweisungen zusammengefasst werden
- Schleifenbedingungen von abweisenden Schleifen müssen allerdings als
  separater Knoten dargestellt werden

... auf den Start- und den Final-Knoten ("n_start" und "n_final")
kann diesmal ebenfalls verzichtet werden. Es macht bei der Berechnung
der "zyklomatischen Komplexität" keinen Unterschied, verringert aber
den Umfang der Elementarpfade. Ich komme somit auf 10-stellige
Vektoren.

Zur Erzeugung und Nutzung der Elementarpfade:

(1) Zuerst unter Ausklammerung der Schleife vier unabhängige Pfade
bilden, die jeweils eine der vier möglichen Kombinationen (zwei
"if"-Bedingungen) durchlaufen.

(2) Von diesen vier Pfaden muss einer um einen Schleifendurchlauf
ergänzt werden (müssten zwei zusätzliche Kanten im Graph sein).

(3) Werden für eine Linearkombination mehrere Schleifendurchläufe
benötigt, bekommt der entsprechende Elementarpfad, der die Schleife
enthält, einen entsprechenden Multiplikator/Koeffizienten verpasst.

(4) Wenn insgesamt ein anderer Pfad um die Schleife umzu benötigt
wird, muss in der Linearkombination ein passender Elementarpfad (der
den jeweils "unerwünschten" (Teil-)Pfad um die Schleife umzu
beschreibt) mit einem entsprechenden Koeffizienten abgezogen und im
Gegenzug ein anderer Elementarpfad mit positivem Koeffizienten
hinzugenommen werden (um den "fehlenden" (Teil-)Pfad ausserhalb der
Schleife zu erhalten).

(5) Gleiches Vorgehen ("Abziehen" und "Ergänzen" der äußeren
Teilpfade), wenn genau der Pfad durchlaufen werden soll, der im
Elementarpfad mit der Schleife um die Schleife umzu besteht. In diesem
Fall allerdings müssen die Koeffizienten der Elementarpfade mit den
"abzuziehenden" (Teil-)Pfaden je nach Anzahl der benötigten Durchläufe
entsprechend kleinere Multiplikatoren sein, damit die in diesem Fall
"erwünschten" äußeren (Teil-)Pfade bestehen bleiben.

Viele Grüße
Wolfgang


-- 
Dipl.-Inf. Wolfgang Runte              woru at informatik.uni-osnabrueck.de
Institut für Informatik                +49-541-969-2487 (Fon)
Universität Osnabrück                  +49-541-969-2799 (Fax)
Albrechtstraße 28, Raum 31/317         http://www.inf.uos.de/woru
D-49069 Osnabrück