Setting the color of a vertex during breadth_first_search

Question

I would like to do region growing on a BGL graph. The idea of region growing is to visit vertices, starting from a specified root vertex, and collect and return a subgraph or a list of vertices that passed some criterion function as compared to their parent. For example, say we have a simple graph that looks like this:

A-B-C-D

and the edge weights are:

AB = 4, BC = 10, CD = 3

Now we want to grow a region starting at A. We want to do the following:

• Discover A and add it to the connected region
• Discover B, and decide if B is "similar enough" to A. For this example, lets say the criterion is a threshold on the edge weight: if the edge weight is > 5, then we should not continue traversing to B. So here, AB = 4 so we should grow to B, but since BC=10, we should never reach C.
  • If so, add B to the connected region and continue by discovering C and checking if C is similar enough to B, etc.
  • If not, stop and return the current connected region

I can check this criterion function in the tree_edge function of the visitor. If A and B are too dissimilar, I tried to "stop" the BFS from continuing (adding B to the queue and then processing it later, etc.) by setting the target vertex of the edge passed to tree_edge to black. However, this doesn't seem to stop the traversal:

#include <iostream>

#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/breadth_first_search.hpp>

using EdgeWeightProperty = boost::property<boost::edge_weight_t, float>;

using ColorPropertyType = boost::property<boost::vertex_color_t, boost::default_color_type>;

using GraphType =  boost::adjacency_list<boost::setS, // out edge container
                                         boost::vecS, // vertex container
                                         boost::undirectedS, // directed or undirected
                                         ColorPropertyType, // vertex properites
                                         EdgeWeightProperty> // edge properties
                                         ;

template <typename TGraph>
void printColors(const TGraph& g)
{
    const auto& colorMapGraph = get(boost::vertex_color_t(), g);

    std::cout << "colors: ";
    for(unsigned int i = 0; i < num_vertices(g); ++i) {
        std::cout << get(colorMapGraph, vertex(i, g)) << " ";
    }

    std::cout << std::endl;
}

class BreadthFirstSearchVisitor : public boost::default_bfs_visitor
{
public:

    // We must provide a mutable version of the graph to the visitor since we want to change properties
    BreadthFirstSearchVisitor(GraphType& graph) : mGraph(graph) {}

    template < typename TEdge, typename TGraph>
    void tree_edge(TEdge e, const TGraph& g) const
    {
        std::cout << std::endl << "tree_edge: " << e << std::endl;
        printColors(g);
        const auto& colors = get(boost::vertex_color_t(), mGraph); // Though this is const&, you can still call put()

        const auto& edgeWeights = get(boost::edge_weight_t(), mGraph);

        boost::graph_traits<GraphType>::vertex_descriptor targetVertex = boost::target(e, g);
        std::cout << "targetVertex: " << targetVertex << std::endl;

        float edgeWeight = get(edgeWeights, e);
        std::cout << "edgeWeight: " << edgeWeight << std::endl;

        if(edgeWeight > 5.f) {
            std::cout << "Next vertex does not belong to the region!" << std::endl;
            put(colors, vertex(targetVertex, mGraph), boost::color_traits<GraphType>::black());
            printColors(g);
        }

    }

    // A very strange pattern, but this is (officially) recommended here: http://stackoverflow.com/a/2608616/284529
    GraphType& mGraph;
};

int main(int,char*[])
{
    // Create a graph object
    GraphType g(4);

    EdgeWeightProperty e0 = 4.f;
    add_edge(0, 1, e0, g);

    EdgeWeightProperty e1 = 10.f;
    add_edge(1, 2, e1, g);

    EdgeWeightProperty e2 = 3.f;
    add_edge(2, 3, e2, g);

    BreadthFirstSearchVisitor breadthFirstSearchVisitor(g);

    unsigned int startVertex = 0;

    // named argument signature
    breadth_first_search(g, vertex(startVertex, g), visitor(breadthFirstSearchVisitor).color_map(get(boost::vertex_color_t(), g)));

    return 0;
}

The output is:

tree_edge: (0,1)
colors: 1 0 0 0 
targetVertex: 1
edgeWeight: 4

tree_edge: (1,2)
colors: 4 1 0 0 
targetVertex: 2
edgeWeight: 10
Next vertex does not belong to the region!
colors: 4 1 4 0 

tree_edge: (2,3)
colors: 4 4 1 0 
targetVertex: 3
edgeWeight: 3

but I would have expected it not to ever call tree_edge with edge (2,3) because we marked vertex 2 as black.

Can anyone explain why this doesn't work as I'd expect?

Answer 1

The answer seems to simply be to change from handling tree_edge in the visitor to examine_edge instead. I guess the target vertex has already been added to the queue once tree_edge gets called, so it's color no longer matters (as the color is used to determine if a vertex should be added to the queue).