Make a boost filtered_graph by vertex label proper

Question

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;

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.

Thanks for any help.

Answer 1

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:

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

}

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

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.

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