BFS – generic and fast

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 …

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>