c++11 - 通过顶点标签属性制作 boost filtered_graph

Question

目前，我有一个图表，我通过外部 map 跟踪顶点和标签。因此，只要我需要访问标签属性，我就会在 map 中找到标签并获取 mapped vertex。

/// vertex properties
struct VertexData
{
    std::string label;
    int num;
};

/// edges properties
struct EdgeData
{
    std::string edge_name;
    double edge_confidence;
};

/// define the 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 the vertices to make the vertexMap here ...
vertexMap.insert(std::pair<std::string, vertex_t> (label, v));

/// find any label in the map and access the corresponding vertex
vertex_t vertex = vertexMap.find(label)->second;

现在我的问题是:如果我想通过过滤一些标签从当前图制作一个filtered_graph，我应该如何在类模板中做到这一点？ boost图库里的例子不一样，我也查了这个帖子boost graph copy and removing vertex但这与我想做的完全不同。

感谢您的帮助。

Answer 1

过滤

您需要一个过滤谓词。您可以为不同的图形元素设置多个。但让我们关注顶点。

您想要的是有状态谓词。这样做的方法通常是将状态保持在谓词之外，并将指向该状态的指针放在谓词内部:

Live On Coliru

#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 the 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;
    for (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 and vertex
            bool operator()(Graph::edge_descriptor) const      { return true; } // all
            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)));
    }

}

首先打印未过滤的图 (g)，然后打印过滤后的图 (fg):

digraph G {
2[label=buster];
5[label=Enoch];
10[label=lire];
14[label=Rodger];
18[label=tiling];
}

索引

这不是真正的问题，但您可以使用侵入式容器使维护索引稍微更友好一些。如果您向 VertexData 添加一个钩子(Hook):

struct VertexData : bi::set_base_hook<> {
    std::string label;
    int num;

    struct by_label;
};

您可以使用侵入式集:

using by_label_idx_t = bi::set<VertexData, bi::key_of_value<VertexData::by_label> >;

这意味着您可以添加所有顶点:

by_label_idx_t label_idx;
for (auto vd : boost::make_iterator_range(boost::vertices(g)))
    label_idx.insert(g[vd]);

这给你带来了什么？本身并不多。但是启用自动取消链接，它确实让你知道当一个顶点被删除时，它会自动从索引中删除。

Live On Coliru

#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 the 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;
    for (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();
        for (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";

    for (auto& vertex : label_idx) {
        std::cout << vertex.label << " " << vertex.num << "\n";
    }
}