c++ - 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)

现在，如果我不使用传递给各个函数的图形，而是将图形的引用传递给访问者的构造函数，并将该图形用作 g，则属性将更新为预期的，所以我只能猜测问题是 g 在例如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) { ...

如果图形是 const 的，那当然是行不通的(这就像在 BGL 中实现 dfs 的情况一样。

让它成为常量引用!

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)