c++ - 无向 DFS : how can I provide color maps as exterior properties?

Question

我正在使用无向 DFS ( Depth First Search ) 算法 implemented in boost::graph .

此算法需要顶点和边上的颜色值来跟踪已解析的颜色值。在 the provided example ，代码将这些颜色值存储为图形的内部属性:

typedef adjacency_list<
    vecS,
    vecS,
    undirectedS,
    no_property,       // vertex properties
    property<edge_color_t, default_color_type> // edge colors
> graph_t;

调用是使用“命名属性”版本完成的:

undirected_dfs(g, root_vertex(vertex_t(0)).visitor(vis)
             .edge_color_map(get(edge_color, g)));

我的问题是我有顶点和边的自定义值。我用的似乎是 the preferred way of doing ， 这就是所谓的“捆绑属性”:

struct my_vertex { int a1; float a2; }
struct my_edge   { int b1; float b2; }
typedef adjacency_list<
    vecS,
    vecS,
    undirectedS,
    my_vertex,       // vertex properties
    my_edge          // edge properties
> graph_t;

当然，之前的DFS函数调用对这个图类型定义不起作用。对于顶点，手册指出提供了默认值，并且它确实可以仅使用特定的顶点类型和边类型构建良好，如上所示。但是如果我想要特定的边缘类型，我得出的结论是我需要单独提供算法所需的颜色，因为我不能使用示例代码中所示的属性。所以我认为这可以通过将它们提供为“外部属性”来完成。

我的问题是:我该怎么做？

Manual excerpt :

UTIL: edge_color_map(EdgeColorMap edge_color) This is used by the algorithm to keep track of which edges have been visited. The type EdgeColorMap must be a model of Read/Write Property Map and its key type must be the graph's edge descriptor type and the value type of the color map must model ColorValue.

这对我来说不清楚，我已经尝试阅读有关属性映射的部分，但我就是无法理解。

在this answer的帮助下，我在下面尝试过，但是失败了:(使用“未命名参数”版本)

std::vector<int> edge_color(   boost::num_edges(g), 0);
std::vector<int> vertex_color( boost::num_vertices(g), 0 );

boost::undirected_dfs(
    g,
    boost::visitor( boost::default_dfs_visitor() ),
    boost::vertex_color_map( vertex_color ),
    boost::edge_color_map( edge_color ),
    boost::root_vertex( vertex_t(0) )
);

如果有人能指出我正确的方向......

Answer 1

您需要满足记录的确切参数要求:http://www.boost.org/doc/libs/1_63_0/libs/graph/doc/undirected_dfs.html

这意味着您/可以/摆脱顶点颜色的 vector ，但边缘颜色需要在关联容器中，因为边缘描述符不像顶点描述符用于您的图形类型那样是完整的。

std::vector<default_color_type> vertex_color(num_vertices(g));
std::map<graph_t::edge_descriptor, default_color_type> edge_color;

auto idmap = get(vertex_index, g);
auto vcmap = make_iterator_property_map(vertex_color.begin(), idmap);
auto ecmap = make_assoc_property_map(edge_color);

graph_t::vertex_descriptor const start = 0;

现在您可以调用算法的固定参数版本:

undirected_dfs(g, vis, vcmap, ecmap, start);

或者，使用命名参数版本调用完全相同的方法:

undirected_dfs(g, 
        root_vertex(graph_t::vertex_descriptor(0))
        .visitor(vis)
        .vertex_color_map(vcmap)
        .edge_color_map(ecmap)
    );

演示

Live On Coliru

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

using namespace boost;

struct my_vertex { int a1; float a2; };
struct my_edge   { int b1; float b2; };

struct detect_loops : public boost::dfs_visitor<> {
    template <class Edge, class Graph>
    void back_edge(Edge e, const Graph& g) {
        std::cout << g[source(e,g)].a1 << " -- " << g[target(e,g)].a1 << "\n";
    }
};


typedef adjacency_list<vecS, vecS, undirectedS, my_vertex, my_edge> graph_t;

int main() {
    detect_loops vis;

    graph_t g;

    std::vector<default_color_type> vertex_color(num_vertices(g));
    std::map<graph_t::edge_descriptor, default_color_type> edge_color;

    auto idmap = get(vertex_index, g);
    auto vcmap = make_iterator_property_map(vertex_color.begin(), idmap);
    auto ecmap = make_assoc_property_map(edge_color);

    graph_t::vertex_descriptor const start = 0;

    undirected_dfs(g, vis, vcmap, ecmap, start);

    undirected_dfs(g, 
            root_vertex(graph_t::vertex_descriptor(0))
            .visitor(vis)
            .vertex_color_map(vcmap)
            .edge_color_map(ecmap)
        );
}