无向 DFS：如何提供彩色贴图作为外部属性？

Question

我正在使用无向 DFS (Depth First Search) algorithm 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;

调用是使用 "named properties" 版本完成的：

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

我的问题是我有顶点和边的自定义值。我使用的似乎是the preferred way of doing，它被称为 "bundled properties":

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函数调用不适用于这种图类型定义。对于顶点，手册指出提供了默认值，并且它确实可以仅使用特定的顶点类型和边类型构建良好，如上所示。但是如果我想要特定的边缘类型，我得出的结论是我需要单独提供算法所需的颜色，因为我不能使用示例代码中所示的属性。所以我认为这可以通过将它们提供为 "exterior properties".

来完成

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

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 的帮助下，我在下面尝试了这个，但是失败了：（使用 "unnamed parameter" 版本）

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

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

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

无向 DFS：如何提供彩色贴图作为外部属性？

undirected DFS: how can I provide color maps as exterior properties?

c++

boost

depth-first-search

boost-graph

演示