Datenstrukturen für gerichtete und ungerichtete Graphen sind von grundlegender Bedeutung. Bekannte und weit verbreitete Implementierungen wie die Boost Graph Library und Lemon sind so entworfen, dass die zusammenhängenden ganzzahligen Indizes von Knoten und Kanten dem Benutzer über die Schnittstelle nicht zugänglich sind.
Stattdessen identifiziert der Benutzer Knoten und Kanten durch (kleine) repräsentative Objekte. Ein Vorteil besteht darin, dass diese Objekte automatisch aktualisiert werden, wenn sich die Indizes von Knoten und Kanten aufgrund der Entfernung von Kanten oder Knoten aus dem Diagramm ändern.
Meiner Meinung nach (!) wird dieser Vorteil überbewertet. Benutzer speichern typischerweise die repräsentativen Objekte von Knoten und / oder Kanten in einem Container, z. B. std::vector . Wenn nun Knoten oder Kanten aus dem Graphen entfernt werden und deren Repräsentationsobjekte ungültig werden, muss der Benutzer entweder diesen ignorieren oder den Vektor neu anordnen, um gültige Ganzzahlindizes zusammenhängend zu halten, dh genau die Buchhaltung auszuführen, die der Entwurf haben sollte unnötig machen.
Daher lautet meine Frage : Hat die Design-Option (das Ausblenden der zusammenhängenden ganzzahligen Indizes von Knoten und Kanten durch den Benutzer) weitere Vorteile?
(Ich bin in der Java-Welt zu Hause, hoffe aber, dass es in Ordnung ist, eine Antwort zu geben, die sich nicht auf die fraglichen Bibliotheken konzentriert)
Es gibt mehrere mögliche Vorteile einer solchen Abstraktion. Eine der wichtigsten wurde bereits in der Frage erwähnt: Die Konsistenz beim Durchführen von Änderungen in einem Graphen ist viel schwieriger zu erreichen, wenn Indizes beibehalten werden müssen.
Der Grund warum dies schwierig sein kann, liegt in den verschiedenen möglichen Graphendarstellungen: Es kann leicht sein, konsistente Indizes beizubehalten, wenn die interne Darstellung nur (und immer) aus zufälligen Zugriffslisten von% bestand. co_de% und Vertex Objekte. Bei anderen Darstellungen kann das Bestimmen eines Index jedoch schwierig sein.
Dies steht in direktem Zusammenhang mit dem zweiten Hauptvorteil: Man kann verschiedene Implementierungen der Graph-Schnittstelle verwenden. Der Abschnitt "Graph Data Structures" in der Review of Elementary Graph Theory der Boost-Dokumentation listet mehrere Datenstrukturen auf, die bereits vom BGL angeboten werden (und jeder kann seine eigene Implementierung hinzufügen). Die Laufzeiten für bestimmte Operationen sind in Big-O-Notation angegeben, und einmal kann man sehen, dass sie zwischen den verschiedenen Datenstrukturen stark variieren.
Man kann sich leicht vorstellen, dass verschiedene Implementierungen für bestimmte Aufgaben besser geeignet sind. Angenommen, ein Algorithmus muss häufig prüfen, ob ein bestimmter Vertex in einem Graphen enthalten ist. Für einen indexierten (also Edge -basierten) Vertexspeicher würde dies für jeden Test O (n) erfordern. Bei einem list -basierten Speicher der Vertices könnte dies in O (1) geschehen - aber in diesem Fall gibt es einfach keine sinnvollen "Indizes".
Wie in der Grafikkonzepte im Überblick:
Tatsächlich muss die BGL-Schnittstelle nicht einmal mit einer Datenstruktur implementiert werden, da es für einige Probleme einfacher oder effizienter ist, einen Graphen implizit auf der Grundlage einiger Funktionen zu definieren.
So suggerieren , dass es einen "indizierten Zugriff" gibt, selbst wenn der Graph nicht einmal im Speicher existiert, kann eine solche rein funktionale Implementierung behindern.
Ich kann nicht für Lemon-Grafik sprechen, aber für Boost-Grafik denke ich, das Hauptziel ist es, generisch zu sein. Das Abstrahieren des Ecken- (Kanten-) Zugriffs hilft also, dieses Ziel zu erreichen.
In der Dokumentation steht, dass das Boost-Diagramm auf Dietmar Kühls Masterarbeit zu generischen Graphalgorithmen basiert. (Siehe meine Antwort zu Sind Eigenschaftskarten für BGL erforderlich? ). Das Hauptziel der Bibliothek ist daher, generisch und erweiterbar zu sein. Die Wahl des Kapselungszugriffs ist Teil der Abstraktion der Algorithmen von der Graphendarstellung. Für mich sind kontinuierliche ganzzahlige Indizes ein Implementierungsdetail.
Boost macht keine Annahmen darüber, wie Sie das Diagramm verwenden oder welche Leistungseinbußen für Sie wichtig sind. Sie können den Container auswählen (oder implementieren), der Ihren Anforderungen am besten entspricht.
Wenn Sie diese Kapselung brechen wollen, können Sie das tun. In der Tat beinhaltet meine häufigste Verwendung von Boost-Graphen vecS containers und eine vector von struct s. Ich arbeite normalerweise mit Graphen, bei denen die Größe festgelegt ist. Ich könnte genauso einfach ein map von vertex_descriptor s (oder edge_descriptor s) für Objekte verwenden, um dasselbe Ziel zu erreichen.
Zusammenfassend würde ich sagen, dass dies nicht so sehr eine Design-Entscheidung ist, sondern eher eine Konsequenz des Erreichens des allgemeineren Ziels, generisch zu sein. Das Verstecken des Zugriffs hat also den Vorteil, allgemeiner zu sein.
Tags und Links c++ indexing graph boost-graph lemon-graph-library