1
我想在BGL圖上做區域生長。區域增長的想法是從指定的根頂點開始訪問頂點，並且收集並返回一個子圖或者與它們的父元素相比通過某個標準函數的頂點列表。例如，假設我們有一個簡單的圖形，看起來像這樣：在breadth_first_search期間設置頂點的顏色
A-B-C-D
和邊緣的權重分別是：
AB = 4，BC = 10， CD = 3
現在我們想長的區域開始答：我們要做到以下幾點：
- 發現一個，並把它添加到連接區域
- 發現B，並確定B是否與A「足夠相似」。對於此示例，可以說標準是邊權重的閾值：如果邊權重> 5，那麼我們不應該繼續遍歷B.所以在這裏，
AB = 4所以我們應該發展到B，但由於BC=10，我們應該永遠不會達到C.- 如果是這樣，添加B到所連接的區域，並繼續通過發現C和檢查如果C是B，等足夠相似。
- 如果沒有，停止，返回當前連接區域
我可以在訪問者的tree_edge函數中檢查這個標準函數。如果A和B太不相似，我試圖通過將傳遞到tree_edge的邊的目標頂點設置爲黑色來「停止」BFS繼續（將B添加到隊列中並稍後處理，等等）。然而，這似乎並沒有停止遍歷：
#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爲黑色。
任何人都可以解釋爲什麼這不工作，因爲我期望？