Boost Graphen mit Hilfe von Graphviz anzeigen


In unserem DV-Projekt verwenden wir einen Graphen für die interne Darstellung des Spielfeldes. Damit prüfen wir, ob ein Kraftwerk mit der Stadt über Stromtrassen verbunden ist. Dabei ist jedes Feld ein Knoten im Graph und die Kanten entsprechen den Verbindungen, welche über die Trassen hergestellt werden. Bei einer Spielfeldgröße von 20 x 20 Feldern besitzt auch der entsprechende Graph bereits eine beachtliche Größe.

Insbesondere für Debugging-Zwecke ist es praktisch, wenn man sich den Graphen auch darstellen lassen kann. Es gibt von Boost bereits vorgefertigte Methoden, welche den Graphen auf der Konsole ausgeben lassen, das wird aber bei größeren Graphen sehr schnell unübersichtlich. Zum Glück gibt es bei Boost aber auch die Möglichkeit den Graphen in der DOT-Sprache auszugeben.

Dabei können beispielsweise Knoten, Knotennamen, Kanten und Kantennamen ausgegeben werden. In unserem Fall sind für das Spielfeld nur die Knoten, Kanten und Knotennamen relevant. Für die Knotennamen wäre es wünschenswert, wenn im Namen die Indizierung auftauchen würde. Wir greifen auf die Knoten per Zeilen- und Spaltenindex zu, daher sollten diese auch im Knotennamen auftauchen.

Realisiert werden kann das wie im folgenden Beispiel zu sehen. Für die Namensgebung (Indizes) wird ein std::vector von std::string angelegt. Dort wird für jeden Eintrag im Graphen als Name das Paar (Zeilenindex, Spaltenindex) hinterlegt. Die eigentliche Arbeit verrichtet die Methode write_graphviz, welche einen Ausgabestream zu einem File, den Graphen und die gerade eben generierten Kennzeichnungen entgegen nimmt.


#include <boost/graph/graphviz.hpp>
using namespace boost;
...
std::vector<std::string> names(fieldLength*fieldLength);

for (int x = 0; x < fieldLength; x++) {
	for (int y = 0; y < fieldLength; y++) {
		names[convertIndex(x, y)] = names[convertIndex(x, y)] = std::to_string(x) + std::string(", ") + std::to_string(y);
	}
}

std::ofstream file;
file.open("graph.dot");
if (file.is_open()) {
	write_graphviz(file, powerLineGraph, make_label_writer(&names[0]));
}

Führt man diesen Code aus, so erhält man eine entsprechende graph.dot Datei. Um deren Inhalt nun anzuzeigen, wird noch Graphviz benötigt. Dort ist das Programm dot enthalten, welches die Datei lesen und daraus einen Graphen plotten kann. In unserem Fall ist der Graph sehr groß und gerade am Anfang haben viele Knoten noch gar keine Kanten. Daher wird vorher noch eine Filterung mit dem Programm gvpr durchgeführt, um alle Knoten ohne Kanten aus dem Graphen zu löschen. Eine entsprechende Batch-Datei könnte dabei wie folgt aussehen (in der ersten Zeile wird nur der Pfad zum graphviz Verzeichnis gesetzt):


set PATH=<YOUR_GRAPHVIZ_PATH>\bin;%PATH%
gvpr -c "N[$.degree==0]{delete(0,$);}" graph.dot | dot -Tpng > graph.png

Als Ergebnis erhält man dann beispielsweise folgenden Graphen:

Erzeugte Graphen