5.2.7. Spezielle Hilfsdatenstrukturen für Graphenalgorithmen

Lernziele

Die Klasse node_list
Die Klasse node_set
Die Klasse node_pq
Die Klasse b_node_pq
Die Klasse node_partition
Die Klasse edge_set

Häufig müssen in Graphenalgorithmen Knoten in einer linearen Liste verwaltet werden. Dafür kann natürlich eine list<node> verwendet werden. Für diese spezielle Kombination jedoch bietet LEDA eine besonders effiziente Implementierung in Form der Klasse node_list an, die allerdings eine gegenüber der Klasse list eingeschränkte Schnittstelle besitzt. Zudem kann jeder Knoten eines Graphen zu jedem Zeitpunkt in nur einer node_list enthalten sein. Der Test, ob ein bestimmter Knoten in einer node_list enthalten ist, benötigt nur erwartete Zeit O(1).

Dem entsprechend gibt es für Mengen von Knoten den speziellen Typ node_set und für Partitionen von Knoten den Typ node_partition. Für Prioritäts-Warteschlangen von Knoten bietet LEDA die Typen node_pq und b_node_pq an, wobei letzterer nur für Prioritäts-Warteschlangen mit beschränkten, ganzzahligen Prioritäten geeignet ist.

Darüber hinaus gibt es die Klasse edge_set zum effizienten Verwalten von Kantenmengen.

Alle diese Klassen sollten i. Allg. aus Effizienzgründen überall dort verwendet werden, wo sonst der entsprechend parametrisierte Containertyp bzw. die entsprechend parametrisierte Prioritäts-Warteschlange verwendet würde und das Programm mit den Funktionen der eingeschränkten Schnittstelle auskommt.

Auf eine genauere Beschreibung der Schnittstellen wollen wir hier verzichten, da sie ohnehin mit den Schnittstellen der allgemeineren Typen weitgehend übereinstimmen. Vielmehr sei hierfür auf die Manualseiten von node_list, node_set, node_partition, node_pq, b_node_pq und edge_set verwiesen.