BGL - 傳遞給訪客函數的圖忘記頂點屬性

Question

我試圖通過編寫自定義DFS訪問者（class TarjanVisitor : public default_dfs_visitor）在BGL中實現橋檢測算法（tarjan），並且我使用頂點屬性parent來保留追蹤到達節點的路徑。

但是，我似乎無法在遍歷過程中設置頂點的屬性，而不訴諸於某些訪客全局引用。

在我的具體情況，我有我的tree_edge如下：

debug_print("setting " << g[trgt].id << "'s parent to " << g[curr].id) 
g[trgt].parent = g[curr].id; 
debug_print(g[trgt].id << "'s parent is now " << g[trgt].parent) 

（debug_print就是，我可以通過取消定義宏關閉打印）

然後在discover_vertex，我有

debug_print(g[u].id << "'s parent is " << g[u].parent) 
assert(g[u].parent >= 0); 

，我設置爲1根及其parent本身啓動DFS遍歷。

TarjanVisitor vis = TarjanVisitor(); 
g[vertex(1,g)].parent = 1; 
depth_first_search(g,visitor(vis) 
    .root_vertex(vertex(1,g)) //note to self: DOT, not comma 
); 

這裏的（清潔）調試輸出我得到：

discover_vertex: 1 
1's parent is 1 
examine_edge: 1 <-> 2 
tree_edge: 1 <-> 2 
setting 2's parent to 1 
2's parent is now 1 
discover_vertex: 2 
2's parent is -1 
Assertion `g[u].parent >= 0' failed. 
Aborted (core dumped) 

現在，如果不是使用圖形傳遞到各個功能，我傳遞一個參考圖表的訪問者的構造函數並使用Graph作爲g，屬性如預期更新，所以我只能猜測問題是g在eg void tree_edge(Edge e, Graph g)通過值傳遞圖並忽略對其所做的任何更改。

更改爲例如void tree_edge(Edge e, Graph& g)將在我的例子boost::detail::depth_first_visit_impl實例化過程中爲我提供一個很長且絕對難以辨認的錯誤消息。

傳遞給訪問者的引用真的是唯一的途徑嗎？因爲我有點拒絕相信我需要通過價值將圖表傳遞給所有函數，而不是而不是。

Answer 1

我剛剛有一個腦電波。你說你試過

void tree_edge(Edge e, Graph& g) { ... 

如果圖是常量（這就像因爲DFS的BGL實施的情況下當然就不能正常工作。

讓它const引用！

Live On Coliru

#include <iostream> 
#include <boost/graph/adjacency_list.hpp> 
#include <boost/graph/depth_first_search.hpp> 

using namespace boost; 

struct MyVertex {}; 
struct MyEdge {}; 

using Graph = adjacency_list<vecS, vecS, directedS, MyVertex, MyEdge>; 

struct my_visitor : default_dfs_visitor { 
    template <class Vertex, class Graph> 
     void initialize_vertex(Vertex u, const Graph& g) { 
      std::cout << __FUNCTION__ << "(" << u << ", g)\n"; 
      (void) g; 
     } 
    template <class Vertex, class Graph> 
     void start_vertex(Vertex u, const Graph& g) { 
      std::cout << __FUNCTION__ << "(" << u << ", g)\n"; 
      (void) g; 
     } 
    template <class Vertex, class Graph> 
     void discover_vertex(Vertex u, const Graph& g) { 
      std::cout << __FUNCTION__ << "(" << u << ", g)\n"; 
      (void) g; 
     } 
    template <class Edge, class Graph> 
     void examine_edge(Edge u, const Graph& g) { 
      std::cout << __FUNCTION__ << "(" << u << ", g)\n"; 
      (void) g; 
     } 
    template <class Edge, class Graph> 
     void tree_edge(Edge u, const Graph& g) { 
      std::cout << __FUNCTION__ << "(" << u << ", g)\n"; 
      (void) g; 
     } 
    template <class Edge, class Graph> 
     void back_edge(Edge u, const Graph& g) { 
      std::cout << __FUNCTION__ << "(" << u << ", g)\n"; 
      (void) g; 
     } 
    template <class Edge, class Graph> 
     void forward_or_cross_edge(Edge u, const Graph& g) { 
      std::cout << __FUNCTION__ << "(" << u << ", g)\n"; 
      (void) g; 
     } 
    template <class Edge, class Graph> 
     void finish_edge(Edge u, const Graph& g) { 
      std::cout << __FUNCTION__ << "(" << u << ", g)\n"; 
      (void) g; 
     } 
    template <class Vertex, class Graph> 
     void finish_vertex(Vertex u, const Graph& g) { 
      std::cout << __FUNCTION__ << "(" << u << ", g)\n"; 
      (void) g; 
     } 
}; 

#include <random> 
#include <boost/graph/random.hpp> 

int main() { 
    Graph g; 

    std::mt19937 prng {42}; 
    generate_random_graph(g, 10, 20, prng); 

    my_visitor vis; 
    std::vector<default_color_type> colormap(num_vertices(g)); 
    depth_first_search(g, vis, make_iterator_property_map(colormap.begin(), get(vertex_index, g))); 
} 

打印

initialize_vertex(0, g) 
initialize_vertex(1, g) 
initialize_vertex(2, g) 
initialize_vertex(3, g) 
initialize_vertex(4, g) 
initialize_vertex(5, g) 
initialize_vertex(6, g) 
initialize_vertex(7, g) 
initialize_vertex(8, g) 
initialize_vertex(9, g) 
start_vertex(0, g) 
discover_vertex(0, g) 
examine_edge((0,4), g) 
tree_edge((0,4), g) 
discover_vertex(4, g) 
examine_edge((4,1), g) 
tree_edge((4,1), g) 
discover_vertex(1, g) 
finish_vertex(1, g) 
finish_vertex(4, g) 
examine_edge((0,9), g) 
tree_edge((0,9), g) 
discover_vertex(9, g) 
examine_edge((9,1), g) 
forward_or_cross_edge((9,1), g) 
examine_edge((9,2), g) 
tree_edge((9,2), g) 
discover_vertex(2, g) 
finish_vertex(2, g) 
examine_edge((9,1), g) 
forward_or_cross_edge((9,1), g) 
finish_vertex(9, g) 
examine_edge((0,1), g) 
forward_or_cross_edge((0,1), g) 
examine_edge((0,4), g) 
forward_or_cross_edge((0,4), g) 
examine_edge((0,2), g) 
forward_or_cross_edge((0,2), g) 
finish_vertex(0, g) 
start_vertex(3, g) 
discover_vertex(3, g) 
examine_edge((3,7), g) 
tree_edge((3,7), g) 
discover_vertex(7, g) 
examine_edge((7,5), g) 
tree_edge((7,5), g) 
discover_vertex(5, g) 
examine_edge((5,1), g) 
forward_or_cross_edge((5,1), g) 
examine_edge((5,6), g) 
tree_edge((5,6), g) 
discover_vertex(6, g) 
examine_edge((6,1), g) 
forward_or_cross_edge((6,1), g) 
examine_edge((6,3), g) 
back_edge((6,3), g) 
examine_edge((6,5), g) 
back_edge((6,5), g) 
finish_vertex(6, g) 
finish_vertex(5, g) 
examine_edge((7,6), g) 
forward_or_cross_edge((7,6), g) 
examine_edge((7,8), g) 
tree_edge((7,8), g) 
discover_vertex(8, g) 
examine_edge((8,3), g) 
back_edge((8,3), g) 
finish_vertex(8, g) 
finish_vertex(7, g) 
examine_edge((3,1), g) 
forward_or_cross_edge((3,1), g) 
finish_vertex(3, g)