如何以一般方式访问 Boost Graph 捆绑属性?
How do I Generically Access the Boost Graph Bundled Properties?
我正在编写一个 C++ 模板来读取 GraphViz and GraphML.
格式的加权图表
困难在于我使用不同的图形类型和不同的 vertex/edge 包,它们看起来像
struct EdgeBundle_1 {
double weight = 1.;
};
struct EdgeBundle_2 {
double weight = 2.;
int some_int;
};
using Graph_1 = typename boost::adjacency_list<boost::listS,
boost::vecS,
boost::undirectedS,
VertexBundle,
EdgeBundle_1>;
using Graph_2 = typename boost::adjacency_list<boost::listS,
boost::vecS,
boost::undirectedS,
VertexBundle,
EdgeBundle_2>;
现在我想访问任意 Graph
的边缘包,所以我必须在以下仅适用于 Graph_1
的代码中替换 &EdgeBundle_1
template <typename Graph>
void do_sth_with_bundled_weight(Graph& g){
boost::dynamic_properties dp(boost::ignore_other_properties);
dp.property("weight", boost::get(&EdgeBundle_1::weight, g));
... // here, I read in the graph via `boost::read_graphml(if_stream, g, dp);`
}
除了如何在 this boost docs page 的最底部访问捆绑 属性 的 类型 之外,我找不到任何其他内容.
非常感谢您的帮助! :)
对于 BGL,真正的问题是“如何做任何非一般性的事情”:)
因此,您可以像 boost 一样精确地进行操作。所有算法都采用 property-maps 抽象出图元素及其属性之间的关系。
通常这与特定于算法的临时属性有关,但没有什么可以阻止您在更多地方使用它。
最棒的是,您已经拥有 属性 地图,而它正是可变部分:get(&EdgeBundle_1::weight, g)
,因此只需将其作为一个参数:
template <typename Graph, typename WeightMap>
void write_graph(std::ostream& os, Graph& g, WeightMap weight_map) {
boost::dynamic_properties dp;
dp.property("weight", weight_map);
boost::write_graphml(os, g, dp);
}
template <typename Graph, typename WeightMap>
void read_graph(Graph& g, WeightMap weight_map) {
boost::dynamic_properties dp(boost::ignore_other_properties);
dp.property("weight", weight_map);
std::ifstream ifs("input.xml", std::ios::binary);
g.clear();
boost::read_graphml(ifs, g, dp);
}
您甚至可以将其默认为库默认边权重贴图:
template <typename Graph> void read_graph(Graph& g) {
return read_graph(g, get(boost::edge_weight, g));
}
template <typename Graph> void write_graph(std::ostream& os, Graph& g) {
return write_graph(os, g, get(boost::edge_weight, g));
}
演示:读取和比较等于
往返 XML Graph_1 和 Graph_2 并检查是否相等:
<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
<key id="key0" for="edge" attr.name="weight" attr.type="double" />
<graph id="G" edgedefault="undirected" parse.nodeids="free" parse.edgeids="canonical" parse.order="nodesfirst">
<node id="n0">
</node>
<node id="n1">
</node>
<node id="n2">
</node>
<node id="n3">
</node>
<node id="n4">
</node>
<node id="n5">
</node>
<node id="n6">
</node>
<node id="n7">
</node>
<node id="n8">
</node>
<node id="n9">
</node>
<edge id="e0" source="n0" target="n7">
<data key="key0">2.2</data>
</edge>
<edge id="e1" source="n7" target="n3">
<data key="key0">3.3</data>
</edge>
<edge id="e2" source="n3" target="n2">
<data key="key0">4.4</data>
</edge>
</graph>
</graphml>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphml.hpp>
#include <iostream>
#include <fstream>
struct VertexBundle {};
struct EdgeBundle_1 {
double weight = 1.;
};
struct EdgeBundle_2 {
double weight = 2.;
int some_int;
};
using Graph_1 = typename boost::adjacency_list<
boost::listS, boost::vecS, boost::undirectedS, VertexBundle, EdgeBundle_1>;
using Graph_2 = typename boost::adjacency_list<
boost::listS, boost::vecS, boost::undirectedS, VertexBundle, EdgeBundle_2>;
template <typename Graph, typename WeightMap>
void write_graph(std::ostream& os, Graph& g, WeightMap weight_map) {
boost::dynamic_properties dp;
dp.property("weight", weight_map);
boost::write_graphml(os, g, dp);
}
template <typename Graph, typename WeightMap>
void read_graph(std::istream& is, Graph& g, WeightMap weight_map) {
boost::dynamic_properties dp(boost::ignore_other_properties);
dp.property("weight", weight_map);
g.clear();
boost::read_graphml(is, g, dp);
}
template <typename Graph> void read_graph(std::istream& is, Graph& g) {
return read_graph(is, g, get(boost::edge_weight, g));
}
template <typename Graph> void write_graph(std::ostream& os, Graph& g) {
return write_graph(os, g, get(boost::edge_weight, g));
}
extern std::string const demo_xml;
int main() {
Graph_1 g1;
Graph_2 g2;
auto w1 = get(&EdgeBundle_1::weight, g1);
auto w2 = get(&EdgeBundle_2::weight, g2);
auto roundtrip = [](auto g, auto w) {
{
std::istringstream is(demo_xml);
read_graph(is, g, w);
}
std::ostringstream os;
write_graph(os, g, w);
return os.str();
};
auto xml1 = roundtrip(Graph_1{}, w1);
auto xml2 = roundtrip(Graph_2{}, w2);
std::cout << "Equal:" << std::boolalpha << (xml1 == xml2) << "\n";
}
版画
Equal:true
奖金
要实现更多自动化,您可以 这样您就不必再手动指定它了。
更新 添加这个作为手指练习。警告:这不适合胆小的人。就代码行而言,我看起来无伤大雅,但实际上它非常密集,并使用了许多高级和微妙的库和语言功能。
在自定义命名空间(例如 MyLib
)中,我们创建了一个可以自定义的包装器类型:
template <typename Impl> struct Graph {
Impl& graph() { return _impl; };
Impl const& graph() const { return _impl; };
void clear() { _impl.clear(); }
private:
Impl _impl;
};
接下来,我们委托常见的 BGL 操作:
namespace detail {
template <typename... T> static auto& fwd_impl(Graph<T...>& g) {
return g.graph();
}
template <typename... T> static auto const& fwd_impl(Graph<T...> const& g) {
return g.graph();
}
template <typename T> static decltype(auto) fwd_impl(T&& v) {
return std::forward<T>(v);
}
}
#define DELEGATE_ONE(r, _, name) \
template <typename... Args> \
static inline decltype(auto) name(Args&&... args) { \
return (boost::name)( \
detail::fwd_impl(std::forward<decltype(args)>(args))...); \
}
#define DELEGATE(...) \
BOOST_PP_SEQ_FOR_EACH(DELEGATE_ONE, _, \
BOOST_PP_VARIADIC_TO_SEQ(__VA_ARGS__))
DELEGATE(add_vertex, add_edge, vertices, edges, num_vertices, num_edges,
out_edges, out_degree, get, source, target, vertex)
#undef DELEGATE
#undef DELEGATE_ONE
是的。好多啊。基本上,如果 ADL 关联我们的命名空间,我们委托所有命名的自由函数,并且我们将所有参数转发给未经修改的提升版本 除了 的 Graph<>
包装器被其替换_impl
.
接下来,我们添加我们正在寻找的扭曲:
// The crux: overriding the edge_weight map to access the bundle
template <typename Impl> auto get(boost::edge_weight_t, Graph<Impl>& g) {
auto bundle_map = boost::get(boost::edge_bundle, g.graph());
auto accessor = [](auto& bundle) -> decltype(auto) {
return access_edge_weight(bundle);
};
return boost::make_transform_value_property_map(accessor, bundle_map);
}
我们使用包装器重新定义原始图:
using Graph_1 = Graph<GraphImpl_1>;
using Graph_2 = Graph<GraphImpl_2>;
特质
特征不是自由函数,需要在我们的命名空间之外。为了简洁起见,我使用 c++17 语法:
template <typename Impl>
struct boost::graph_traits<MyLib::Graph<Impl>> : boost::graph_traits<Impl> {};
template <typename Impl, typename Property>
struct boost::graph_property<MyLib::Graph<Impl>, Property>
: boost::graph_property<Impl, Property> {};
template <typename Impl, typename Property>
struct boost::property_map<MyLib::Graph<Impl>, Property>
: boost::property_map<Impl, Property> {};
那里。这告诉 BGL 我们的图表是 traits/property 地图的实现类型。
但是,我们确实覆盖了 edge_weight_t
映射:
template <typename Impl>
struct boost::property_map<MyLib::Graph<Impl>, boost::edge_weight_t> {
using Wrapper = MyLib::Graph<Impl>;
using type = decltype(MyLib::get(boost::edge_weight, std::declval<Wrapper&>()));
using const_type = decltype(MyLib::get(boost::edge_weight, std::declval<Wrapper const&>()));
};
(为简洁起见,再次自由使用 c++14 功能。)
证明
所有这些魔法让我们相信现在我们不必提供 属性 地图,它会被自动检测到:
int main() {
auto roundtrip = [](auto g) {
std::istringstream is(demo_xml);
read_graph(is, g);
std::ostringstream os;
write_graph(os, g);
return os.str();
};
std::cerr << "Equal:" << std::boolalpha
<< (roundtrip(MyLib::Graph_1{}) == roundtrip(MyLib::Graph_2{}))
<< "\n";
}
仍然打印
Equal:true
我正在编写一个 C++ 模板来读取 GraphViz and GraphML.
格式的加权图表困难在于我使用不同的图形类型和不同的 vertex/edge 包,它们看起来像
struct EdgeBundle_1 {
double weight = 1.;
};
struct EdgeBundle_2 {
double weight = 2.;
int some_int;
};
using Graph_1 = typename boost::adjacency_list<boost::listS,
boost::vecS,
boost::undirectedS,
VertexBundle,
EdgeBundle_1>;
using Graph_2 = typename boost::adjacency_list<boost::listS,
boost::vecS,
boost::undirectedS,
VertexBundle,
EdgeBundle_2>;
现在我想访问任意 Graph
的边缘包,所以我必须在以下仅适用于 Graph_1
&EdgeBundle_1
template <typename Graph>
void do_sth_with_bundled_weight(Graph& g){
boost::dynamic_properties dp(boost::ignore_other_properties);
dp.property("weight", boost::get(&EdgeBundle_1::weight, g));
... // here, I read in the graph via `boost::read_graphml(if_stream, g, dp);`
}
除了如何在 this boost docs page 的最底部访问捆绑 属性 的 类型 之外,我找不到任何其他内容.
非常感谢您的帮助! :)
对于 BGL,真正的问题是“如何做任何非一般性的事情”:)
因此,您可以像 boost 一样精确地进行操作。所有算法都采用 property-maps 抽象出图元素及其属性之间的关系。
通常这与特定于算法的临时属性有关,但没有什么可以阻止您在更多地方使用它。
最棒的是,您已经拥有 属性 地图,而它正是可变部分:get(&EdgeBundle_1::weight, g)
,因此只需将其作为一个参数:
template <typename Graph, typename WeightMap>
void write_graph(std::ostream& os, Graph& g, WeightMap weight_map) {
boost::dynamic_properties dp;
dp.property("weight", weight_map);
boost::write_graphml(os, g, dp);
}
template <typename Graph, typename WeightMap>
void read_graph(Graph& g, WeightMap weight_map) {
boost::dynamic_properties dp(boost::ignore_other_properties);
dp.property("weight", weight_map);
std::ifstream ifs("input.xml", std::ios::binary);
g.clear();
boost::read_graphml(ifs, g, dp);
}
您甚至可以将其默认为库默认边权重贴图:
template <typename Graph> void read_graph(Graph& g) {
return read_graph(g, get(boost::edge_weight, g));
}
template <typename Graph> void write_graph(std::ostream& os, Graph& g) {
return write_graph(os, g, get(boost::edge_weight, g));
}
演示:读取和比较等于
往返 XML Graph_1 和 Graph_2 并检查是否相等:
<?xml version="1.0" encoding="UTF-8"?>
<graphml xmlns="http://graphml.graphdrawing.org/xmlns" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://graphml.graphdrawing.org/xmlns http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd">
<key id="key0" for="edge" attr.name="weight" attr.type="double" />
<graph id="G" edgedefault="undirected" parse.nodeids="free" parse.edgeids="canonical" parse.order="nodesfirst">
<node id="n0">
</node>
<node id="n1">
</node>
<node id="n2">
</node>
<node id="n3">
</node>
<node id="n4">
</node>
<node id="n5">
</node>
<node id="n6">
</node>
<node id="n7">
</node>
<node id="n8">
</node>
<node id="n9">
</node>
<edge id="e0" source="n0" target="n7">
<data key="key0">2.2</data>
</edge>
<edge id="e1" source="n7" target="n3">
<data key="key0">3.3</data>
</edge>
<edge id="e2" source="n3" target="n2">
<data key="key0">4.4</data>
</edge>
</graph>
</graphml>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphml.hpp>
#include <iostream>
#include <fstream>
struct VertexBundle {};
struct EdgeBundle_1 {
double weight = 1.;
};
struct EdgeBundle_2 {
double weight = 2.;
int some_int;
};
using Graph_1 = typename boost::adjacency_list<
boost::listS, boost::vecS, boost::undirectedS, VertexBundle, EdgeBundle_1>;
using Graph_2 = typename boost::adjacency_list<
boost::listS, boost::vecS, boost::undirectedS, VertexBundle, EdgeBundle_2>;
template <typename Graph, typename WeightMap>
void write_graph(std::ostream& os, Graph& g, WeightMap weight_map) {
boost::dynamic_properties dp;
dp.property("weight", weight_map);
boost::write_graphml(os, g, dp);
}
template <typename Graph, typename WeightMap>
void read_graph(std::istream& is, Graph& g, WeightMap weight_map) {
boost::dynamic_properties dp(boost::ignore_other_properties);
dp.property("weight", weight_map);
g.clear();
boost::read_graphml(is, g, dp);
}
template <typename Graph> void read_graph(std::istream& is, Graph& g) {
return read_graph(is, g, get(boost::edge_weight, g));
}
template <typename Graph> void write_graph(std::ostream& os, Graph& g) {
return write_graph(os, g, get(boost::edge_weight, g));
}
extern std::string const demo_xml;
int main() {
Graph_1 g1;
Graph_2 g2;
auto w1 = get(&EdgeBundle_1::weight, g1);
auto w2 = get(&EdgeBundle_2::weight, g2);
auto roundtrip = [](auto g, auto w) {
{
std::istringstream is(demo_xml);
read_graph(is, g, w);
}
std::ostringstream os;
write_graph(os, g, w);
return os.str();
};
auto xml1 = roundtrip(Graph_1{}, w1);
auto xml2 = roundtrip(Graph_2{}, w2);
std::cout << "Equal:" << std::boolalpha << (xml1 == xml2) << "\n";
}
版画
Equal:true
奖金
要实现更多自动化,您可以
更新 添加这个作为手指练习。警告:这不适合胆小的人。就代码行而言,我看起来无伤大雅,但实际上它非常密集,并使用了许多高级和微妙的库和语言功能。
在自定义命名空间(例如 MyLib
)中,我们创建了一个可以自定义的包装器类型:
template <typename Impl> struct Graph {
Impl& graph() { return _impl; };
Impl const& graph() const { return _impl; };
void clear() { _impl.clear(); }
private:
Impl _impl;
};
接下来,我们委托常见的 BGL 操作:
namespace detail {
template <typename... T> static auto& fwd_impl(Graph<T...>& g) {
return g.graph();
}
template <typename... T> static auto const& fwd_impl(Graph<T...> const& g) {
return g.graph();
}
template <typename T> static decltype(auto) fwd_impl(T&& v) {
return std::forward<T>(v);
}
}
#define DELEGATE_ONE(r, _, name) \
template <typename... Args> \
static inline decltype(auto) name(Args&&... args) { \
return (boost::name)( \
detail::fwd_impl(std::forward<decltype(args)>(args))...); \
}
#define DELEGATE(...) \
BOOST_PP_SEQ_FOR_EACH(DELEGATE_ONE, _, \
BOOST_PP_VARIADIC_TO_SEQ(__VA_ARGS__))
DELEGATE(add_vertex, add_edge, vertices, edges, num_vertices, num_edges,
out_edges, out_degree, get, source, target, vertex)
#undef DELEGATE
#undef DELEGATE_ONE
是的。好多啊。基本上,如果 ADL 关联我们的命名空间,我们委托所有命名的自由函数,并且我们将所有参数转发给未经修改的提升版本 除了 的 Graph<>
包装器被其替换_impl
.
接下来,我们添加我们正在寻找的扭曲:
// The crux: overriding the edge_weight map to access the bundle
template <typename Impl> auto get(boost::edge_weight_t, Graph<Impl>& g) {
auto bundle_map = boost::get(boost::edge_bundle, g.graph());
auto accessor = [](auto& bundle) -> decltype(auto) {
return access_edge_weight(bundle);
};
return boost::make_transform_value_property_map(accessor, bundle_map);
}
我们使用包装器重新定义原始图:
using Graph_1 = Graph<GraphImpl_1>;
using Graph_2 = Graph<GraphImpl_2>;
特质
特征不是自由函数,需要在我们的命名空间之外。为了简洁起见,我使用 c++17 语法:
template <typename Impl>
struct boost::graph_traits<MyLib::Graph<Impl>> : boost::graph_traits<Impl> {};
template <typename Impl, typename Property>
struct boost::graph_property<MyLib::Graph<Impl>, Property>
: boost::graph_property<Impl, Property> {};
template <typename Impl, typename Property>
struct boost::property_map<MyLib::Graph<Impl>, Property>
: boost::property_map<Impl, Property> {};
那里。这告诉 BGL 我们的图表是 traits/property 地图的实现类型。
但是,我们确实覆盖了 edge_weight_t
映射:
template <typename Impl>
struct boost::property_map<MyLib::Graph<Impl>, boost::edge_weight_t> {
using Wrapper = MyLib::Graph<Impl>;
using type = decltype(MyLib::get(boost::edge_weight, std::declval<Wrapper&>()));
using const_type = decltype(MyLib::get(boost::edge_weight, std::declval<Wrapper const&>()));
};
(为简洁起见,再次自由使用 c++14 功能。)
证明
所有这些魔法让我们相信现在我们不必提供 属性 地图,它会被自动检测到:
int main() {
auto roundtrip = [](auto g) {
std::istringstream is(demo_xml);
read_graph(is, g);
std::ostringstream os;
write_graph(os, g);
return os.str();
};
std::cerr << "Equal:" << std::boolalpha
<< (roundtrip(MyLib::Graph_1{}) == roundtrip(MyLib::Graph_2{}))
<< "\n";
}
仍然打印
Equal:true