Die Boost C++ Bibliotheken

Knoten und Kanten

Graphen bestehen aus Punkten und Verbindungslinien. Um einen Graph zu erstellen, muss daher angegeben werden, aus wie vielen Punkten er besteht und zwischen welchen Punkten Verbindungslinien verlaufen. Im Beispiel 31.1 soll ein erster einfacher Graph erstellt werden, der aus vier Punkten besteht, ohne dass diese verbunden werden.

Beispiel 31.1. Ein Graph vom Typ boost::adjacency_list mit vier Knoten
#include <boost/graph/adjacency_list.hpp>
#include <iostream>

int main()
{
  boost::adjacency_list<> g;

  boost::adjacency_list<>::vertex_descriptor v1 = boost::add_vertex(g);
  boost::adjacency_list<>::vertex_descriptor v2 = boost::add_vertex(g);
  boost::adjacency_list<>::vertex_descriptor v3 = boost::add_vertex(g);
  boost::adjacency_list<>::vertex_descriptor v4 = boost::add_vertex(g);

  std::cout << v1 << ", " << v2 << ", " << v3 << ", " << v4 << '\n';
}

Boost.Graph bietet drei Container an, um Graphen zu definieren. Der wichtigste Container ist boost::adjacency_list, der in fast allen Beispielen in diesem Kapitel Verwendung findet. Um auf diese Klasse zugreifen zu können, müssen Sie die Headerdatei boost/graph/adjacency_list.hpp einbinden. Möchten Sie einen anderen Container verwenden, müssen Sie auf eine andere Headerdatei zugreifen. Es gibt keine Master-Headerdatei, um Zugriff auf alle Klassen und Funktionen von Boost.Graph zu erhalten.

boost::adjacency_list ist ein Template, das im Beispiel 31.1 mit Standardwerten instanziiert wird. Welche Template-Parameter Sie übergeben können, erfahren Sie später. Wie Sie sehen, ist die Klasse im Namensraum boost definiert. Alle für Anwender von Boost.Graph wichtigen Klassen und Funktionen sind in diesem Namensraum abgelegt.

Um dem Graphen vier Punkte hinzuzufügen, rufen Sie die Funktion boost::add_vertex() viermal auf. Diese Funktion erwartet als einzigen Parameter den Graphen, der den neuen Punkt erhalten soll.

Beachten Sie, dass es sich bei boost::add_vertex() um eine freistehende Funktion und nicht um eine Methode der Klasse boost::adjacency_list handelt. Sie finden in Boost.Graph sehr viele Funktionen, die man genauso gut als Methode hätte implementieren können. Boost.Graph will jedoch mehr eine generische als eine objektorientierte Bibliothek sein. Für Anwender von Boost.Graph macht es jedoch keinen Unterschied, ob eine Funktion oder Methode aufgerufen wird. Für einen besseren Überblick, welche freistehenden Funktionen mit boost::adjacency_list verwendet werden, führt die Dokumentation von boost::adjacency_list die entsprechenden Funktionen an.

Die Funktion, um einen Punkt einem Graphen hinzuzufügen, heißt boost::add_vertex(). In der Graphentheorie werden Punkte als Knoten oder Ecken bezeichnet. Ins Englische übersetzt wird daraus vertex – daher der Funktionsname.

boost::add_vertex() gibt ein Objekt vom Typ boost::adjacency_list::vertex_descriptor zurück. Dieses Objekt stellt den neu hinzugefügten Punkt im Graphen dar. Sie können wie im Beispiel 31.1 das Objekt direkt auf die Standardausgabe ausgeben. Wenn Sie Beispiel 31.1 ausführen, sehen Sie 0, 1, 2, 3.

Im Beispiel 31.1 werden Punkte über positive Ganzzahlen identifiziert. Diese Zahlen sind Indizes in einen Vektor, der innerhalb von boost::adjacency_list verwendet wird. Es ist daher kein Wunder, dass boost::add_vertex() die Zahlen 0, 1, 2 und 3 zurückgibt – mit jedem Aufruf wird dem Vektor ein zusätzlicher Punkt hinzugefügt.

Es ist durchaus möglich, dass boost::adjacency_list::vertex_descriptor einen anderen Typ als std::size_t hat. Das hängt von den Template-Parametern ab, die an boost::adjacency_list übergeben werden. Standardmäßig verwendet boost::adjacency_list einen Vektor, um Punkte zu speichern.

Beispiel 31.2. Zugriff auf Knoten mit boost::vertices()
#include <boost/graph/adjacency_list.hpp>
#include <utility>
#include <algorithm>
#include <iterator>
#include <iostream>

int main()
{
  boost::adjacency_list<> g;

  boost::add_vertex(g);
  boost::add_vertex(g);
  boost::add_vertex(g);
  boost::add_vertex(g);

  std::pair<boost::adjacency_list<>::vertex_iterator,
    boost::adjacency_list<>::vertex_iterator> vs = boost::vertices(g);

  std::copy(vs.first, vs.second,
    std::ostream_iterator<boost::adjacency_list<>::vertex_descriptor>{
      std::cout, "\n"});
}

Um auf alle Punkte in einem Graph zuzugreifen, kann boost::vertices() aufgerufen werden. Diese Funktion gibt zwei Iteratoren vom Typ boost::adjacency_list::vertex_iterator zurück, die auf den Anfang und das Ende der Punkte zeigen. Die Iteratoren werden in einem std::pair zurückgegeben. Im Beispiel 31.2 werden die Iteratoren verwendet, um die Punkte auf die Standardausgabe auszugeben. Dieses Beispiel gibt wie das vorherige die Zahlen 0, 1, 2 und 3 aus.

Beispiel 31.3 zeigt Ihnen, wie Punkte mit Linien verbunden werden.

Beispiel 31.3. Zugriff auf Kanten mit boost::edges()
#include <boost/graph/adjacency_list.hpp>
#include <utility>
#include <algorithm>
#include <iterator>
#include <iostream>

int main()
{
  boost::adjacency_list<> g;

  boost::adjacency_list<>::vertex_descriptor v1 = boost::add_vertex(g);
  boost::adjacency_list<>::vertex_descriptor v2 = boost::add_vertex(g);
  boost::add_vertex(g);
  boost::add_vertex(g);

  std::pair<boost::adjacency_list<>::edge_descriptor, bool> p =
    boost::add_edge(v1, v2, g);
  std::cout.setf(std::ios::boolalpha);
  std::cout << p.second << '\n';

  p = boost::add_edge(v1, v2, g);
  std::cout << p.second << '\n';

  p = boost::add_edge(v2, v1, g);
  std::cout << p.second << '\n';

  std::pair<boost::adjacency_list<>::edge_iterator,
    boost::adjacency_list<>::edge_iterator> es = boost::edges(g);

  std::copy(es.first, es.second,
    std::ostream_iterator<boost::adjacency_list<>::edge_descriptor>{
      std::cout, "\n"});
}

Sie rufen die Funktion boost::add_edge() auf, um zwei Punkte in einem Graphen zu verbinden. Sie müssen dazu die Punkte und den Graphen als Parameter übergeben.

In der Graphentheorie werden Verbindungslinien als Kanten bezeichnet. Im Englischen wird daraus edge – daher der Funktionsname boost::add_edge().

boost::add_edge() gibt ein std::pair zurück. Über first haben Sie Zugriff auf die Verbindungslinie. second ist eine bool-Variable, die angibt, ob die Verbindungslinie mit boost::add_edge() neu hinzugefügt wurde. Wenn Sie Beispiel 31.3 ausführen, sehen Sie, dass p.second jeweils auf true gesetzt ist und alle Aufrufe von boost::add_edge() dazu führen, dass eine neue Verbindungslinie dem Graphen hinzugefügt wird.

Über boost::edges() erhalten Sie Zugriff auf alle Verbindungslinien eines Graphen. So wie boost::vertices() gibt auch boost::edges() zwei Iteratoren zurück, die auf den Anfang und das Ende aller Verbindungslinien zeigen. Beispiel 31.3 gibt alle Verbindungslinien auf die Standardausgabe aus. Wenn Sie das Beispiel ausführen, erhalten Sie (0,1), (0,1) und (1,0).

Die Ausgabe zeigt, dass der Graph drei Verbindungslinien hat. Diese verlaufen alle zwischen den ersten beiden Punkten – die mit den Indizes 0 und 1. Die Ausgabe zeigt auch an, an welchem Punkt Verbindungslinien beginnen und enden. Zwei Verbindungslinien laufen vom ersten zum zweiten Punkt, eine Verbindungslinie in die umgekehrte Richtung. Die Richtung hängt davon ab, welcher Punkt jeweils als erster und zweiter Parameter an boost::add_edge() übergeben wird.

Es ist problemlos möglich, mehrere Verbindungslinien zwischen zwei Punkten aufzuspannen. Die Möglichkeit, die gleichen Verbindungslinien mehrfach zu definieren, kann jedoch ausgeschaltet werden.

Beispiel 31.4. boost::adjacency_list mit Selektoren
#include <boost/graph/adjacency_list.hpp>
#include <utility>
#include <algorithm>
#include <iterator>
#include <iostream>

int main()
{
  typedef boost::adjacency_list<boost::setS, boost::vecS,
    boost::undirectedS> graph;
  graph g;

  boost::adjacency_list<>::vertex_descriptor v1 = boost::add_vertex(g);
  boost::adjacency_list<>::vertex_descriptor v2 = boost::add_vertex(g);
  boost::add_vertex(g);
  boost::add_vertex(g);

  std::pair<graph::edge_descriptor, bool> p =
    boost::add_edge(v1, v2, g);
  std::cout.setf(std::ios::boolalpha);
  std::cout << p.second << '\n';

  p = boost::add_edge(v1, v2, g);
  std::cout << p.second << '\n';

  p = boost::add_edge(v2, v1, g);
  std::cout << p.second << '\n';

  std::pair<graph::edge_iterator,
    graph::edge_iterator> es = boost::edges(g);

  std::copy(es.first, es.second,
    std::ostream_iterator<graph::edge_descriptor>{std::cout, "\n"});
}

Im Beispiel 31.4 wird boost::adjacency_list nicht mehr mit Standardwerten instanziiert. Stattdessen werden drei Template-Parameter übergeben, die Selektoren darstellen – deswegen enden ihre Namen mit einem S. Diese Selektoren bestimmen unter anderem, welche Typen innerhalb von boost::adjacency_list verwendet werden, um Punkte und Verbindungslinien zu speichern.

boost::adjacency_list verwendet standardmäßig std::vector für Punkte und Verbindungslinien. Indem im Beispiel 31.4 boost::setS als erster Template-Parameter angegeben wird, wird std::set als Container für Verbindungslinien ausgewählt. Weil std::set im Vergleich zu std::vector keine Duplikate zulässt, ist es im Beispiel 31.4 nicht möglich, mehrfach die gleiche Verbindungslinie mit boost::add_edge() hinzuzufügen. Wenn Sie das Beispielprogramm ausführen, sehen Sie, dass nur mehr (0,1) ausgegeben wird.

Über den zweiten Template-Parameter wird boost::adjacency_list mitgeteilt, welche Klasse für Punkte verwendet werden soll. Im Beispiel 31.4 ist dies boost::vecS. Über diesen Selektor wird std::vector ausgewählt. boost::vecS ist der Standardwert für den ersten und zweiten Template-Parameter von boost::adjacency_list.

Der dritte Template-Parameter gibt an, ob Verbindungslinien gerichtet oder ungerichtet sind. Standardmäßig verwendet boost::adjacency_list als Selektor boost::directedS. In diesem Fall sind Verbindungslinien gerichtet und können zum Beispiel als Pfeil dargestellt werden. Wird boost::directedS verwendet, können Verbindungslinien nur in eine Richtung laufen.

Im Beispiel 31.4 ist als Selektor boost::undirectedS angegeben, womit Verbindungslinien ungerichtet sind. Derartige Verbindungslinien können in beide Richtungen laufen. Der Start- und Endpunkt solcher Verbindungslinien spielt keine Rolle. Dies ist ein weiterer Grund, warum im Beispiel 31.4 lediglich eine Verbindungslinie erstellt wird. Beim dritten Aufruf von boost::add_edge() sind der Start- und Endpunkt ausgetauscht – die Verbindungslinie wird dennoch nicht dem Graphen hinzugefügt, da sie identisch mit der bereits beim ersten Aufruf von boost::add_edge() erstellten Linie ist.

Neben den erwähnten Selektoren bietet Boost.Graph weitere an. Zu diesen zählen zum Beispiel boost::listS, boost::mapS oder boost::hash_setS, um Container für Punkte und Verbindungslinien auszuwählen. Als weiterer Selektor für Verbindungslinien steht außerdem boost::bidirectionalS zur Verfügung, mit dem Verbindungslinien erstellt werden können, die doppelt gerichtet sind und in beide Richtungen laufen. Dieser Selektor ähnelt boost::undirectedS. Start- und Endpunkt sind bei boost::bidirectionalS jedoch entscheidend. Wenn Sie im Beispiel 31.4 boost::bidirectionalS verwenden, fügt der dritte Aufruf von boost::add_edge() dem Graphen eine neue Verbindungslinie hinzu.

Beispiel 31.5 zeigt Ihnen, wie Sie einfacher Punkte und Verbindungslinien erstellen.

Beispiel 31.5. Automatisch Knoten mit boost::add_edge() erstellen
#include <boost/graph/adjacency_list.hpp>
#include <tuple>
#include <algorithm>
#include <iterator>
#include <iostream>

int main()
{
  typedef boost::adjacency_list<boost::setS, boost::vecS,
    boost::undirectedS> graph;
  graph g;

  enum { topLeft, topRight, bottomRight, bottomLeft };

  boost::add_edge(topLeft, topRight, g);
  boost::add_edge(topRight, bottomRight, g);
  boost::add_edge(bottomRight, bottomLeft, g);
  boost::add_edge(bottomLeft, topLeft, g);

  graph::edge_iterator it, end;
  std::tie(it, end) = boost::edges(g);
  std::copy(it, end,
    std::ostream_iterator<graph::edge_descriptor>{std::cout, "\n"});
}

Im Beispiel 31.5 wird ein Graph bestehend aus vier Punkten definiert. Um sich den Graphen besser als eine Karte mit vier Feldern vorstellen zu können, werden den Punkten Namen gegeben: topLeft, topRight, bottomRight und bottomLeft. Hinter diesen Namen stehen Zahlen, wie sie in vorherigen Beispielen von boost::add_vertex() zurückgegeben und als Indizes verwendet wurden.

Es ist möglich, den Graphen ohne einen Aufruf von boost::add_vertex() zu definieren. Boost.Graph fügt fehlende Punkte einem Graphen automatisch hinzu, wenn die an boost::add_edge() übergebenen Punkte nicht existieren. So führt der vierfache Aufruf von boost::add_edge() im Beispiel 31.5 dazu, dass nicht nur vier Verbindungslinien definiert werden, sondern der Graph gleichzeitig die für die Verbindungslinien notwendigen vier Punkte erhält.

Beachten Sie außerdem, wie mit std::tie() die Iteratoren, die boost::edges() in einem std::pair zurückgibt, direkt in it und end gespeichert werden. std::tie() ist seit C++11 Teil der Standardbibliothek.

Beim im Beispiel 31.5 erstellten Graphen handelt es sich um eine Karte, die aus vier Feldern besteht. Um von links oben nach rechts unten zu gelangen, kann entweder über das rechte obere oder das linke untere Feld gegangen werden. Es gibt keine Verbindung zu gegenüberliegenden Feldern, so dass nicht direkt von links oben nach rechts unten gelangt werden kann. Alle folgenden Beispiele in diesem Kapitel arbeiten mit diesem Graphen.

Beispiel 31.6. boost::adjacent_vertices() und boost::out_edges()
#include <boost/graph/adjacency_list.hpp>
#include <tuple>
#include <algorithm>
#include <iterator>
#include <iostream>

int main()
{
  typedef boost::adjacency_list<boost::setS, boost::vecS,
    boost::undirectedS> graph;
  graph g;

  enum { topLeft, topRight, bottomRight, bottomLeft };

  boost::add_edge(topLeft, topRight, g);
  boost::add_edge(topRight, bottomRight, g);
  boost::add_edge(bottomRight, bottomLeft, g);
  boost::add_edge(bottomLeft, topLeft, g);

  graph::adjacency_iterator vit, vend;
  std::tie(vit, vend) = boost::adjacent_vertices(topLeft, g);
  std::copy(vit, vend,
    std::ostream_iterator<graph::vertex_descriptor>{std::cout, "\n"});

  graph::out_edge_iterator eit, eend;
  std::tie(eit, eend) = boost::out_edges(topLeft, g);
  std::for_each(eit, eend,
    [&g](graph::edge_descriptor it)
      { std::cout << boost::target(it, g) << '\n'; });
}

Im Beispiel 31.6 lernen Sie Funktionen kennen, um zusätzliche Informationen zu Punkten zu erhalten. So gibt boost::adjacent_vertices() ein Paar Iteratoren zurück, über die auf Punkte zugegriffen werden kann, mit denen der Punkt, der als Parameter an die Funktion übergeben ist, verbunden ist. boost::out_edges() können Sie aufrufen, wenn Sie auf die ausgehenden Verbindungslinien eines Punkts zugreifen möchten. Boost.Graph bietet auch eine Funktion boost::in_edges() an, um eingehende Verbindungslinien zu erhalten. Wird wie im Beispiel 31.6 mit ungerichteten Verbindungslinien gearbeitet, spielt es keine Rolle, welche dieser beiden Funktionen aufgerufen wird.

boost::target() gibt den Endpunkt einer Verbindungslinie zurück. Der Startpunkt wird mit boost::source() erhalten.

Beispiel 31.6 gibt zweimal 1 und 3 auf die Standardausgabe aus. Das sind die Indizes für das rechte obere und das linke untere Feld. Da das linke obere Feld an boost::adjacent_vertices() übergeben wird, werden die Indizes für die genannten Felder zurückgegeben und mit std::copy() auf die Standardausgabe ausgegeben. Das linke obere Feld wird auch an boost::out_edges() übergeben, so dass auf die ausgehenden Verbindungslinien zugegriffen werden kann. Da in std::for_each() auf boost::target() zugegriffen wird, werden wieder die Indizes des rechten oberen und linken unteren Feldes ausgegeben.

Beispiel 31.7 zeigt Ihnen, wie Sie einen Graphen beim Instanziieren von boost::adjacency_list definieren können, ohne für jede Verbindungslinie boost::add_edge() aufrufen zu müssen.

Beispiel 31.7. Verbindungslinien beim Instanziieren definieren
#include <boost/graph/adjacency_list.hpp>
#include <array>
#include <utility>
#include <iostream>

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_list<boost::setS, boost::vecS,
    boost::undirectedS> graph;
  graph g{edges.begin(), edges.end(), 4};

  std::cout << boost::num_vertices(g) << '\n';
  std::cout << boost::num_edges(g) << '\n';

  g.clear();
}

Sie können an den Konstruktor von boost::adjacency_list Iteratoren übergeben, die auf Objekte vom Typ std::pair<int, int> zeigen, die Verbindungslinien definieren. Übergeben Sie Iteratoren, müssen Sie außerdem als dritten Parameter angeben, wie viele Punkte der Graph erhalten soll. Es werden auf alle Fälle die Punkte definiert, die für die Definition der Verbindungslinien notwendig sind. Über den dritten Parameter können Sie dem Graphen zusätzliche Punkte hinzufügen, die nicht mit anderen Punkten verbunden sind.

Sie sehen im Beispiel 31.7 weitere Funktionen wie boost::num_vertices() und boost::num_edges(), mit denen die Anzahl der Punkte und Verbindungslinien erhalten werden kann. Wenn Sie das Beispielprogramm ausführen, wird zweimal 4 auf die Standardausgabe ausgegeben.

Im Beispiel 31.7 wird außerdem boost::adjacency_list::clear() aufgerufen. Mit dieser Methode können alle Punkte und Verbindungslinien entfernt werden. Hierbei handelt es sich tatsächlich um eine Methode der Klasse boost::adjacency_list und nicht um eine freistehende Funktion.