Graphencontainer

Alle Beispiele in diesem Kapitel verwendeten zur Definition von Graphen die Klasse boost::adjacency_list. Im Folgenden werden die anderen beiden von Boost.Graph angebotenen Klassen boost::adjacency_matrix und boost::compressed_sparse_row_graph vorgestellt.

#include <boost/graph/adjacency_matrix.hpp>
#include <array>
#include <utility>

int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };

  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};

  typedef boost::adjacency_matrix<boost::undirectedS> graph;
  graph g{edges.begin(), edges.end(), 4};
}

Wie im Beispiel 31.15 zu sehen, wird boost::adjacency_matrix grundsätzlich genauso verwendet wie boost::adjacency_list. Ein Unterschied ist jedoch, dass die ersten beiden Template-Parameter zur Auswahl von Containern für Punkte und Verbindungslinien bei boost::adjacency_matrix nicht existieren. Im Zusammenhang mit boost::adjacency_matrix werden also keine Selektoren wie boost::vecS oder boost::setS verwendet. boost::adjacency_matrix speichert den Graphen als Matrix, so dass die interne Struktur vorgegeben ist. Wenn Sie sich die Matrix als zweidimensionale Tabelle vorstellen: Die Tabelle hat genauso viele Reihen und Spalten wie der Graph Punkte hat. Verbindungslinien werden erstellt, indem in der entsprechenden Zelle, die der Schnittpunkt zweier Punkte ist, eine Markierung vorgenommen wird.

Die Struktur von boost::adjacency_matrix erlaubt es, Verbindungen sehr schnell zu erstellen und zu entfernen. Dafür ist der Speicherbedarf höher. Als Grundregel gilt: Verwenden Sie boost::adjacency_list, wenn es relativ wenige Verbindungen im Vergleich zu Punkten gibt. Je mehr Verbindungen, umso mehr ergibt es Sinn, boost::adjacency_matrix zu verwenden.

#include <boost/graph/compressed_sparse_row_graph.hpp>
#include <array>
#include <utility>

int main()
{
  enum { topLeft, topRight, bottomRight, bottomLeft };

  std::array<std::pair<int, int>, 4> edges{{
    std::make_pair(topLeft, topRight),
    std::make_pair(topRight, bottomRight),
    std::make_pair(bottomRight, bottomLeft),
    std::make_pair(bottomLeft, topLeft)
  }};

  typedef boost::compressed_sparse_row_graph<boost::bidirectionalS> graph;
  graph g{boost::edges_are_unsorted_multi_pass, edges.begin(),
    edges.end(), 4};
}

Die Klasse boost::compressed_sparse_row_graph wird wie im Beispiel 31.16 zu sehen ähnlich wie boost::adjacency_list und boost::adjacency_matrix verwendet. Der entscheidende Unterschied ist, dass keine Änderungen bei Graphen vom Typ boost::compressed_sparse_row_graph möglich sind. Punkte und Verbindungen können nach der Instanziierung des Graphen weder hinzugefügt noch entfernt werden. boost::compressed_sparse_row_graph ergibt daher nur Sinn, wenn mit Graphen gearbeitet wird, deren Definition unveränderlich ist.

Beachten Sie außerdem, dass boost::compressed_sparse_row_graph ausschließlich gerichtete Verbindungslinien unterstützt. Sie können boost::compressed_sparse_row_graph nicht mit dem Template-Parameter boost::undirectedS instanziieren.

Der Vorteil von boost::compressed_sparse_row_graph ist, dass Graphen kompakter gespeichert werden können. boost::compressed_sparse_row_graph bietet sich daher bei sehr großen Graphen an, um den Speicherbedarf gering zu halten.