- Java 双重比较
- java - 比较器与 Apache BeanComparator
- Objective-C 完成 block 导致额外的方法调用?
- database - RESTful URI 是否应该公开数据库主键?
我正在尝试使用 boost::lengauer_tarjan_dominator_tree带有 custom vertex properties 的图表,但连一个简单的例子都无法编译:
#include <vector>
#include <iterator>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dominator_tree.hpp>
#include <boost/property_map/property_map.hpp>
struct GraphNode
{
explicit GraphNode(unsigned i) : index {i} {}
unsigned index;
};
using Graph = boost::adjacency_list<boost::listS, boost::listS,
boost::bidirectionalS, GraphNode, boost::no_property>;
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
int main()
{
Graph g {};
const auto u = boost::add_vertex(GraphNode {0}, g);
const auto v = boost::add_vertex(GraphNode {1}, g);
const auto x = boost::add_vertex(GraphNode {2}, g);
const auto y = boost::add_vertex(GraphNode {3}, g);
const auto z = boost::add_vertex(GraphNode {4}, g);
boost::add_edge(u, v, g);
boost::add_edge(u, x, g);
boost::add_edge(v, y, g);
boost::add_edge(x, y, g);
boost::add_edge(y, z, g);
const auto index_map = boost::get(&GraphNode::index, g);
std::vector<Vertex> dom_tree_pred_vector(boost::num_vertices(g),
boost::graph_traits<Graph>::null_vertex());
auto dom_tree_pred_map = boost::make_iterator_property_map(std::begin(dom_tree_pred_vector),
index_map);
boost::lengauer_tarjan_dominator_tree(g, u, dom_tree_pred_map);
}
我试图从 example 改编而来在文档中给出。
这是错误信息的一部分:
/usr/local/include/boost/graph/detail/adjacency_list.hpp:2544:33: error: cannot form a reference to 'void'
typedef const value_type& const_reference;
^
/usr/local/include/boost/graph/dominator_tree.hpp:355:31: error: no matching function for call to 'get'
const IndexMap indexMap = get(vertex_index, g);
我还尝试使用方法的第二种形式显式传递索引映射,但没有成功。我注意到这个方法接口(interface)似乎与其他图形方法有点不同,例如 depth_first_search ,其中 vertex_index_map
是命名参数。
是否可以将此方法与自定义顶点属性一起使用?
最佳答案
问题 - 一如既往 - 是为顶点容器使用 vecS
以外的东西。您丢失了内置的 vertex_index
属性,因此必须将其提供给 API。
遗憾的是,该算法不能很好地支持自定义顶点索引映射。您通过使用 index_map
尝试了 - 正确 - 但在内部算法仍在寻找 vertex_index_t
标记的属性。
我能看到这项工作的唯一两种方式是,
手动执行 DFS 阶段(因为即使 lengauer_tarjan*
的全参数重载也无法将正确的索引映射转发到 DFS)。然后您可以调用 lengauer_tarjan_dominator_tree_without_dfs
实现并获得结果。
或者您可以将图表的索引图告知图书馆。
(最后,您可以接受命运并使用 vecS
作为顶点容器选择器。我怀疑这显然不是您想要的。)
使用第二种方法,这可能是最优雅的。以下是要添加的特化/重载:
namespace boost {
template <>
struct property_map<Graph, vertex_index_t> {
typedef typename property_map<Graph, size_t GraphNode::*>::type type;
typedef typename property_map<Graph, size_t GraphNode::*>::const_type const_type;
};
static auto get(vertex_index_t, Graph& g) { return get(&GraphNode::index, g); }
static auto get(vertex_index_t, Graph const& g) { return get(&GraphNode::index, g); }
}
#include <vector>
#include <iterator>
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dominator_tree.hpp>
#include <boost/property_map/property_map.hpp>
struct GraphNode
{
explicit GraphNode(size_t i) : index {i} {}
size_t index;
};
using Graph = boost::adjacency_list<boost::listS, boost::listS, boost::bidirectionalS, GraphNode, boost::no_property>;
namespace boost {
template <>
struct property_map<Graph, vertex_index_t> {
typedef typename property_map<Graph, size_t GraphNode::*>::type type;
typedef typename property_map<Graph, size_t GraphNode::*>::const_type const_type;
};
static property_map<Graph, vertex_index_t>::type get(vertex_index_t, Graph& g) { return get(&GraphNode::index, g); }
static property_map<Graph, vertex_index_t>::const_type get(vertex_index_t, Graph const& g) { return get(&GraphNode::index, g); }
}
using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
int main()
{
Graph g {};
const auto u = boost::add_vertex(GraphNode {0}, g);
const auto v = boost::add_vertex(GraphNode {1}, g);
const auto x = boost::add_vertex(GraphNode {2}, g);
const auto y = boost::add_vertex(GraphNode {3}, g);
const auto z = boost::add_vertex(GraphNode {4}, g);
boost::add_edge(u, v, g);
boost::add_edge(u, x, g);
boost::add_edge(v, y, g);
boost::add_edge(x, y, g);
boost::add_edge(y, z, g);
std::vector<Vertex> dom_pred(num_vertices(g), boost::graph_traits<Graph>::null_vertex());
auto index_map = boost::get(&GraphNode::index, g); // equivalent to vertex_index_t now
auto dom_tree_pred_map (boost::make_iterator_property_map(std::begin(dom_pred), index_map));
// Run main algorithm
boost::lengauer_tarjan_dominator_tree(g, u, dom_tree_pred_map);
std::cout << "Result: ";
for (auto v : dom_pred) {
if (v == boost::graph_traits<Graph>::null_vertex())
std::cout << "(root) ";
else
std::cout << g[v].index << " ";
}
}
打印
Result: (root) 0 0 0 3
关于c++ - 为具有自定义顶点属性的图 boost 支配树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36387730/
我是一名优秀的程序员,十分优秀!