无向DFS：我如何提供彩色图作为外部属性？-Java 学习之路

我正在使用无向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，名为"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函数调用不适用于此图形类型定义 . 对于顶点，手册指出提供了默认值，并且它只使用特定的顶点类型和边缘类型构建得很好，如上所示 . 但是如果我想要一个特定的边缘类型，我得出的结论是我需要分别提供算法所需的颜色，因为我不能使用示例代码中所示的属性 . 所以我认为这可以通过提供它们作为“外部属性”来完成 .

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

Manual excerpt：

UTIL：edge_color_map（EdgeColorMap edge_color）算法使用它来跟踪已访问的边缘 . EdgeColorMap类型必须是读/写属性映射的模型，其键类型必须是图的边描述符类型，并且颜色映射的值类型必须为ColorValue建模 .

我不清楚这一点，我试图阅读有关属性 Map 的部分，但我无法得到它 .

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

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

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

DEMO

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

回复于 2024-04-28T01:57:45+08:00

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

1 回答

DEMO

相关问题