Ansicht
Dokumentation

CL_TCL_GRAPH_SHORTEST_PATH_IT - Depth-First Iteration über alle Knoten eines Graphen

General Material Data   SUBST_MERGE_LIST - merge external lists to one complete list with #if... logic for R3up  
Diese Dokumentation steht unter dem Copyright der SAP AG.

Funktionalität

Die Klasse CL_TCL_GRAPH_SHORTEST_PATH_ITist eine spezialisierte Iterator-Klasse um einen Graphen der Klasse CL_TCL_GRAPH zu traversieren. Der Iterator folgt den Verweisen in den Adjazenz-Listen von Knoten der Klasse CL_TCL_VERTEX. Der Iterator benötigt einen Startpunkt, von dem aus die Iteration beginnen soll und einen Endpunkt, an dem die Iteration enden soll. Diese Punkte sind Knoten innerhalb des Graphen und werden 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 kürzester Pfad . Dies geht nur bei einem gewichteten Graphen, bei dem die Kannten eine Gewichtung ungleich Null haben. Ausgehend vom Zielknoten geht man rückwärts zum Startknoten, wobei ein Pfad gewählt wird, der in der Summe aller Kannten der günstigste ist. Alle weiteren Knoten werden nicht traversiert.

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_FLIGHT_EXAMPLE.

Hinweise

Alle 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 diese 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

PERFORM Short Reference   CL_GUI_FRONTEND_SERVICES - Frontend Services  
Diese Dokumentation steht unter dem Copyright der SAP AG.

Length: 3244 Date: 20240427 Time: 025810     sap01-206 ( 62 ms )