通过图权重增强深度优先访问者最小生成树

本文介绍了通过图权重增强深度优先访问者最小生成树的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我想从具有边缘权重的顶点创建最小生成树，并以深度优先的顺序遍历图形.我可以构建图形和最小生成树，但是编写自定义访问者失败.

I want to create a minimum spanning tree from vertices with edge weights and traverse the graph in depth-first order. I can build the graph and the minimum spanning tree but I am failing at writing the custom visitor.

#include <iostream> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/kruskal_min_spanning_tree.hpp> #include <boost/graph/depth_first_search.hpp> #include <boost/graph/graph_traits.hpp> #include <vector> #include <string> typedef boost::property<boost::edge_weight_t, double> EdgeWeightProperty; typedef boost::adjacency_list < boost::listS, boost::vecS, boost::undirectedS, boost::no_property, EdgeWeightProperty> MyGraph; typedef MyGraph::edge_descriptor Edge; class MyVisitor : public boost::default_dfs_visitor { public: void tree_edge(Edge e, const MyGraph& g) const { } }; void mst() { MyGraph g; boost::add_edge(0, 1, 0.7, g); boost::add_edge(0, 2, 0.1, g); boost::add_edge(1, 2, 0.3, g); boost::add_edge(1, 0, 0.7, g); boost::add_edge(1, 3, 0.8, g); boost::add_edge(1, 4, 0.2, g); boost::add_edge(2, 1, 0.3, g); boost::add_edge(2, 0, 0.1, g); boost::add_edge(2, 5, 0.1, g); boost::add_edge(2, 4, 0.5, g); boost::add_edge(3, 1, 0.8, g); boost::add_edge(4, 1, 0.2, g); boost::add_edge(4, 2, 0.5, g); boost::add_edge(5, 2, 0.1, g); std::list <Edge> spanning_tree; boost::kruskal_minimum_spanning_tree(g, std::back_inserter(spanning_tree)); // the following two lines are failing MyVisitor vis(); boost::depth_first_search(spanning_tree, visitor(vis)); } int main(int argc, char** argv) { mst(); std::cin.get(); return (0); }

我想访问自定义访问者中的顶点和边缘权重.这可能吗?我看到了这篇文章:提升最小生成树，如何进行深度首先?，但我宁愿不构建单独的体重图.

I would like to access the vertices and edge weights in the custom visitor. Is this possible? I saw this post: boost minimum spanning tree, how to do depth first? but I would prefer to not build a separate weight map.

此外，是否可以使用boost工具在深度树优先的顺序中进行迭代，而无需编写自定义访问者?

Additionally, is it possible to iterate in depth-first order through the tree with boost tools without writing a custom visitor?

推荐答案

MyVisitor vis();

那是一个函数声明.请参见大多数恼人的解析器

That is a function declaration. See Most Vexing Parse

boost::depth_first_search(spanning_tree, visitor(vis));

在std::list<Edge>上调用图算法. depth_first_search 需要一个对正确的图形概念建模的图形:

That calls the graph algorithm on a std::list<Edge>. depth_first_search requires a graph that models the right graph concepts:

std :: list都不建模.

The std::list models neither.

您可以构建仅包含MST集中的边缘的图形.您链接到的问题的答案可以尝试.

You could build a graph including just the edges from the MST set. The answer to the question you linked to tries that.

但是，创建同一图形的filtered_graph<>视图似乎更加容易和有效，因此可以通过相同的机制简单地获得边缘属性.

However, it seems easier and more efficient to create a filtered_graph<> view of the same graph, so that the edge properties are simply available through the same mechanism.

首先，让我们更喜欢在set<>而不是list<>中获得MST边缘:

First, let's prefer to get the MST edges in a set<> instead of a list<>:

struct InSpanning { std::set<Edge> edges; bool operator()(Edge e) const { return edges.count(e); } } spanning; boost::kruskal_minimum_spanning_tree(g, std::inserter(spanning.edges, spanning.edges.end()));

您会注意到的有趣的事情是InSpanning也是也是一个函数对象，可用作filtering_graph的过滤谓词:

The interesting thing you'll note is that InSpanning is also a function object that be used as a filtering predicate for filtering_graph:

boost::filtered_graph<MyGraph, InSpanning, boost::keep_all> mst(g, spanning, {});

现在您可以致电de DFS:

Now you can call de DFS:

boost::depth_first_search(mst, visitor(vis));

我已经微调了访客的位置:

I've tweaked the visitor slightly:

struct MyVisitor : boost::default_dfs_visitor { template <typename Graph> void tree_edge(Edge e, const Graph& g) { std::cout << "Visiting: " << e << " with weight " << get(boost::edge_weight, g, e) << "\n"; } };

注意:

它不再对MyGraph类型进行硬编码(因为filtered_graph具有不同的类型).

它会打印您想要查看的信息.

It doesn't hardcode the MyGraph type anymore (because the filtered_graph has a different type).

It prints the information you wanted to see.

实时演示

在Coliru上直播 #include <boost/graph/adjacency_list.hpp> #include <boost/graph/filtered_graph.hpp> #include <boost/graph/depth_first_search.hpp> #include <boost/graph/kruskal_min_spanning_tree.hpp> #include <iostream> #include <string> #include <vector> typedef boost::property<boost::edge_weight_t, double> EdgeWeightProperty; typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS, boost::no_property, EdgeWeightProperty> MyGraph; typedef MyGraph::edge_descriptor Edge; struct MyVisitor : boost::default_dfs_visitor { template <typename Graph> void tree_edge(Edge e, const Graph& g) { std::cout << "Visiting: " << e << " with weight " << get(boost::edge_weight, g, e) << "\n"; } }; void run_mst_test() { MyGraph g; boost::add_edge(0, 1, 0.7, g); boost::add_edge(0, 2, 0.1, g); boost::add_edge(1, 2, 0.3, g); boost::add_edge(1, 0, 0.7, g); boost::add_edge(1, 3, 0.8, g); boost::add_edge(1, 4, 0.2, g); boost::add_edge(2, 1, 0.3, g); boost::add_edge(2, 0, 0.1, g); boost::add_edge(2, 5, 0.1, g); boost::add_edge(2, 4, 0.5, g); boost::add_edge(3, 1, 0.8, g); boost::add_edge(4, 1, 0.2, g); boost::add_edge(4, 2, 0.5, g); boost::add_edge(5, 2, 0.1, g); struct InSpanning { std::set<Edge> edges; bool operator()(Edge e) const { return edges.count(e); } } spanning; boost::kruskal_minimum_spanning_tree(g, std::inserter(spanning.edges, spanning.edges.end())); MyVisitor vis; boost::filtered_graph<MyGraph, InSpanning, boost::keep_all> mst(g, spanning, {}); boost::depth_first_search(mst, visitor(vis)); } int main() { run_mst_test(); }

打印

Visiting: (0,2) with weight 0.1 Visiting: (2,1) with weight 0.3 Visiting: (1,3) with weight 0.8 Visiting: (1,4) with weight 0.2 Visiting: (2,5) with weight 0.1