Algorithmen

Nachdem Sie gesehen haben, wie Sie eigene Graphen definieren, lernen Sie im Folgenden Algorithmen kennen. Algorithmen von Boost.Graph ähneln denen aus der Standardbibliothek – sie sind generisch und höchst flexibel. Es erschließt sich aber nicht immer auf den ersten Blick, wie sie verwendet werden.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <iterator>
#include <algorithm>
#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};

  boost::array<int, 4> distances{{0}};

  boost::breadth_first_search(g, topLeft,
    boost::visitor(
      boost::make_bfs_visitor(
        boost::record_distances(distances.begin(),
          boost::on_tree_edge{}))));

  std::copy(distances.begin(), distances.end(),
    std::ostream_iterator<int>{std::cout, "\n"});
}

Im Beispiel 31.8 wird der Algorithmus boost::breadth_first_search() verwendet, um Punkte von innen nach außen zu besuchen. Der Algorithmus beginnt an dem Punkt, der als zweiter Parameter übergeben wird, und besucht zuerst alle Punkte, die von diesem Punkt direkt erreicht werden können. boost::breadth_first_search() funktioniert wie eine sich in alle Richtungen ausbreitende Wasserwelle.

boost::breadth_first_search() gibt jedoch kein bestimmtes Ergebnis zurück. Der Algorithmus besucht Punkte – sonst nichts. Ob bei diesen Besuchen Daten ermittelt und gespeichert werden sollen, hängt davon ab, welche Besucher Sie übergeben.

Besucher sind Objekte, deren Methoden aufgerufen werden, wenn ein Punkt besucht wird. Indem Sie Besucher an einen Algorithmus wie boost::breadth_first_search() übergeben, legen Sie fest, was passieren soll, wenn ein Punkt besucht wird. Besucher entsprechen Funktionsobjekten, die an Algorithmen aus der Standardbibliothek übergeben werden können.

Im Beispiel 31.8 wird ein Besucher verwendet, der Distanzen aufzeichnen kann. Als Distanz wird die Anzahl der Verbindungslinien bezeichnet, die durchlaufen werden müssen, um zu einem bestimmten Punkt zu gelangen – ausgehend von dem Punkt, der als zweiter Parameter an boost::breadth_first_search() übergeben wird. Boost.Graph bietet die Hilfsfunktion boost::record_distances() an, um das entsprechende Objekt zu erstellen. An diese Funktion muss eine Property-Map und ein Tag übergeben werden.

Property-Maps sind Objekte, die Eigenschaften zu Punkten oder Verbindungslinien in einem Graphen speichern können. Das Konzept der Property-Maps ist in der Bibliothek Boost.Graph beschrieben. Ein Zeiger oder ein Iterator auf einen entsprechenden Container wird automatisch als Anfang einer Property-Map interpretiert, so dass Sie sich nicht im Detail mit Property-Maps beschäftigen müssen. Im Beispiel 31.8 wird mit distances.begin() der Anfang des Arrays distances an boost::record_distances() übergeben, womit das Array als Property-Map für Punkte verwendet wird. Dabei ist wichtig, dass die Länge des Arrays der Anzahl der Punkte im Graphen entspricht. Schließlich soll für jeden Punkt im Graphen die Distanz zum Ausgangspunkt gespeichert werden.

Beachten Sie, dass distances auf dem Typ boost::array und nicht auf std::array basiert. std::array würde zu einem Compilerfehler führen.

Abhängig vom verwendeten Algorithmus gibt es verschiedene Ereignisse, wenn ein Punkt besucht wird. Über den zweiten Parameter, der an boost::record_distances() übergeben wird, wird angegeben, zu welchem Ereignis der Besucher informiert werden soll. Boost.Graph definiert hierfür Tags, bei denen es sich um leere Klassen handelt, deren einziger Sinn darin besteht, ein Ereignis auszuwählen. So ist im Beispiel 31.8 mit dem Tag boost::on_tree_edge angegeben, dass die Distanz dann aufgezeichnet werden soll, wenn über eine Verbindungslinie ein neuer Punkt gefunden wurde.

Ereignisse sind abhängig vom verwendeten Algorithmus. Welche Ereignisse ein Algorithmus unterstützt und welche Tags Sie verwenden können, müssen Sie jeweils in der Dokumentation des Algorithmus nachschlagen.

Ein Besucher wie der, der von boost::record_distances() erstellt wird, ist unabhängig vom Algorithmus. Sie können boost::record_distances() also durchaus im Zusammenhang mit anderen Algorithmen verwenden. Die Verbindung zwischen dem jeweils verwendeten Algorithmus und dem Besucher findet über einen Adapter statt. Im Beispiel 31.8 wird dieser Adapter über boost::make_bfs_visitor() erstellt. Diese Hilfsfunktion gibt ein Besucherobjekt zurück, wie es vom Algorithmus boost::breadth_first_search() erwartet wird. Dieses Besucherobjekt bietet Methoden an, die genau zu den Ereignissen passen, die der jeweilige Algorithmus unterstützt. So definiert das Besucherobjekt, das von boost::make_bfs_visitor() zurückgegeben wird, zum Beispiel eine Methode namens tree_edge(). Wird an boost::make_bfs_visitor() ein Besucher übergeben, der wie im Beispiel 31.8 mit dem Tag boost::on_tree_edge definiert wird, wird dieser Besucher dann aufgerufen, wenn tree_edge() aufgerufen wird. Auf diese Weise ist es möglich, Besucher mit unterschiedlichen Algorithmen zu verwenden, ohne dass Besucher wie der, der mit boost::record_distances() erstellt wird, sämtliche Methoden definieren müssen, wie sie von allen nur erdenklichen Algorithmen benötigt werden.

Der Besucher-Adapter, der von boost::make_bfs_visitor() zurückgegeben wird, kann nicht direkt als dritter Parameter an boost::breadth_first_search() übergeben werden. Er muss mit boost::visitor() verpackt werden, um als dritter Parameter akzeptiert werden zu können.

Algorithmen wie boost::breadth_first_search() gibt es in zwei Varianten: Eine Variante erwartet, dass sämtliche vom Algorithmus erwarteten Parameter einzeln übergeben werden. Die andere Variante unterstützt etwas Ähnliches wie Parameter mit Namen. Diese zweite Variante ist üblicherweise einfacher zu verwenden, weil nur die Parameter übergeben werden müssen, an denen Interesse besteht. Viele Parameter müssen oft nicht übergeben werden, weil Algorithmen Standardwerte verwenden.

Die im Beispiel 31.8 verwendete Variante von boost::breadth_first_search() erwartet, dass Parameter mit Namen übergeben werden – abgesehen von den ersten beiden Parametern, die den Graphen und den Ausgangspunkt darstellen. Der dritte Parameter von boost::breadth_first_search() kann aber quasi alles Mögliche sein. Im Beispiel 31.8 soll ein Besucher übergeben werden. Damit das funktioniert, wird der Besucher-Adapter, der von boost::make_bfs_visitor() zurückgegeben wird, mit boost::visitor() benannt. Es ist nun klar, dass es sich beim dritten Parameter um einen Besucher handelt. Sie werden in nachfolgenden Beispielen sehen, wie Sie andere oder mehrere Parameter mit Namen an dritter Stelle an boost::breadth_first_search() übergeben.

Wenn Sie Beispiel 31.8 ausführen, werden Ihnen die Zahlen 0, 1, 2 und 1 ausgegeben. Die Zahlen stellen die Distanzen zu anderen Punkten dar – ausgehend von links oben. Zum Feld rechts oben – das mit dem Index 1 – ist lediglich ein Schritt nötig. Zum Feld rechts unten – das mit dem Index 2 – sind zwei Schritte nötig. Zum Feld links unten – das mit dem Index 3 – ist wiederum nur ein Schritt nötig. Die Zahl 0, die zuerst ausgegeben wird, bezieht sich auf das Feld links oben. Da es sich dabei um den Ausgangspunkt handelt, der an boost::breadth_first_search() übergeben wurde, ist die Schrittzahl entsprechend 0.

Beachten Sie, dass Sie alle Felder im Array distances initialisieren müssen. boost::breadth_first_search() setzt die Felder im Array nicht direkt, sondern erhöht lediglich die im Array vorgefundenen Werte.

Nachdem Sie im Beispiel 31.8 gesehen haben, wie Sie die Distanz zu Punkten berechnen können, erfahren Sie im Folgenden, wie Sie den kürzesten Weg zu Punkten finden.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <algorithm>
#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};

  boost::array<int, 4> predecessors;
  predecessors[bottomRight] = bottomRight;

  boost::breadth_first_search(g, bottomRight,
    boost::visitor(
      boost::make_bfs_visitor(
        boost::record_predecessors(predecessors.begin(),
          boost::on_tree_edge{}))));

  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = predecessors[p];
  }
  std::cout << p << '\n';
}

Beispiel 31.9 gibt 0, 1 und 2 auf die Standardausgabe aus. Dies ist der kürzeste Weg von links oben nach rechts unten. Er führt über das Feld rechts oben, wobei der Weg über links unten natürlich genauso kurz wäre.

Der kürzeste Weg wird mit dem bereits bekannten Algorithmus boost::breadth_first_search() berechnet. Wie ebenfalls bereits bekannt macht dieser Algorithmus nichts anderes als Punkte zu besuchen. Um Wegbeschreibungen zu erhalten, muss deswegen ein geeigneter Besucher verwendet werden. Dieser wird im Beispiel 31.9 mit boost::record_predecessors() erhalten.

boost::record_predecessors() gibt einen Besucher zurück, der jeweils den Vorgänger eines Punkts speichert. Immer dann, wenn boost::breadth_first_search() einen neuen Punkt besucht, wird in der Property-Map, die an boost::record_predecessors() übergeben wird, der Punkt gespeichert, von dem aus der neue Punkt gefunden wurde. Da boost::breadth_first_search() von innen nach außen vorgeht, wird auf diese Weise die kürzeste Wegbeschreibung zu allen Punkten erhalten – ausgehend von dem Punkt, der als zweiter Parameter an boost::breadth_first_search() übergeben wird. Beispiel 31.9 ermittelt die kürzesten Wege von allen Punkten im Graphen nach rechts unten.

Nachdem boost::breadth_first_search() aufgerufen wurde, enthält die Property-Map predecessors die jeweiligen Vorgänger jedes Punkts. Um das erste Feld zu finden, zu dem man sich von links oben nach rechts unten bewegen muss, wird mit dem Index 0 – das ist der Index des linken oberen Felds – auf predecessors zugegriffen. Der Wert an dieser Stelle in der Property-Map ist 1. Dies bedeutet, dass das nächste Feld das rechte obere ist. Der Zugriff mit dem Index 1 auf predecessors ergibt das nächste Feld. Das ist in diesem Beispiel bereits das rechte untere – das mit dem Index 2. Auf diese Weise können in beliebig großen Graphen iterativ die Punkte gefunden werden, anhand derer man sich von einem Start- zu einem Endpunkt fortbewegen muss.

Beispiel 31.10 zeigt, wie boost::breadth_first_search() mit zwei Besuchern verwendet wird.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/graph/visitors.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <algorithm>
#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};

  boost::array<int, 4> distances{{0}};
  boost::array<int, 4> predecessors;
  predecessors[bottomRight] = bottomRight;

  boost::breadth_first_search(g, bottomRight,
    boost::visitor(
      boost::make_bfs_visitor(
        std::make_pair(
          boost::record_distances(distances.begin(),
            boost::on_tree_edge()),
          boost::record_predecessors(predecessors.begin(),
            boost::on_tree_edge{})))));

  std::for_each(distances.begin(), distances.end(),
    [](int d){ std::cout << d << '\n'; });

  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = predecessors[p];
  }
  std::cout << p << '\n';
}

Um zwei Besucher zu verwenden, müssen sie wie im Beispiel 31.10 mit std::make_pair() zu einem Paar verknüpft werden. Sollen mehr als zwei Besucher verwendet werden, müssen Sie die Paare verschachteln.

Beispiel 31.10 macht das Gleiche wie Beispiel 31.8 und Beispiel 31.9 zusammen.

Der Algorithmus boost::breadth_first_search() kann nur dann verwendet werden, wenn es keine unterschiedliche Gewichtung zwischen Verbindungen gibt. Verbindungen zwischen zwei Punkten können also zum Beispiel gleich schnell durchlaufen werden. Werden Gewichtungen vorgenommen, muss ein anderer Algorithmus verwendet werden, um kürzeste Wege zu finden.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/array.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::listS, boost::vecS,
    boost::undirectedS, boost::no_property,
    boost::property<boost::edge_weight_t, int>> graph;

  std::array<int, 4> weights{{2, 1, 1, 1}};

  graph g{edges.begin(), edges.end(), weights.begin(), 4};

  boost::array<int, 4> directions;
  boost::dijkstra_shortest_paths(g, bottomRight,
    boost::predecessor_map(directions.begin()));

  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = directions[p];
  }
  std::cout << p << '\n';
}

Im Beispiel 31.11 wird boost::dijkstra_shortest_paths() verwendet, um die kürzesten Wegstrecken nach rechts unten zu finden. Dieser Algorithmus wird eingesetzt, wenn Verbindungen unterschiedlich gewichtet sind. So wird für Beispiel 31.11 angenommen, dass es doppelt so lange dauert, von links oben nach rechts oben zu gelangen, als jede andere Verbindung zu überqueren.

Bevor boost::dijkstra_shortest_paths() verwendet werden kann, muss den Verbindungen ein entsprechendes Gewicht zugewiesen werden. Dies geschieht mit Hilfe des Arrays weights. Die Elemente im Array entsprechen den Verbindungslinien im Graphen. Da die erste Verbindungslinie von links oben nach rechts oben geht, ist das erste Element in weights auf einen doppelt so großen Wert wie alle anderen Elemente gesetzt.

Um die Gewichte den Verbindungslinien zuzuweisen, wird der Iterator auf den Anfang des Arrays weights als dritter Parameter an den Konstruktor des Graphen übergeben. Dieser dritte Parameter kann verwendet werden, um Verbindungseigenschaften zu initialisieren. Dies wiederum funktioniert nur, wenn Eigenschaften für Verbindungen definiert wurden.

Wenn Sie sich Beispiel 31.11 näher ansehen, stellen Sie fest, dass zusätzliche Template-Parameter an boost::adjacency_list übergeben werden. Der vierte und fünfte Template-Parameter geben an, ob und welche Eigenschaften Punkte und Verbindungslinien haben. Es ist also nicht nur möglich, Verbindungslinien Eigenschaften zuzuweisen, sondern auch Punkten.

Standardmäßig verwendet boost::adjacency_list boost::no_property, um anzugeben, dass weder Punkte noch Verbindungslinien Eigenschaften haben. Für den vierten Parameter im Beispiel 31.11 ist boost::no_property angegeben, um keine Eigenschaften für Punkte zu definieren. Der fünfte Parameter verwendet jedoch boost::property, um eine gebündelte Eigenschaft zu erstellen.

Gebündelte Eigenschaften sind Eigenschaften, die intern im Graphen gespeichert werden. Da es möglich ist, beliebig viele gebündelte Eigenschaften zu definieren, erwartet boost::property einen Tag, um die Eigenschaft definieren zu können. Boost.Graph stellt einige Tags wie boost::edge_weight_t bereit, um oft benötigte Eigenschaften zu definieren, die automatisch von Algorithmen erkannt und verwendet werden. Als zweiten Template-Parameter wird an boost::property der Typ übergeben, der für die Eigenschaft verwendet werden soll. Im Beispiel 31.11 sollen Gewichte über int-Zahlen definiert werden.

Beispiel 31.11 funktioniert, weil boost::dijkstra_shortest_paths() automatisch auf die mit Verbindungslinien gebündelte Eigenschaft vom Typ boost::edge_weight_t zugreift.

Beachten Sie, dass boost::dijkstra_shortest_paths() als dritten Parameter keinen Besucher bekommt. Dieser Algorithmus besucht nicht nur einfach Punkte, sondern hat das Ziel, den jeweils kürzesten Weg zu ermitteln – deswegen heißt der Algorithmus boost::dijkstra_shortest_paths(). Sie müssen sich also nicht überlegen, mit welchem Besucher Sie wie auf welches Ereignis reagieren wollen. Sie müssen lediglich einen Container übergeben, der von boost::dijkstra_shortest_paths() verwendet wird, um den Vorgänger zu jedem Punkt abzulegen. Wenn Sie wie im Beispiel 31.11 die Variante von boost::dijkstra_shortest_paths() verwenden, die Parameter mit Namen erwartet, übergeben Sie den Container mit boost::predecessor_map(). Es handelt sich hierbei um eine Hilfsfunktion, die wie andere einen Zeiger oder Iterator auf den Anfang eines Arrays erwartet.

Wenn Sie Beispiel 31.11 ausführen, wird 0, 3 und 2 ausgegeben: Der kürzeste Weg von links oben nach rechts unten führt über das linke untere Feld. Der Weg über das rechte obere Feld würde über eine Verbindung führen, die eine doppelte Gewichtung erhalten hat als alle anderen.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/array.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)
  }};

  struct edge_properties
  {
    int weight;
  };

  typedef boost::adjacency_list<boost::listS, boost::vecS,
    boost::undirectedS, boost::no_property,
    edge_properties> graph;

  graph g{edges.begin(), edges.end(), 4};

  graph::edge_iterator it, end;
  boost::tie(it, end) = boost::edges(g);
  g[*it].weight = 2;
  g[*++it].weight = 1;
  g[*++it].weight = 1;
  g[*++it].weight = 1;

  boost::array<int, 4> directions;
  boost::dijkstra_shortest_paths(g, bottomRight,
    boost::predecessor_map(directions.begin()).
    weight_map(boost::get(&edge_properties::weight, g)));

  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = directions[p];
  }
  std::cout << p << '\n';
}

Beispiel 31.12 funktioniert wie das vorherige und gibt das gleiche Ergebnis aus. Der Unterschied ist, dass nun nicht mehr eine vordefinierte Eigenschaft, sondern eine benutzerdefinierte Eigenschaft verwendet wird. So wird im Beispiel 31.12 nicht mehr auf boost::property zugegriffen. Mit edge_properties wird eine eigene Klasse als Eigenschaft für Verbindungen angegeben.

edge_properties definiert eine Variable weight, um das Gewicht einer Verbindung zu speichern. Es könnten beliebig viele weitere Variablen definiert werden, wenn zusätzliche Eigenschaften für Verbindungen notwendig sind.

Sie können auf benutzerdefinierte Eigenschaften zugreifen, wenn Sie den Deskriptor für Verbindungen als Index für den Graphen verwenden. Der Graph wird also wie ein Array behandelt. Die Deskriptoren wiederum erhalten Sie über die Iteratoren für Verbindungen, die von boost::edges() zurückgegeben werden. Auf diese Weise ist es möglich, jeder Verbindung ein Gewicht zuzuweisen.

Damit boost::dijkstra_shortest_paths() versteht, dass sich in der Variablen weight in edge_properties die Gewichte für Verbindungen befinden, muss jedoch ein zusätzlicher Parameter mit Namen übergeben werden. Dies geschieht mit Hilfe von weight_map(). Beachten Sie, dass es sich hierbei um eine Methode des Objekts handelt, das von boost::predecessor_map() zurückgegeben wird. Es existiert auch eine freistehende Funktion boost::weight_map(). Sollen mehrere Parameter mit Namen übergeben werden, müssen jedoch mehrfach Methoden des Objekts aufgerufen werden, das beim Aufruf der freistehenden Funktion zurückgegeben wird. Auf diese Weise werden alle Parameter in das eine Objekt gepackt, das dann dem Algorithmus übergeben wird.

Um boost::dijkstra_shortest_paths() mitzuteilen, dass weight in edge_properties die Gewichte enthält, wird der Zeiger auf diese Eigenschaft übergeben. Er wird nicht direkt an weight_map() übergeben, sondern in einem Objekt, das mit boost::get() erstellt werden muss. An dieser Stelle ist der Code komplett und boost::dijkstra_shortest_paths() versteht, wie auf welche Eigenschaft zugegriffen werden muss, um Gewichte zu erhalten.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/array.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)
  }};

  struct edge_properties
  {
    int weight;
  };

  typedef boost::adjacency_list<boost::listS, boost::vecS,
    boost::undirectedS, boost::no_property,
    edge_properties> graph;

  boost::array<edge_properties, 4> props{{2, 1, 1, 1}};

  graph g{edges.begin(), edges.end(), props.begin(), 4};

  boost::array<int, 4> directions;
  boost::dijkstra_shortest_paths(g, bottomRight,
    boost::predecessor_map(directions.begin()).
    weight_map(boost::get(&edge_properties::weight, g)));

  int p = topLeft;
  while (p != bottomRight)
  {
    std::cout << p << '\n';
    p = directions[p];
  }
  std::cout << p << '\n';
}

Wenn Sie mit benutzerdefinierten Eigenschaften arbeiten, können Sie diese auch beim Instanziieren des Graphen initialisieren. Sie müssen lediglich an den Konstruktor von boost::adjacency_list als dritten Parameter einen Iterator übergeben, der auf Objekte vom Typ der benutzerdefinierten Eigenschaft zeigt. Es ist also nicht notwendig, über Deskriptoren einzeln auf Eigenschaften von Verbindungen zuzugreifen. Beispiel 31.13 funktioniert genauso wie das vorherige Beispiel und gibt die gleichen Ergebnisse aus.

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/random_spanning_tree.hpp>
#include <boost/graph/named_function_params.hpp>
#include <boost/array.hpp>
#include <array>
#include <utility>
#include <random>
#include <iostream>
#include <ctime>
#include <cstdint>

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)
  }};

  struct edge_properties
  {
    int weight;
  };

  typedef boost::adjacency_list<boost::listS, boost::vecS,
    boost::undirectedS> graph;

  graph g{edges.begin(), edges.end(), 4};

  boost::array<int, 4> predecessors;

  std::mt19937 gen{static_cast<uint32_t>(std::time(0))};
  boost::random_spanning_tree(g, gen,
    boost::predecessor_map(predecessors.begin()).
    root_vertex(bottomLeft));

  int p = topRight;
  while (p != -1)
  {
    std::cout << p << '\n';
    p = predecessors[p];
  }
}

Abschließend wird Ihnen im Beispiel 31.14 ein Algorithmus vorgestellt, der zufällige Wegstrecken zurückgibt. boost::random_spanning_tree() funktioniert ähnlich wie boost::dijkstra_shortest_paths() und gibt die Vorgänger von Punkten in einem Container zurück, der mit boost::predecessor_map übergeben werden muss. Im Gegensatz zu boost::dijkstra_shortest_paths() wird der Punkt, zu dem die zufälligen Wegstrecken ermittelt werden sollen, nicht direkt an boost::random_spanning_tree() übergeben. Sie müssen ihn stattdessen als Parameter mit Namen übergeben. Deswegen wird für das Objekt vom Typ boost::predecessor_map root_vertex() aufgerufen. Im Beispiel 31.14 sollen also zufällige Wege zum Punkt links unten ermittelt werden.

Da boost::random_spanning_tree() einen zufälligen Weg finden soll, erwartet der Algorithmus als zweiten Parameter einen Zufallsgenerator. Im Beispiel 31.14 wird ein Objekt vom Typ std::mt19937 übergeben. Diese Klasse ist seit C++11 Teil der Standardbibliothek. Sie können auch einen Zufallsgenerator von Boost.Random verwenden.

Wenn Sie Beispiel 31.14 ausführen, wird Ihnen entweder 1, 0 und 3 oder 1, 2 und 3 ausgegeben. 1 ist das rechte obere Feld, 3 das linke untere Feld. Da man sowohl über das linke obere als auch das rechte untere Feld nach links unten gelangen kann, hängt es vom Zufall ab, welcher Weg von boost::random_spanning_tree() zurückgegeben wird.