c++11 - Make a boost filtered_graph by vertex label property -
currently, have graph, keep tracking of vertices , labels means of external map. anytime need access label property, find label in map , mapped vertex.
/// vertex properties struct vertexdata { std::string label; int num; }; /// edges properties struct edgedata { std::string edge_name; double edge_confidence; }; /// define boost-graph typedef boost::adjacency_list<boost::vecs, boost::vecs, boost::bidirectionals, boost::property<boost::edge_index_t , size_t , vertexdata>, boost::property<boost::edge_weight_t, double, edgedata> > graph; /// define vertexmap std::map<std::string, vertex_t> vertexmap; ///loop through vertices make vertexmap here ... vertexmap.insert(std::pair<std::string, vertex_t> (label, v)); /// find label in map , access corresponding vertex vertex_t vertex = vertexmap.find(label)->second; now question is: if want make filtered_graph current graph filtering labels, how should in class template? examples in boost graph library different, , checked post boost graph copy , removing vertex it's quite different want do.
thanks help.
filtering
you need filtering predicate. can have multiple different graph elements. let's focus on vertices.
what want stateful predicate. way keeping state outside predicate , putting pointer inside predicate:
#include <boost/graph/adjacency_list.hpp> #include <boost/graph/filtered_graph.hpp> #include <boost/graph/graphviz.hpp> #include <iostream> namespace bi = boost::intrusive; /// vertex properties struct vertexdata { std::string label; int num; }; /// edges properties struct edgedata { std::string edge_name; double edge_confidence; }; /// define boost-graph typedef boost::adjacency_list<boost::vecs, boost::vecs, boost::bidirectionals, vertexdata, boost::property<boost::edge_weight_t, double, edgedata> > graph; int main() { using vertex_t = graph::vertex_descriptor; graph g; (auto label : { "alerts", "amazed", "buster", "deaths", "ekes", "enoch", "gale", "hug", "input", "knifed", "lire", "man", "pithy", "purims", "rodger", "suckle", "terr", "theme", "tiling", "vases", }) { boost::add_vertex(vertexdata{label, 1+rand()%5}, g); } boost::write_graphviz(std::cout, g, boost::make_label_writer(boost::get(&vertexdata::label, g))); { using labels = std::set<std::string>; labels suppressed { "alerts", "amazed", "deaths", "ekes", "gale", "hug", "input", "knifed", "man", "pithy", "purims", "suckle", "terr", "theme", "vases", }; struct predicate { // both edge , vertex bool operator()(graph::edge_descriptor) const { return true; } // bool operator()(graph::vertex_descriptor vd) const { return suppressed_->count((*g)[vd].label) == 0; } graph* g; labels* suppressed_; } predicate {&g, &suppressed}; using filtered = boost::filtered_graph<graph, predicate, predicate>; filtered fg(g, predicate, predicate); boost::write_graphviz(std::cout, fg, boost::make_label_writer(boost::get(&vertexdata::label, fg))); } } prints unfiltered graph (g) first, , filtered graph (fg):
digraph g { 2[label=buster]; 5[label=enoch]; 10[label=lire]; 14[label=rodger]; 18[label=tiling]; } indexing
not question, can make maintaining index more friendly using intrusive containers. if add hook vertexdata:
struct vertexdata : bi::set_base_hook<> { std::string label; int num; struct by_label; }; you can use intrusive-set:
using by_label_idx_t = bi::set<vertexdata, bi::key_of_value<vertexdata::by_label> >; this means can add vertices:
by_label_idx_t label_idx; (auto vd : boost::make_iterator_range(boost::vertices(g))) label_idx.insert(g[vd]); what buy you? not lot per se. enabling auto-unlinking, buy when vertex removed, it's automatically removed index.
#include <boost/graph/adjacency_list.hpp> #include <boost/graph/filtered_graph.hpp> #include <boost/intrusive/set_hook.hpp> #include <boost/intrusive/set.hpp> #include <iostream> namespace bi = boost::intrusive; /// vertex properties struct vertexdata : bi::set_base_hook<bi::link_mode<bi::auto_unlink>, bi::constant_time_size<false> > { std::string label; int num; vertexdata(std::string label, int num) : label(label), num(num) {} struct by_label { using type = std::string; std::string const& operator()(vertexdata const& vd) const { return vd.label; } }; }; using by_label_idx_t = bi::set<vertexdata, bi::constant_time_size<false>, bi::key_of_value<vertexdata::by_label> >; /// edges properties struct edgedata { std::string edge_name; double edge_confidence; }; /// define boost-graph typedef boost::adjacency_list<boost::vecs, boost::vecs, boost::bidirectionals, vertexdata, boost::property<boost::edge_weight_t, double, edgedata> > graph; int main() { using vertex_t = graph::vertex_descriptor; graph g; (auto label : { "alerts", "amazed", "buster", "deaths", "ekes", "enoch", "gale", "hug", "input", "knifed", "lire", "man", "pithy", "purims", "rodger", "suckle", "terr", "theme", "tiling", "vases", }) { boost::add_vertex(vertexdata{label, 1+rand()%5}, g); } /// define vertexmap by_label_idx_t label_idx; auto reindex = [&] { label_idx.clear(); (auto vd : boost::make_iterator_range(boost::vertices(g))) label_idx.insert(g[vd]); }; reindex(); std::cout << "index: " << label_idx.size() << " elements\n"; g.clear(); std::cout << "index: " << label_idx.size() << " elements\n"; (auto& vertex : label_idx) { std::cout << vertex.label << " " << vertex.num << "\n"; } } wiki
Comments
Post a Comment