boost::get boost::filtered_graph 在 adjacency_list 上具有 netsed 属性
boost::get with boost::filtered_graph on adjacency_list with netsed properties
我为boost::adjacency_list
写了一个小包装:
template <typename T>
using VertexWithIndexProperty =
boost::property<boost::vertex_index_t, int, T>;
template <typename VertexProperty, typename EdgeProperty =
boost::no_property>
class MutableGraph : public boost::adjacency_list< boost::setS,
boost::listS, boost::undirectedS,
VertexWithIndexProperty<VertexProperty>, EdgeProperty> {
public:
using BoostBase =
boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS,
VertexWithIndexProperty<VertexProperty>,
EdgeProperty>;
MutableGraph() {}
MutableGraph(std::size_t n) : BoostBase(n) {}
MutableGraph(const MutableGraph &rhs) : BoostBase(rhs) {}
MutableGraph &operator=(const MutableGraph &rhs) {
static_cast<BoostBase *>(this)->operator=(rhs);
return *this;
}
};
然后我按如下方式使用它:我在集合中收集了一些 vertex_descriptors 以创建 boost::filtered_graph
:
`
using Graph = MutableGraph<boost::property<vertex_color_t, int>>;
Graph g;
std::set<int> C, H; //vertex_descriptors I collect
...
auto vertex_index_map = get(vertex_index, g);
std::function<bool(vertex_descriptor)> vertexes_filter =
[&vertex_index_map, &C, &H](vertex_descriptor v) {
auto index = vertex_index_map[v];
return C.find(index) != C.end() || H.find(index) != H.end();
};
boost::filtered_graph<Graph, boost::keep_all, decltype(crown_vertexes_filter)>
auxilary(g, boost::keep_all(), crown_vertexes_filter);
一切正常,但是当我尝试为顶点获取任何 property_map 时,例如:`
auto auxilary_vertex_index_map
= get(boost::vertex_index, auxilary);
我收到以下错误:
could not convert
boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS,
boost::listS, boost::undirectedS,
boost::property<boost::vertex_index_t, int,
boost::property<boost::vertex_color_t, int> >,
boost::no_property, boost::no_property, boost::listS>, int,
int&, boost::vertex_index_t>
to
boost::adj_list_vertex_property_map<MutableGraph<
boost::property<boost::vertex_color_t, int> >,
int,
int&,
boost::vertex_index_t>
我在
中收到此错误
template <typename G, typename EP, typename VP, typename Property>
typename property_map<G, Property>::type
get(Property p, filtered_graph<G, EP, VP>& g)
{
return get(p, const_cast<G&>(g.m_g));
}
在 filtered_graph.hpp
.
我不明白为什么会这样,是因为我的包装器还是因为我决定使用嵌套属性而不是捆绑属性。
提前致谢!
嵌套属性称为 "interior properties"。他们不是你的问题。
相反,您的问题出在 VertexContainerSelector 参数 (boost::listS
) 上。它导致 vertex_descriptor
类型为
- 不是整数(现在是不透明类型)
- 不是分解因子顶点索引的两倍
您已经知道这一点,这就是为什么您添加了一个 属性 作为顶点索引图。但是,您没有预料到的是,它使 vertex_index
属性 映射 (boost::property_map<Graph, vertex_index_t>::type
) 的结果类型不同,因此 filtered_graph
中的转发包装器不会不再符合要求:
template <typename G, typename EP, typename VP, typename Property>
typename property_map<G, Property>::type
get(Property p, filtered_graph<G, EP, VP>& g)
{
return get(p, const_cast<G&>(g.m_g));
}
如果您负担得起只切换到 vecS
,我会选择它。否则,请仔细考虑您的要求和影响。值得注意的是,您 VertexContainerSelector
选择 listS
会导致 vertex_descriptor
具有引用和迭代器稳定性。 filtered_graph 中的任何 vertex_descriptor
都应该对主图有效,反之亦然¹。为什么不只保留同一张地图:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_utility.hpp> // print_graph
template <typename T> using AddIndex = boost::property<boost::vertex_index_t, int, T>;
template <
typename VertexProperty,
typename EdgeProperty = boost::no_property,
typename Base = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, AddIndex<VertexProperty>, EdgeProperty> >
struct MutableGraph : Base {
using BoostBase = Base;
MutableGraph(std::size_t n = 0) : BoostBase(n) {}
using BoostBase::operator=;
};
int main() {
using Graph = MutableGraph<boost::property<boost::vertex_color_t, int> >;
using vertex_descriptor = Graph::vertex_descriptor;
Graph g;
auto a = add_vertex({1, 0}, g);
auto b = add_vertex({2, 0}, g);
auto c = add_vertex({3, 0}, g);
auto d = add_vertex({4, 0}, g);
add_edge(a, b, g);
add_edge(a, c, g);
add_edge(b, d, g);
std::set<int> C{1,2}, H{/*3,*/4}; // vertex_descriptors I collect
auto id = get(boost::vertex_index, g);
std::function<bool(vertex_descriptor)> vertexes_filter = [id, &C, &H](vertex_descriptor v) {
auto index = id[v];
return C.count(index) || H.count(index);
};
boost::filtered_graph<Graph, boost::keep_all, decltype(vertexes_filter)> auxilary(g, boost::keep_all(), vertexes_filter);
auto aux_id = id;
print_graph(g, id, std::cout << "\n---- Original\n");
print_graph(auxilary, aux_id, std::cout << "\n---- Filtered\n");
}
打印:
---- Original
1 <--> 2 3
2 <--> 1 4
3 <--> 1
4 <--> 2
---- Filtered
1 <--> 2
2 <--> 1 4
4 <--> 2
这正是您想要的。
旁注
注意代码中的简化。你的MutableGraph
class可以写成:
template <
typename VertexProperty,
typename EdgeProperty = boost::no_property,
typename Base = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, AddIndex<VertexProperty>, EdgeProperty> >
struct MutableGraph : Base {
using BoostBase = Base;
MutableGraph(std::size_t n = 0) : BoostBase(n) {}
using BoostBase::operator=;
};
虽然在这个例子中甚至可以简单地省略这两个成员的用法(operator=
仍然会被编译器正确生成)。
¹ 过滤后的可能除外...
奖金
根据评论更新:您可以 "automate" 通过特化 boost::property_map<>
特征进行类型转发:
namespace boost {
// overriding the typedef to take the types from the BoostBase instead:
template <typename Tag, typename... Args>
struct property_map<MyGraph<Args...>, Tag> : property_map<typename MyGraph<Args...>::BoostBase, Tag> {
};
}
就是这样。现在你可以在一个不知道它正在处理什么类型的图形的函数中进行打印:
template <typename WhateverGraph>
void some_naive_user_function(WhateverGraph const& g, std::ostream& os) {
// we don't know whether WhateverGraph is filtered or not, but we don't care
print_graph(g, get(boost::vertex_index, g), os);
}
get(boost::vertex_index, g)
由于专业化才有效:
boost::filtered_graph<Graph, boost::keep_all, decltype(vertexes_filter)> auxilary(g, boost::keep_all(), vertexes_filter);
some_naive_user_function(g, std::cout << "\n---- Origina (via naive user function)\n");
some_naive_user_function(auxilary, std::cout << "\n---- Filtered (via naive user function)\n");
我为boost::adjacency_list
写了一个小包装:
template <typename T>
using VertexWithIndexProperty =
boost::property<boost::vertex_index_t, int, T>;
template <typename VertexProperty, typename EdgeProperty =
boost::no_property>
class MutableGraph : public boost::adjacency_list< boost::setS,
boost::listS, boost::undirectedS,
VertexWithIndexProperty<VertexProperty>, EdgeProperty> {
public:
using BoostBase =
boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS,
VertexWithIndexProperty<VertexProperty>,
EdgeProperty>;
MutableGraph() {}
MutableGraph(std::size_t n) : BoostBase(n) {}
MutableGraph(const MutableGraph &rhs) : BoostBase(rhs) {}
MutableGraph &operator=(const MutableGraph &rhs) {
static_cast<BoostBase *>(this)->operator=(rhs);
return *this;
}
};
然后我按如下方式使用它:我在集合中收集了一些 vertex_descriptors 以创建 boost::filtered_graph
:
`
using Graph = MutableGraph<boost::property<vertex_color_t, int>>;
Graph g;
std::set<int> C, H; //vertex_descriptors I collect
...
auto vertex_index_map = get(vertex_index, g);
std::function<bool(vertex_descriptor)> vertexes_filter =
[&vertex_index_map, &C, &H](vertex_descriptor v) {
auto index = vertex_index_map[v];
return C.find(index) != C.end() || H.find(index) != H.end();
};
boost::filtered_graph<Graph, boost::keep_all, decltype(crown_vertexes_filter)>
auxilary(g, boost::keep_all(), crown_vertexes_filter);
一切正常,但是当我尝试为顶点获取任何 property_map 时,例如:`
auto auxilary_vertex_index_map
= get(boost::vertex_index, auxilary);
我收到以下错误:
could not convert
boost::adj_list_vertex_property_map<boost::adjacency_list<boost::setS,
boost::listS, boost::undirectedS,
boost::property<boost::vertex_index_t, int,
boost::property<boost::vertex_color_t, int> >,
boost::no_property, boost::no_property, boost::listS>, int,
int&, boost::vertex_index_t>
to
boost::adj_list_vertex_property_map<MutableGraph<
boost::property<boost::vertex_color_t, int> >,
int,
int&,
boost::vertex_index_t>
我在
中收到此错误template <typename G, typename EP, typename VP, typename Property>
typename property_map<G, Property>::type
get(Property p, filtered_graph<G, EP, VP>& g)
{
return get(p, const_cast<G&>(g.m_g));
}
在 filtered_graph.hpp
.
我不明白为什么会这样,是因为我的包装器还是因为我决定使用嵌套属性而不是捆绑属性。
提前致谢!
嵌套属性称为 "interior properties"。他们不是你的问题。
相反,您的问题出在 VertexContainerSelector 参数 (boost::listS
) 上。它导致 vertex_descriptor
类型为
- 不是整数(现在是不透明类型)
- 不是分解因子顶点索引的两倍
您已经知道这一点,这就是为什么您添加了一个 属性 作为顶点索引图。但是,您没有预料到的是,它使 vertex_index
属性 映射 (boost::property_map<Graph, vertex_index_t>::type
) 的结果类型不同,因此 filtered_graph
中的转发包装器不会不再符合要求:
template <typename G, typename EP, typename VP, typename Property>
typename property_map<G, Property>::type
get(Property p, filtered_graph<G, EP, VP>& g)
{
return get(p, const_cast<G&>(g.m_g));
}
如果您负担得起只切换到 vecS
,我会选择它。否则,请仔细考虑您的要求和影响。值得注意的是,您 VertexContainerSelector
选择 listS
会导致 vertex_descriptor
具有引用和迭代器稳定性。 filtered_graph 中的任何 vertex_descriptor
都应该对主图有效,反之亦然¹。为什么不只保留同一张地图:
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_utility.hpp> // print_graph
template <typename T> using AddIndex = boost::property<boost::vertex_index_t, int, T>;
template <
typename VertexProperty,
typename EdgeProperty = boost::no_property,
typename Base = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, AddIndex<VertexProperty>, EdgeProperty> >
struct MutableGraph : Base {
using BoostBase = Base;
MutableGraph(std::size_t n = 0) : BoostBase(n) {}
using BoostBase::operator=;
};
int main() {
using Graph = MutableGraph<boost::property<boost::vertex_color_t, int> >;
using vertex_descriptor = Graph::vertex_descriptor;
Graph g;
auto a = add_vertex({1, 0}, g);
auto b = add_vertex({2, 0}, g);
auto c = add_vertex({3, 0}, g);
auto d = add_vertex({4, 0}, g);
add_edge(a, b, g);
add_edge(a, c, g);
add_edge(b, d, g);
std::set<int> C{1,2}, H{/*3,*/4}; // vertex_descriptors I collect
auto id = get(boost::vertex_index, g);
std::function<bool(vertex_descriptor)> vertexes_filter = [id, &C, &H](vertex_descriptor v) {
auto index = id[v];
return C.count(index) || H.count(index);
};
boost::filtered_graph<Graph, boost::keep_all, decltype(vertexes_filter)> auxilary(g, boost::keep_all(), vertexes_filter);
auto aux_id = id;
print_graph(g, id, std::cout << "\n---- Original\n");
print_graph(auxilary, aux_id, std::cout << "\n---- Filtered\n");
}
打印:
---- Original
1 <--> 2 3
2 <--> 1 4
3 <--> 1
4 <--> 2
---- Filtered
1 <--> 2
2 <--> 1 4
4 <--> 2
这正是您想要的。
旁注
注意代码中的简化。你的MutableGraph
class可以写成:
template <
typename VertexProperty,
typename EdgeProperty = boost::no_property,
typename Base = boost::adjacency_list<boost::setS, boost::listS, boost::undirectedS, AddIndex<VertexProperty>, EdgeProperty> >
struct MutableGraph : Base {
using BoostBase = Base;
MutableGraph(std::size_t n = 0) : BoostBase(n) {}
using BoostBase::operator=;
};
虽然在这个例子中甚至可以简单地省略这两个成员的用法(operator=
仍然会被编译器正确生成)。
¹ 过滤后的可能除外...
奖金
根据评论更新:您可以 "automate" 通过特化 boost::property_map<>
特征进行类型转发:
namespace boost {
// overriding the typedef to take the types from the BoostBase instead:
template <typename Tag, typename... Args>
struct property_map<MyGraph<Args...>, Tag> : property_map<typename MyGraph<Args...>::BoostBase, Tag> {
};
}
就是这样。现在你可以在一个不知道它正在处理什么类型的图形的函数中进行打印:
template <typename WhateverGraph>
void some_naive_user_function(WhateverGraph const& g, std::ostream& os) {
// we don't know whether WhateverGraph is filtered or not, but we don't care
print_graph(g, get(boost::vertex_index, g), os);
}
get(boost::vertex_index, g)
由于专业化才有效:
boost::filtered_graph<Graph, boost::keep_all, decltype(vertexes_filter)> auxilary(g, boost::keep_all(), vertexes_filter);
some_naive_user_function(g, std::cout << "\n---- Origina (via naive user function)\n");
some_naive_user_function(auxilary, std::cout << "\n---- Filtered (via naive user function)\n");