Seite 1 von 1

Frage zu der Definition: "Abhängigkeitsgraph"

Verfasst: 30. Mai 2011 20:33
von oren78
Hallo miteinander,

Ich hätte da eine Frage bzgl. der Definition des "Abhängigkeitsgraphen". In den Folien steht auf der Seite: 202 folgende Def.
  • \((*)\)
    alle Knoten und Kanten des Datenflussgraphen enthält (ohne Zusammenfassung von Teilgraphen zu Segmenten) sowie zusätzlich
  • \((**)\)
    .. Kanten für Pfade des Kontrollflussgraphen von allen Bedingungen zu direkt kontrollierten Anweisungen (das sind die Anweisungen, deren Ausführung von der Auswertung der betrachteten Bedingung direkt abhängt).
Das \((*)\) ist soweit kein problem, mir gehts es nur darum \((**)\) zu entschlüsseln, ich finde diese Def. leider etwas verwirrend und das Beispiel auf der nächsten Folie hat leider nicht wirklich Licht ins Dunkeln gebracht...

Könnte mir daher jemand anhand des folgenden Codefragments kurz erläutern, welche Kanten zu einem "vollständigen Abhängigkeitsgraphen" benötigt werden?

Code: Alles auswählen

01  int computeSomething(int a, int b) {
02       int retval;
03       if(b > 0)  {
04            while(b != a) {
05                     retval = retval + a + b;
06                     b--;
07            }
08            System.out.println("Result: " + retval);
09       }
10      else {
11           retval = 0;
12      }
13      return retval ;
14  }
Der dazugehörige Kontrollflussgraph:
Kontrolflussgraph.png
Kontrolflussgraph.png (217.42 KiB) 882 mal betrachtet
Sowie die dazugehörige Attribute:

n01: \(d(a),\; d(b)\)
n02: \(u(retval)\)
n03: \(p(b)\)
n04: \(c(a),\; p(b)\)
n05: \(c(retval),\; c(a), \; c(b), \; d(retval)\)
n06: \(c(b),\; d(b)\)
n08: \(c(retval)\)
n11: \(d(retval)\)
n13: \(c(retval),\; c(retval),\; u(retval) \; u(a), \; u(b)\)

und schließlich der dazugehörige Datenflussgraph:
Datenflussgraph.png
Datenflussgraph.png (424.56 KiB) 882 mal betrachtet

Re: Frage zu der Definition: "Abhängigkeitsgraph"

Verfasst: 31. Mai 2011 08:11
von blackcomb
Hallo,

die aufgrund direkt kontrollierter Anweisungen (**) zum Abhängigkeitsgraph gehörigen Kanten müssten die folgenden sein:
  • n03 --> n04, n03 --> n08, n03 --> n11 (denn n04, n08 und n11 sind Anweisungen, die direkt von der Auswertung der Bedingung in n03 abhängen; dagegen hängen n05 und n06 nur indirekt ab, da noch eine zusätzliche Bedingung dazwischen ist)
  • n04 --> n05, n04 --> n06 (denn n05 und n06 hängen direkt von der Bedingung in n04 ab)
Außerdem gehören natürlich, wie du sagtest, die Datenflusskanten dazu (*).

Re: Frage zu der Definition: "Abhängigkeitsgraph"

Verfasst: 31. Mai 2011 16:33
von oren78
blackcomb hat geschrieben:Hallo,

die aufgrund direkt kontrollierter Anweisungen (**) zum Abhängigkeitsgraph gehörigen Kanten müssten die folgenden sein:
  • n03 --> n04, n03 --> n08, n03 --> n11 (denn n04, n08 und n11 sind Anweisungen, die direkt von der Auswertung der Bedingung in n03 abhängen; dagegen hängen n05 und n06 nur indirekt ab, da noch eine zusätzliche Bedingung dazwischen ist)
  • n04 --> n05, n04 --> n06 (denn n05 und n06 hängen direkt von der Bedingung in n04 ab)
Außerdem gehören natürlich, wie du sagtest, die Datenflusskanten dazu (*).
Super vielen dank, ich glaub jetzt verstehe ich endlich die Def. ;-)