This weekend, originally I wanted to implement special BFS procedures for my student job, of course using generic programming and the like. Looking at the normal BFS implementation in Boost I noticed that it needs a ColorMap and allocates one as the default behavior. However, in many applications of breadth-first search one can use another map for this purpose, like one for distance or predecessors, and interpret a special value like -1 or the null pointer as white, i.e. not visited. Then one can no longer distinguish between gray and black nodes, though (I have not understood how this can become relevant for BFS – for DFS it’s clear), but one does not have to anyway in most applications. Doing so, one saves the memory for another map – normally one byte per vertex – and the overhead for updating it.

So I started working on an implementation of the ReadWritePropertyMap concept that is initialized with another map and a value for “white” and when queried for the color of a vertex reads the value of the underlying map and determines whether it is white. Write operations just do nothing. This was not totally easy, as with all this template stuff, even small mistakes lead to very long diagnostics. But the result is now here. So now there remains just the issue with the Koenig lookup, but I hope this will be solved as well …

Dieses Wochenende wollte ich eigentlich Spezialbreitensuchmethoden für meinen Hiwi-Job implementieren, natürlich generisch und so. Beim Anschauen der normalen BFS in Boost fiel mir auf, daß das Teil ja eine ColorMap benötigt und standardmäßig eine anlegt. Dabei kann man ja für viele Anwendungen der Breitensuche dafür eine andere Map, zum Beispiel für Distanz oder Vorgänger, verwenden, und einen speziellen Wert, wie -1 oder den Nullpointer, als weiß, also unbesucht, ansehen. Dann kann man zwar nicht mehr zwischen grauen und schwarzen Knoten unterscheiden (mir ist noch nicht ganz klar geworden, welche Relevanz das überhaupt bei BFS haben kann – bei DFS ist es klar), aber das muß man ja in den meisten Anwendungen auch nicht. Damit spart man dann den Speicherplatz für eine weitere Map – immerhin im Regelfall ein Byte pro Knoten – und den Overhead für das Update derselben.

Also hab ich mich daran gemacht, eine Implementierung des Konzepts ReadWritePropertyMap zu erstellen, die mit einer anderen Map und einem “Weiß-Wert” initialisiert wird und bei Anfragen nach der Farbe eines Knoten den Wert aus der zugrundeliegenden Map liest und guckt, ob der Knoten weiß ist. Schreibzugriffe gehen einfach ins leere. Das Ganze war nicht ganz einfach, da mit dem Template-Geraffel auch kleine Fehler zu ellenlangen Fehlermeldungen führen. Aber das Ergebnis ist jetzt hier. Bleibt nur noch die Sache mit dem Koenig-Lookup, aber die wird mir hoffentlich auch jemand beantworten.