Kontrollflussgraph - LinkFang.de





Kontrollflussgraph


Dieser Artikel bedarf einer Überarbeitung.

Ein Kontrollflussgraph ist ein Begriff aus der Informatik und bezeichnet einen gerichteten Graphen der dazu dient, den Kontrollfluss eines Computerprogramms zu beschreiben. Sie werden unter anderem zur Programmoptimierung eingesetzt [1].

Aufbau

Jeder Kontrollflussgraph besteht aus

  • einer Menge von Knoten [math]V[/math], die Instruktionen darstellen,
  • dem Wurzelknoten [math]r\in V[/math], an dem die Ausführung beginnt, und
  • einer Menge von gerichteten Kanten [math]E[/math], die mögliche Übergänge, d. h. Programmabläufe darstellen.

Die Schreibweise lautet [math]G\langle V,E,r\rangle[/math].

Den Wurzelknoten kann man sich als Startpunkt des Computer-Programmes, den Exit-Knoten als seinen Endpunkt vorstellen.

Wenn von einem Knoten mehrere Kanten wegführen (der Knoten also Quelle mehrerer gerichteter Kanten ist), so entspricht das einer Verzweigung. Schleifen finden sich als Zyklen in Kontrollflussgraphen wieder. Beispielsweise zeigt der Zyklus [math]B\to C\to E\to D\to B[/math] im unten abgebildeten Graph [math]G_2\langle V,E,A\rangle[/math] an, dass im zugrundeliegenden Computer-Programm eine Schleife enthalten ist.

Formale Anforderungen an Kontrollflussgraphen

In jedem Kontrollflussgraphen muss es von [math]r[/math] zu jedem anderen Knoten [math]u\in V[/math] einen Pfad geben.

Der oben dargestellte Graph [math]G_1\langle V,E,A\rangle[/math] ist kein Kontrollflussgraph, da es keinen Pfad von [math]A[/math] nach [math]G[/math] gibt.

Dieser Graph [math]G_2\langle V,E,A\rangle[/math] ist ein Kontrollflussgraph, da es von [math]A[/math] zu jedem anderen Knoten einen Pfad gibt. So gibt es zum Beispiel folgenden Pfad von [math]A[/math] nach [math]D[/math]: [math]A\to B\to C\to E\to D[/math].

Manchmal wird auch gefordert, dass der Wurzelknoten [math]r[/math] keine einkommenden Kanten haben darf, also nicht Ziel einer gerichteten Kante sein darf.

Darüber hinaus zeichnet man manchmal auch einen Exit-Knoten [math]x\in V[/math] eines Kontrollflussgraphen [math]G\langle V,E,r,x \rangle[/math] aus. Dann muss es von jedem Knoten [math]u\in V[/math] einen Pfad zu [math]x[/math] geben.

Siehe auch

Einzelnachweise

  1. : Masking wrong-successor Control Flow Errors employing data redundancy . IEEE, S. 201–205. doi:10.1109/ICCKE.2015.7365827

Kategorien: Softwarearchitektur | Compilerbau | Gerichteter Graph

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Kontrollflussgraph (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.