通过顶点标签属性制作增强的filtered_graph [英] Make a boost filtered_graph by vertex label property

问题描述

目前，我有一个图形，可以通过external map跟踪vertices和labels.因此，只要我需要访问label属性，就可以在地图上找到标签并获取mapped vertex.

Currently, I have a graph, that I keep tracking of vertices and labels by means of an external map. So anytime I need to access the label property, I find the label in the map and get the 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中执行此操作?提升图库中的示例有所不同，我也检查了这篇文章增强图形复制并删除顶点，但这与我想做的完全不同.

Now my question is: If I want to make a filtered_graph from current graph by filtering some labels, how should I do that in the class template? The examples in the boost graph library are different, and I checked also this post boost graph copy and removing vertex but it's quite different from what I want to do.

感谢您的帮助.

推荐答案

过滤

您需要一个过滤谓词.您可以针对不同的图形元素具有多个.但是，让我们关注顶点.

Filtering

You need a filtering predicate. You can have multiple for different graph elements. But let's focus on vertices.

您想要的是一个有状态谓词.实现此目的的方法通常是将状态保持在谓词之外，并在谓词内部放置一个指向该状态的指针:

What you want is a stateful predicate. The way to do this is usually keeping the state outside the predicate and putting a pointer to that inside the predicate:

在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):

Prints the unfiltered graph (g) first, and then the filtered graph (fg):

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

索引

并不是真正的问题，但是您可以使用介入式容器使索引的维护更加友好.如果将钩子添加到VertexData:

Indexing

Not really the question, but you can make maintaining an index slightly more friendly using intrusive containers. If you add a hook to the VertexData:

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

    struct by_label;
};

您可以使用侵入式设置:

You can use an intrusive-set:

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

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

This means you can add all vertices:

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

这能给您带来什么?本身不是很多.但是启用自动取消链接功能后，您确实可以买到，当删除顶点时，它会自动从索引中删除.

What does this buy you? Not a lot per se. But enabling auto-unlinking, it does buy you that when a vertex is removed, it's automatically removed from the index.

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

这篇关于通过顶点标签属性制作增强的filtered_graph的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！