如何一般性地访问Boost Graph的捆绑属性? [英] How do I Generically Access the Boost Graph Bundled Properties?
问题描述
我正在编写一个c ++模板，以读取格式为
#include< boost/graph/adjacency_list.hpp>#include< boost/graph/graphml.hpp>#include< iostream>#include< fstream>struct VertexBundle {};struct EdgeBundle_1 {双倍权重= 1.};struct EdgeBundle_2 {双倍权重= 2.int some_int;};使用Graph_1 =类型名boost :: adjacency_list<boost :: listS，boost :: vecS，boost :: undirectedS，VertexBundle，EdgeBundle_1> ;;使用Graph_2 = typename boost :: adjacency_list<boost :: listS，boost :: vecS，boost :: undirectedS，VertexBundle，EdgeBundle_2> ;;模板<类型名图，类型名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);}模板<类型名图，类型名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);}模板< typename Graph>void read_graph(std :: istream& is，Graph& g){返回read_graph(is，g，get(boost :: edge_weight，g));}模板< typename Graph>无效write_graph(std :: ostream& os，Graph& g){返回write_graph(os，g，get(boost :: edge_weight，g));}extern std :: string const demo_xml;int main(){Graph_1 g1;Graph_2 g2;自动w1 = get(& EdgeBundle_1 :: weight，g1);自动w2 = get(& EdgeBundle_2 :: weight，g2);自动往返= [](自动g，自动w){{std :: istringstream is(demo_xml);read_graph(is，g，w);}std :: ostringstream os;write_graph(os，g，w);返回os.str();};自动xml1 =往返(Graph_1 {}，w1);自动xml2 =往返(Graph_2 {}，w2);std :: cout<<等于:"<<std :: boolalpha<<(xml1 == xml2)<<"\ n";} 打印
等于:true 奖金
要获得更多的自动化，您可以在Coliru上直播
int main(){自动往返= [](自动g){std :: istringstream is(demo_xml);read_graph(is，g);std :: ostringstream os;write_graph(os，g);返回os.str();};std :: cerr<<等于:"<<std :: boolalpha<<(roundtrip(MyLib :: Graph_1 {})== roundtrip(MyLib :: Graph_2 {}))<<"\ n";} 静态图片
等于:true I am writing a c++ template to read in weighted graphs of the formats GraphViz and GraphML.
The difficulty is that I use different graph types with different vertex/edge bundles, they could look something like
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>;
Now I want to access the edge bundle of an arbitrary Graph, so I have to replace &EdgeBundle_1 in the following code that only works for Graph_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);`
}
I haven't been able to find anything other than how to access the type of a bundled property, at the very bottom of this boost docs page.
I'm grateful for any help! :)
With BGL the real question is "how to do anything not-generically" :)
So, you can do precisely as boost does. All the algorithms take property-maps which abstract away the relation between graph elements and their properties.
Often this will be about temporary properties specific to the algorithm, but there's nothing that prevents you from using it in more places.
The best thing is, you already have the property map, and it's precisely the variable part:get(&EdgeBundle_1::weight, g), so instead just take that as a parameter:
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);
}
You can even make it default to the library default edge weight map:
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));
}
Demo: Reading and Comparing Equal
Roundtripping the following XML both Graph_1 and Graph_2 and checking equality:
<?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";
}
Prints
Equal:true
BONUS
To have more automation, you can tell BGL about your property maps with traits so you don't have to manually specify it at anymore.
Update Added this as a finger exercise. Warning: this is not for the faint of heart. It my look innocous in terms of lines of code, but it is actually pretty dense and uses many advanced and subtle library and language features.
In a custom namespace (e.g. MyLib), we create a wrapper type that we can customize for:
template <typename Impl> struct Graph {
Impl& graph() { return _impl; };
Impl const& graph() const { return _impl; };
void clear() { _impl.clear(); }
private:
Impl _impl;
};
Next, we delegate common BGL operations:
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
Yup. That's a lot. Basically, we delegate all the named free functions if ADL associates our namespace, and we forward all the arguments to the boost version unmodified except for the Graph<> wrapper which is replaced by its _impl.
Next, we add the twist we were looking for:
// 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);
}
We re-define the original graphs using the wrapper:
using Graph_1 = Graph<GraphImpl_1>;
using Graph_2 = Graph<GraphImpl_2>;
Traits
The traits are not free functions and need to be outside our namespace. I use c++17 syntax for brevity:
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> {};
There. That tells BGL that our graph is our implementation type for traits/property maps.
However, we did override edge_weight_t map:
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&>()));
};
(Again liberally using c++14 features for brevity.)
The Proof
All this magic buys us that now we don't have to provide a property map, instead it gets detected automatically:
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";
}
Still prints
Equal:true
这篇关于如何一般性地访问Boost Graph的捆绑属性?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
