Reduzierbarer und irreduzierbarer Kontrollflussgraph

Die Menge der Kontrollflussgraphen kann in reduzierbare und irreduzierbare Kontrollflussgraphen partitioniert (geteilt) werden. Diese Einteilung geht auf Frances E. Allen zurück.<ref>Frances E. Allen: Control flow analysis. In: SIGPLAN Notices. Band 5, Nr. 7, Juli 1970, S. 1–19. </ref> Hecht und Ullman geben äquivalente Charakterisierungen zu Allens ursprünglicher Definition und benutzen diese, um zu zeigen, dass strukturierte Kontrollstrukturen stets reduzierbare Kontrollflussgraphen erzeugen.<ref>Matthew S. Hecht, Jeffrey D. Ullman: Flow Graph Reducibility. In: STOC. 1972, S. 238–250. </ref> Eine Auflistung alternativer Charakterisierungen findet sich in einer späteren Veröffentlichung.<ref>Matthew S. Hecht, Jeffrey D. Ullman: Characterizations of Reducible Flow Graphs. In: Journal of the ACM. Band 21, Nr. 3, Juli 1974, S. 367–375. </ref>

Ein für die Definition eines reduzierbaren Kontrollflussgraphen wichtiger Begriff ist der einer Rückwärtskante (engl. backedge). Wenn man im Zuge einer Tiefensuche eines Kontrollflussgraphen <math>G\langle V,E,r\rangle</math>, die beim Knoten <math>r</math> startet, ausgehend von einem Knoten <math>u</math> entlang der Kante <math>u\to v</math> zu einem Knoten <math>v</math> gelangt, der schon entdeckt worden ist, so nennt man die Kante <math>u\to v</math> Rückwärtskante.

Ein Kontrollflussgraph <math>G\langle V,E,r\rangle</math> ist genau dann reduzibel, wenn er eine der folgenden drei (untereinander äquivalenten) Bedingungen erfüllt.

Jede Tiefensuche findet dieselbe Menge an Rückwärtskanten.
Sei <math>u\to v</math> eine Rückwärtskante. Dann dominiert <math>v</math> den Knoten <math>u</math>.
<math>G</math> enthält keinen Untergraphen der Form Datei:ICFG.svg, wobei die eingezeichneten gestrichelten Kanten Pfade repräsentieren.

Nicht reduzierbare Kontrollflussgraphen nennt man irreduzierbar.

Die Unterscheidung in reduzierbare und irreduzierbare Kontrollflussgraphen ist in der Informatik insofern von Interesse, als für reduzierbare Kontrollflussgraphen im Allgemeinen effizientere Algorithmen existieren.

Bibliographie