Zyklische Abhängigkeiten - einige Metriken

Dieser Artikel ist Teil der folgenden Serie über zyklische Abhängigkeiten. Zahlreiche Grundbegriffe, Konzepte und empirische Befunde wurden im Rahmen dieser Serie detailliert dargestellt. Der vorliegende Artikel stellt einige Metriken vor, die bei der Bewertung der Schädlichkeit von Zyklen hilfreich sein können.

Die Serie

Einführung

Terminologie

Werkzeugunterstützung für Java

Wo liegt eigentlich das Problem?

Einfluss auf Qualitätsmerkmale

Die Praxis

Verschiedene Erscheinungsformen

Zusammenhang mit der Pakethierarchie

Zusammenhang mit der Domäne

Einige Metriken (dieser Artikel)

Durchbrechung von Zyklen

Das Prinzip

In den vorausgehenden Artikeln haben wir bereits einige spezielle Zyklen-Eigenschaften besprochen, die hilfreich bei der Beurteilung von Zyklen sein können:

• Zyklen-Formen: Zyklen kommen in verschiedenen Formen vor. Einige dieser Formen sind als weniger problematisch zu beurteilen als andere. Insbesondere sind unregelmäßige Formen mit höhrerer Wahrscheinlichkeit nicht beabsichtigt und weisen ein größeres Potential auf, die negativen Effekte der Infizierbarkeit und Schwergewichtigkeit wirksam werden zu lassen.
• Die Pakethierarchie als Kontext: Die Einbettung von Paket-Zyklen in die Pakethierarchie kann Hinweise darauf geben, ob ein Zyklus schädlich ist oder nicht. Entfaltet sich ein Paket-Zyklus innerhalb eines Zweiges der Pakethierarchie, so ist es wahrscheinlich, dass die betroffenen Pakete nicht entworfen wurden, um autonom verwendet, getestet und veröffentlicht zu werden, wodurch der Aspekt der Schwergewichtigkeit an Bedeutung verliert.

In [Dietrich2014] wurde detailliert beschrieben, wie sich Zyklus-Formen und die Einbettung in die Pakethierarchie metrisch ermitteln lassen. Der vorliegende Artikel behandelt einige weitere metrisch ermittelbare Eigenschaften, so dass eine metrikbasierte (und damit werkzeuggestützte) Bewertung der Schädlichkeit von Zyklen nach und nach konkretere Gestalt annimmt.

• Größe: die Anzahl der Elemente, die in den Zyklus involviert ist
• Dichte: das Ausmaß der wechselseitigen Abhängigkeiten innerhalb des Zyklus'
• Verschachtelung: die Anzahl und Größe der Teilzyklen in einem Gesamtzyklus
• Stärke: das Ausmaß, in dem ein Zyklus sich seiner Durchbrechung widersetzt
• Durchmesser: die maximale Distanz zwischen je zwei Knotenpaaren des Zyklus'
• Direktheit: die durchschnittliche Distanz aller Knotenpaare

Größe

Die Größe eines Zyklus' ergibt sich aus der Anzahl der involvierten Elemente. Ein Zyklus ist potentiell umso problematischer, je mehr Elemente er enthält. Für physische Einheiten gestaltet sich die Situation am einfachsten: Da diese bei Anwesenheit von Zyklen gleichsam ihren Existenzgrund verlieren, liegt ihr Größenlimit bei zwei. Auch für Pakete dürfte das Limit niedriger liegen als für Klassen, zumal bspw. in [Dietrich2012] gezeigt werden konnte, dass eine Beseitigung von Paketzyklen mit vergleichsweise einfachen Mitteln bereits automatisiert zu über 98% erfolgen kann. In der folgenden Betrachtung konzentriere ich mich daher auf die Betrachtung eines Größenlimits für Klassen-Zyklen.

Bis heute existiert kein empirisch bestätigtes Größenlimit für Zyklen auf Klassen-Ebene. [Savernik2007] stuft Zyklen mit bis zu drei Klassen als "harmlos" ein. Er beruft sich auf die Studie "The magical number 4 in short-term memory. A reconsideration of mental storage capacity" [Nelson2000], um die Einstufung von Zyklen als "verbesserungswürdig" erst ab vier beteiligten Elementen zu rechtfertigen. Im Gegensatz dazu steht die sogenannte Millersche Zahl, die postuliert, dass die Anzahl der Informationseinheiten, die ein Mensch gleichzeitig präsent halten kann, bei sieben +/- zwei liegt.

Erinnern wir uns zudem an den durch die Formel n * (n - 1) charakterisierten Anstieg der Zahl der transitiven Abhängigkeiten in einem Zyklus, so ergeben sich für vier, fünf, sechs und sieben Klassen die Summen 12, 20, 30 und 42 transitiver Abhängigkeiten. Es klingt plausibel, die Größenschwelle in diesem Bereich anzusiedeln, ggf. abhängig von der jeweiligen Gesamtsituation.

Dichte

Zur Bestimmung der Dichte eines Zyklus wird die Menge der Knoten ins Verhältnis zur Menge der Kanten gesetzt. Die einfachste Kennzahl für das Knoten-/Kanten-Verhältnis ist natürlich genau

In [Dietrich2014] wird diese Metrik als RATIO bezeichnet. Ich werde im Folgenden die Anzahl der Knoten mit |V| (für vertices) notieren, die Anzahl der Kanten als |E| (für edges).

Ein Ansatz zur Normalisierung dieser Metrik besteht in folgendem Gedankengang:

• Die minimale Zahl von Kanten (minE) in einem Zyklus beträgt |V| - 1. Dies trifft auf echte Kreise zu.
• Die maximale Zahl von Kanten (maxE) in einem Zyklus beträgt |E| * (|E| - 1). Dies trifft auf Zyklen zu, die für sich genommen vollständige Graphen (oder Cliquen im Sinne von [Dietrich2014]) sind.
• Die Dichte eines Graphen muss dann zwischen minE und maxE liegen.

Dies lässt sich in folgender Formel ausdrücken:

[Dietrich2014] bezeichnet diese Metrik als DENSE. Sie ergibt 0 für einfache Kreise und 1 für vollständige Graphen. Die Autoren merken an, dass sich RATIO besser für große Zyklen eignet, während DENSE besser für kleine Zyklen arbeitet.

Nun stellt sich die Frage, wie Dichte zu interpretieren ist und ob sich analog zur Größe ein Grenzwert definieren lässt. Offensichtlich erhöht sich durch die Dichte nicht die Anzahl der transitiven Abhängigkeiten, sondern lediglich diejenige der direkten Abhängigkeiten. Wir prüfen also, ob eine Vermehrung direkter Abhängigkeiten die beiden Problemgruppen der Infizierbarkeit und Schwergewichtigkeit beeinflusst.

• Hinsichtlich der Infizierbarkeit wiegt eine direkte Abhängigkeit in jedem Fall stärker als eine transitive, da sich mit jeder zusätzlichen Indirektion die Wahrscheinlichkeit verringert, dass eine Änderung in einem Element auch tatsächlich das transitiv abhängige andere Element betrifft. 
• Die Schwergewichtigkeit ist hingegen bereits durch die transitiven Abhängigkeiten maximal, was man sich am Beispiel des Testens verdeutlichen kann. Ist A transitiv abhängig von C (wie z. B. in der Kette A -> B -> C), so wird C in jedem Fall für einen Test von A benötigt. Daran würde eine zusätzliche direkte Abhängigkeit von A zu C nichts ändern.

Eine höhere Dichte beeinflusst also insbesondere die Änderbarkeit der Zyklus-Elemente und erhöht die Wahrscheinlichkeit, dass sich bei Änderungen problematische Eigenschaften im Zyklus bemerkbar machen. Damit wird auch die Durchbrechung des Zyklus ohne unerwünschte Seiteneffekte schwieriger.

Hinsichtlich einer oberen Schranke für die Dichte betrachen wir folgende Cliquen:

Während mindestens die Cliquen aus zwei und drei Elementen noch sehr überschaubar sind, beginnt die Situation ab vier, spätestens aber ab fünf Elementen unklar zu werden. Es ist zudem schwer vorstellbar, dass derartig viele Elemente notwendigerweise in totaler Wechselwirkung zueinander stehen müssen. Dies legt die Vermutung nahe, dass die Dichte abhängig von der Größe zu betrachen ist, d. h. je größer ein Zyklus ist, desto geringer sollte der Grenzwert für die Dichte angesetzt werden. Empirische Untersuchungen zu diesem Zusammenhang existieren nach meiner Kenntnis jedoch nicht.

Verschachtelung

Die Definition von Zyklen als Strongly Connected Components (siehe Terminologie) bedingt, dass ein Zyklus aus mehreren Teilzyklen bestehen kann. Die folgende Abbildung veranschaulicht dies:

Durch das Hinzufügen von Kanten wird nicht nur die Dichte des Zyklus' erhöht, sondern es werden zusätzliche Teilzyklen eingeführt. Durch kleinere Teilzyklen wird insbesondere die Infizierbarkeit weiter erhöht: Die Distanzen zwischen den Elementen werden geringer, und damit steigt auch die Wahrscheinlichkeit, dass Änderungen oder negative Eigenschaften einzelner Elemente eine Auswirkung auf die anderen Elemente haben werden.

[Dietrich2012] definiert eine als Tangledness bezeichnete Metrik zur Messung des Verschachtelungsgrades wie folgt: Für jede Kante e zwischen zwei Knoten s und t werden alle Pfade betrachtet, die von t zurück zu s führen. Die kürzeste gefundene Pfadlänge fließt in eine Summe über alle Kanten ein. Hieraus kann ein Durchschnitt oder eine Min-Max-Normalisierung auf einen Wert zwischen 0 und 1 gebildet werden. Man beachte, dass diese kantenbasierte Zählweise mehr Zyklen erfasst als eine knotenbasierte Zählweise. Hier die normalisierte Version der Metrik:

Ist Tangledness = 1, so existiert zu jeder Kante eine direkte Rückreferenz. Bei Tangledness = 0 liegt hingegen ein echter Kreis ohne Teilzyklen vor. Ein allgemeiner Grenzwert erscheint auch für den Verschachtelungsgrad kaum als sinnvoll. Ähnlich wie für die Dichte muss aber davon ausgegangen werden, dass insbesondere bei steigender Zyklusgröße der Verschachtelungsgrad eine immer größere negative Wirkung entfaltet. Das Absenken der Schwelle bei steigender Größe erscheint daher auch hier als sinnvoll.

Zyklenstärke

Die Metrik Minimum edge feedback set size (MEFS) bestimmt diejenige kleinstmögliche Menge an Kanten, die aus dem System entfernt werden müsste, um alle Zyklen zu beseitigen. Dieses Problem ist NP-vollständig, es existieren jedoch Heuristiken, die eine Näherungslösung in guter Laufzeit ermöglichen (siehe z. B. [Melton2006]). Der Algorithmus zur Bestimmung der MEFS kann zudem zusätzliche Informationen berücksichtigen. Beispielsweise können Vererbungsbeziehungen anders behandelt werden als Nutzungsbeziehungen, da deren Beseitigung meist mit größeren Problemen verbunden ist. Auch können einzelne Beziehungen in eine Ausschlussmenge aufgenommen werden, wenn diese aus architektonischer oder fachlicher Sicht unabdingbar sind. 

Eine Variation der MEFS wird durch das Werkzeug STAN angeboten. Die dort ausgewiesene Tangled-Metrik (auf Paket-Ebene) ermittelt zunächst das Minimum edge feedback set. Diese Kanten werden auf Basis der Anzahl ihrer Einzelabhängigkeiten gewichtet, und diese Gewichte werden aufsummiert. Diese Summe wird ins Verhältnis zur Gesamtsumme aller Kantengewichte gesetzt. Es erscheint sinnvoll, diese Methode auch auf Klassen-Ebene anzuwenden. Zum einen ist der ermittelte Wert auf den Bereich zwischen 0 und 1 normalisiert und wird damit vergleichbar. Zum anderen liefert die Gewichtung auf Basis der Anzahl der Einzelabhängigkeiten mehr Information als eine ungewichtete Betrachtung.

Die folgende Konstellation veranschaulicht die unterschiedlichen Schwerpunkte von MEFS und Tangledness:

Die MEFS ist hier gleich eins, da nur eine der roten Kanten beseitigt werden müsste, um Zyklenfreiheit herzustellen. Dieser minimale Wert ignoriert die erschwerenden Auswirkungen, welche durch die diversen Teilzyklen eingebracht werden. Die Ausrichtung der MEFS liegt klar auf dem pragmatischen Aspekt. Sie liefert die Kosten-Seite einer Kosten-/Nutzen-Betrachtung. Die Nutzen-Seite wird durch die anderen Metriken beigesteuert, die zur Beurteilung der Schädlichkeit von Zyklen dienen.

Durchmesser

Der Durchmesser ist eine Pfadlängen-Metrik auf der Ebene von Zyklen. Sie wird für Zyklen unter dem Namen Diameter in [Laval2011] eingeführt. Dort basiert sie allerdings auf den Gewichten der Einzelabhängigkeiten und nicht auf der reinen Pfadlänge. Ich stelle hier die Version aus [Dietrich2014] vor, die auf Gewichte verzichtet.

Gemäß dieser Definition wird der Durchmesser eines Zyklus wie folgt ermittelt:

• Für jedes im Zyklus vorhandene Knotenpaar (s, t) wird der kürzeste Pfad zwischen s und t ermittelt. Die Länge dieses Pfades wird als Distanz bezeichnet.
• Der Durchmesser des Zyklus ist die längste gefundene Distanz über alle Knotenpaare.

Zunächst ist festzustellen, dass es sich beim Durchmesser um einen Maximalwert handelt. Dieser erfasst nicht notwendigerweise eine "typische" Eigenschaft des Zyklus, wie es beispielsweise bei einem Durchschnitt, einer Verhältniszahl oder einer Summe möglich ist, sondern er reagiert auch auf "pathologische" Deformierungen. Dies zeigt das folgende Beispiel:

Während der Teilgraph links, der eine Clique bildet, lediglich einen Durchmesser von eins hätte, vergrößert die angehängte Kette den Durchmesser des Gesamtzyklus auf fünf. Obwohl ein Großteil der Abhängigkeiten sich innerhalb der Clique befindet, reagiert der Durchmesser auf das mengenmäßig viel kleinere Anhängsel in Form der Kette. Diese Verhaltensweise trägt zwar nicht immer zur allgmeinen Charakterisierung eines Zyklus bei, sie hat aber auch Vorteile:

• Die Metrik eignet sich gut zur Festlegung eines Grenzwerts, da große Durchmesser für sich genommen immer verdächtig sind. Sehr lange Abhängigkeitsketten erweisen sich in den seltensten Fällen als notwendig.
• Große Durchmesser dürften häufig auf kreis- oder kettenförmige Teilstrukturen zurückzuführen sein, da es unwahrscheinlich ist, dass sich innerhalb von Semi-Cliquen oder Hub-Strukturen derartig lange kürzeste Pfade ergeben. Kreise und Ketten sind oftmals besonders leicht zu beseitigen, da nur wenige Kanten durchbrochen werden müssen.

Zusammenfassend lässt sich sagen, dass der Durchmesser eine vergleichsweise gute Metrik zur Erkennung potentieller Deformierungen ist. Als Maximalwert wird er idealerweise von einem Durchschnittswert flankiert, um sinnvoll zur Charakterisierung von Zyklen beitragen zu können. Dieser Durchschnittswert ist die durchschnittliche Distanz, die ich im folgenden Abschnitt unter der Bezeichnung "Direktheit" behandle.

Direktheit

Das Konzept der durchschnittlichen Distanz wurde m. W. erstmalig in [Paymal2011] zur Untersuchung objektorientierter Software-Systeme eingesetzt und wird dort (nicht ganz korrekt) als "Average Path Length" bezeichnet. Die Autoren wenden es (u. a. in Verbindung mit dem Durchmesser) zur Untersuchung der Evolution eines Software-Systems an, d. h. die Metrik arbeitet in dieser Untersuchung auf der Ebene des Gesamtsystems. Meines Wissens wurde die Metrik bislang noch nicht zur Untersuchung von Zyklen eingesetzt.

Die minimale Distanz weisen Cliquen auf; sie ist |V| - 1. Die maximale Distanz entsteht bei Kreisen; sie entspricht der Gauß'schen Summenformel für n = |V| - 1, also (|V| - 1) * |V| / 2. Daraus können wir für die durchschnittliche Distanz die folgende Min-Max-Normalisierung entwickeln, die ich als "Direktheit" bezeichne:

Die Bezeichnung leitet sich aus folgender Überlegung her: Je kleiner die durchschnittliche Distanz ist, desto größer ist der "Direktheitsgrad" innerhalb des Zyklus. Die Abhängigkeiten zwischen Knoten entstehen also nicht (nur) über lange transitive Wegstrecken im Zyklus, sondern sind entweder direkt oder nahezu direkt. Die Direktheit berücksichtigt dabei auch die Größe des Zyklus insgesamt, d. h. sie geht implizit davon aus, dass längere Distanzen in größeren Zyklen gewissermaßen "natürlich" sind.

Wie ist nun die Direktheit zu interpretieren? Offensichtlich bedeutet eine größere Direktheit, dass sich Änderungen oder Probleme vergleichsweise direkt von Knoten zu Knoten auswirken können. Folglich nimmt die Infizierbarkeit des Zyklus zu. Die Schwergewichtigkeit ist hingegen nicht betroffen, da sie bereits durch die transitiven Abhängigkeiten maximal ist. Hier gilt dieselbe Argumentation, wie sie oben im Kontext der Dichte ausgeführt wurde.

Bei der Besprechung des Durchmessers hatten wir oben erwähnt, dass dieser zur Charakterisierung eines Zyklus' durch einen Durchschnittswert flankiert werden sollte. Als "auffällig" sind dabei insbesondere hohe Durchmesser bei hoher Direktheit zu bewerten. In solchen Fällen wird eine ansonsten cliquenähnliche Struktur von einer kreis- oder kettenähnlichen Struktur ergänzt, was ungefähr wie folgt aussehen kann:

In beiden Fällen ist zu vermuten, dass derartige Anhängsel unbeabsichtigt entstanden sind und zumindest die Abhängigkeit der beiden Teilstrukturen durchbrochen werden sollte.

Zusammenfassung

Je größer ein Graph ist, desto schwerwiegender sind allgemein die Probleme der Infizierbarkeit und Schwergewichtigkeit zu bewerten. Die meisten der anderen besprochenen Metriken gewinnen daher erst im Kontext der Größe eines Graphen an Bedeutung. 

Dichte, Verschachtelungsgrad und Direktheit stehen in einem engen Zusammenhang. Mit zunehmender Dichte steigen auch der Verschachtelungsgrad und die Direktheit. Alle drei Eigenschaften beeinflussen im Wesentlichen die Infizierbarkeit, wirken aber kaum oder gar nicht auf die Schwergewichtigkeit, die bereits durch die transitiven Abhängigkeiten entsteht und damit voll etabliert ist. Wir können folgende Vergleiche zum Informationsgehalt dieser drei Eigenschaften anstellen:

• Die Direktheit enthält die meiste Information, da sie auch azyklische Pfade berücksichtigt. 
• Im Gegensatz dazu zählt der Verschachtelungsgrad nur diejenigen Pfadlängen, die zwischen Knoten mit einer direkten Abhängigkeit entstehen, somit also eine Teilmenge der Pfade, die bei der Direktheit betrachtet werden. 
• Die Dichte schließlich berücksichtigt die konkrete Struktur des Zyklus überhaupt nicht und basiert nur auf Knoten- und Kantenzählungen. 

Der genaue Zusammenhang der drei Metriken würde eine nähere Untersuchung verdienen. Sicherlich kann bei Verfügbarkeit der Direktheit auf die beiden anderen Metriken verzichtet werden. Umgekehrt können diese beiden als Näherungswerte der Direktheit interpretiert werden.

Die Zyklenstärke liefert insbesondere wertvolle Information zur Beurteilung des potentiellen Aufwandes zur Durchbrechung des Zyklus' inklusive seiner Teilzyklen.

Der Durchmesser kann in Ergänzung zur Direktheit pathologisch lange Anhängsel von ansonsten relativ dichten Teilzyklen erkennen.

In Kombination ist ein Regelwerk vorstellbar, das auf der Basis von Zyklusform, Einbettung in die Pakethierarchie, Größe, Direktheit (alternativ Dichte oder Verschachtelungsgrad) und Zyklenstärke eine priorisierte Liste von Zyklen eines Systems erzeugt. In einem späteren Artikel werde ich auf diese Möglichkeit zurückkommen.

Quellen

[Cowan2000] - The magical number 4 in short-term memory. A reconsideration of mental storage capacity, Nelson Cowan (2000)

[Dietrich2012] - Making Smart Moves to Untangle Programs, Shah, S.M.A., Dietrich, J., McCartin, C. (2012)

[Dietrich2014] - On The Shape of Circular Dependencies in Java Programs, Al-Mutawa H., Dietrich J., Marsland S., McCartin, C., Proceedings ASWEC'14, Preprint (2014)

[Laval2011] - Efficient retrieval and ranking of undesired package cycles in large software systems, Jean-Rémy Falleri, Simon Denier, Jannik Laval, Philippe Vismara, Stéphane Ducasse (2011)

[Melton2006] - An Empirical Study of Cycles among Classes in Java,  H. Melton, E. Tempero (2006)

[Paymal2011] - A Combinatorial Approach to Evaluating Modification Patterns in Software Development, Prashant Paymal, Rajvardhan Patil, Sanjukta Bhowmick, Harvey Siy (2011)

[Savernik2007] - Anatomie zyklischer Abhängigkeiten in Softwaresystemen, Savernik, Leo (2007)