通过顶点标签属性创建一个boostfiltered_graph

目前，我有一个图表，我一直在跟踪它vertices and labels通过一个external 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通过过滤一些标签从当前图表中，我应该如何在class template？ boost图形库中的示例是不同的，我还检查了这篇文章增强图复制并删除顶点但这与我想做的完全不同。

谢谢你的帮助。

过滤

您需要一个过滤谓词。你can对于不同的图形元素有多个。但让我们关注顶点。

你想要的是一个有状态的谓词。执行此操作的方法通常是将状态保留在谓词外部，并将指向该状态的指针放在谓词内部：

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];
}

Indexing

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

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";
    }
}