BFS generisch und schnell

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.

One thought on “BFS generisch und schnell

Hinterlasse eine Antwort

Deine E-Mail-Adresse wird nicht veröffentlicht.

Du kannst folgende HTML-Tags benutzen: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>