読者です 読者をやめる 読者になる 読者になる

Boost.Graph filtered_graph

C++

Boost.Graphには、filtered_graphというグラフ構造をフィルタリングするためのグラフ構造が用意されています。
以下は、adjacency_listで作成したグラフのうち、辺の重みが正のもののみを抽出するfiltered_graphの例です。

#include <iostream>
#include <vector>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/assign/list_of.hpp>
#include <boost/foreach.hpp>

typedef boost::adjacency_list<boost::listS, boost::vecS, boost::undirectedS,
    boost::no_property, boost::property<boost::edge_weight_t, int> > Graph;
typedef std::pair<int, int>                             Edge;
typedef boost::graph_traits<Graph>::vertex_descriptor   Vertex;

struct Station {
    enum enum_t {
        Omiya,
        Yokohama,
        Oshima,
        Tokyo,
        NishiKokubunji,
        N
    };
};

const std::string StationNames[] = {
    "大宮",
    "横浜",
    "大島",
    "東京",
    "西国分寺"
};

const int vertex_count = Station::N;

template <class EdgeWeightMap>
class positive_filter {
    EdgeWeightMap weight_map_;
public:
    positive_filter() {}
    positive_filter(const EdgeWeightMap& weight_map)
        : weight_map_(weight_map) {}

    template <class Edge>
    bool operator()(const Edge& e) const
    {
        return boost::get(weight_map_, e) >= 0;
    }
};

int main()
{
    const std::vector<Edge> edges = boost::assign::list_of<Edge>
        (Station::Omiya, Station::Tokyo)
        (Station::Tokyo, Station::Yokohama)
        (Station::NishiKokubunji, Station::Yokohama)
        (Station::NishiKokubunji, Station::Omiya)
    ;

    const std::vector<int> weights = boost::assign::list_of
        (3)
        (1)
        (-1)
        (2)
    ;

    Graph g(edges.begin(), edges.end(), weights.begin(), vertex_count);

    typedef boost::property_map<Graph, boost::edge_weight_t>::type EdgeWeightMap;

    positive_filter<EdgeWeightMap> filter(boost::get(boost::edge_weight, g));
    boost::filtered_graph<Graph, positive_filter<EdgeWeightMap>> fg(g, filter);

    boost::print_edges(fg, StationNames);
    boost::print_edges(g, StationNames);
}
(大宮,東京) (東京,横浜) (西国分寺,大宮)
(大宮,東京) (東京,横浜) (西国分寺,横浜) (西国分寺,大宮) 

filtered_graphは、抽出元のグラフ構造の型と、抽出用の述語の型を指定し、それぞれコンストラクタで渡します。
filtered_graphは抽出元のグラフを破壊的に変更することはせず、イテレート時に述語を満たさない辺を読み飛ばす、というもので、filtered_graph自身もadjacency_listのようにグラフ構造のインタフェースで扱うことができます。


正のweightを持つ辺のみを抽出したグラフfgを出力すると、-1の辺が含まれていないことがわかります。
また、抽出されたグラフを出力した後、抽出元のグラフを出力していますが、そちらには負のweightを持つ辺も出力され、抽出元のグラフが変更されていないことがわかります。