Настройка цвета вершины во время breadth_first_search

Question

Хотелось бы заняться регионом, растущим на графике BGL. Идея развития региона состоит в том, чтобы посещать вершины, начиная с заданной вершины корня, и собирать и возвращать подграф или список вершин, которые передавали некоторую функцию критерия по сравнению с их родителями. Например, скажем, у нас есть простой график, который выглядит следующим образом:

A-B-C-D 

и краевые веса:

AB = 4, BC = 10, CD = 3

Теперь мы хотите вырастить область, начиная с А. Мы хотим сделать следующее:

• Discover а и добавить его в связной области
• Откройте B и определите, является ли B «достаточно похожим» на A. В этом примере допустим, что критерий является порогом на весу края: если вес края равен> 5, то мы не должны продолжать движение к B. Так здесь, AB = 4 поэтому мы должны вырасти до B, но так как BC=10, мы никогда не должны достичь С.
  • Если это так, добавьте B в связной области и продолжить обнаруживая C и проверки, если C достаточно похож на B, и т.д. .
  • Если нет, то остановить и вернуть тока, соединенный область

Я могу проверить эту функцию критерия в функции tree_edge посетителя. Если A и B слишком разнородны, я попытался «остановить» BFS от продолжения (добавив B в очередь, а затем обработать позже и т. Д.), Установив целевую вершину ребра, переданного в tree_edge, на черный. Однако, это не похоже, чтобы остановить обход:

#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; 
} 

Выход есть:

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 

, но я бы ожидал, что это не всегда называют tree_edge с краем (2,3), потому что мы отметили вершину 2, как черный.

Может кто-нибудь объяснить, почему это не работает, как я ожидал?

Answer 1

Ответ, похоже, просто изменится с обращения tree_edge на посетителя examine_edge. Я предполагаю, что целевая вершина уже добавлена ​​в очередь после вызова tree_edge, поэтому цвет больше не имеет значения (поскольку цвет используется для определения того, должна ли быть добавлена ​​вершина в очередь).