Ansicht
Dokumentation

CL_TCL_GRAPH_BREADTH_FIRST_IT - Breadth-First Iteration über alle Knoten eines Graphen

BAL Application Log Documentation   ABAP Short Reference  
Diese Dokumentation steht unter dem Copyright der SAP AG.

Funktionalität

Die Klasse CL_TCL_GRAPH_BREADTH_FIRST_ITist eine spezialisierte Iterator-Klasse um eine Graphen der Klasse CL_TCL_GRAPHzu traversieren. Der Iterator folgt den Verweisen in den Adjazenz-Listen von Knoten der Klasse CL_TCL_VERTEX. Daher benötigt der Iterator einen Startpunkt, von dem aus die Iteration beginnen soll. Dieser Startpunkt ist ein Knoten innerhalb des Graphen und wird bei der Instanziirung dieser Klasse festgelegt. Knoten, die nicht über den Startpunkt und alle folgenden Knoten erreicht werden können, bleiben unberührt. Jeder Knoten wird nur einmal traversiert.

Dieser Graphen-Iterator verfolgt die Suchstrategie Breitensuche(engl. breadth-first). Ausgehend von einem Startknoten betrachtet man zuerst alle benachbarten Knoten (d.h. auf dem gleichen Level), bevor man einen Schritt weitergeht. Dies entspricht der Levelorder Traversierung bei Bäumen.

Eine allgemeine Einführung in Graphen-Algorithmen würde den Rahmen dieser Dokumentation sprengen. Wir empfehlen daher einschlägige Dokumentationen.

Beziehungen

Diese Klasse ist eine Spezialisierung der Klasse CL_TCL_GRAPH_ITERATOR.

Beispiel

Ein ausführliches Beispiel finden sie im Programm TCL_GRAPH_EXAMPLE.

Hinweise

Die Iterator-Klassen für Graphen verwenden ein BOOL-Flag in der Klasse CL_TCL_VERTEX. Dieses Flag dient dazu, um sicherzustellen, dass ein Knoten (engl. vertex) nur einmal traversiert wird. Sobald einer der Iteratoren für einen Graphen instanziiert wird, wird dieses Flag in allen Knoten des Graphen initialisiert. Deshalb kann immer nur eine Instanz der Iteratoren je Graphen-Instanz verwendet werden! Sobald eine zweite Instanz instanziiert wird, benutzen beide Iteratoren konkurierend dieses eine Flag in den Knoten, was zu unerwünschten Laufzeitverhalten führen wird.

Da diese Klasse auf der Klasse CL_TCL_ITERATOR basiert, erbt sie einige Methoden, die im Kontext dieser Klasse nicht sinnvoll sind. Aus diesem Grund werfen diese Methoden die Ausnahme CX_TCL_NOT_SUPPORTED.

Weiterführende Informationen

Wer sich intensiver mit dem Thema Graphen beschäftigen möchte, dem können wir folgende Fachbücher empfehlen:

• Algorithemen und Datenstrukturen / K.H. Böhling, U. Kulisch, H. Maurer

• An Introduction to the Analysis of Algorithms / Robert Sedgewick

ROGBILLS - Synchronize billing plans   General Material Data  
Diese Dokumentation steht unter dem Copyright der SAP AG.

Length: 3127 Date: 20240424 Time: 052759     sap01-206 ( 56 ms )