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

Boost.Graph Bundleプロパティ

C++

Boost.Graphのグラフ構造には、Property Mapによって頂点・辺・グラフに任意のプロパティを持たせることができます。
ただ、プロパティが増えてくると管理しきれなくなってくるので、ひとまとめにしたくなります。
そこで、Boost.GraphにはBundleプロパティという機能が用意されています。これは、グラフ構造のプロパティ指定のところにユーザー定義クラスを指定するという機能です。


以下のサンプルでは、

  • 頂点のBundleプロパティとして「名前」「人口」「郵便番号一覧」を持つCity(街)クラス。
  • 辺のBundleプロパティとして「名前」と「距離」を持つHighway(高速道路)クラス。
  • グラフのBundleプロパティとして「名前」を持つCountry(国)クラス

を設定しています。
そして、最短経路の計算の際に、Highwayクラスのdistanceメンバ変数を辺の重みとして使用しています。

#include <iostream>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>

struct City {
    std::string name;
    int population;
    std::vector<int> zipcodes;
};

struct Highway {
    std::string name;
    double distance; // km
};

struct Country {
    std::string name;
};

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    City,    // 頂点のBundleプロパティ
    Highway, // 辺のBundleプロパティ
    Country  // グラフのBundleプロパティ
> Map;

int main()
{
    Map map;

    // グラフのBundleプロパティを設定
    map[boost::graph_bundle].name = "Japan";

    // 街(頂点)を2つ追加
    Map::vertex_descriptor v1 = add_vertex(map);
    Map::vertex_descriptor v2 = add_vertex(map);

    // 頂点のBundleプロパティを設定
    map[v1].name = "Tokyo";
    map[v1].population = 13221169;
    map[v1].zipcodes.push_back(1500013);

    map[v2].name = "Nagoya";
    map[v2].population = 2267048;
    map[v2].zipcodes.push_back(4600006);

    // 辺を追加
    bool inserted = false;
    Map::edge_descriptor e;
    boost::tie(e, inserted) = add_edge(v1, v2, map);

    // 辺のBundleプロパティを設定
    map[e].name = "Tomei Expessway";
    map[e].distance = 325.5;

    // Highwayクラスのdistanceメンバを辺の重みとして計算
    std::vector<double> distance(boost::num_vertices(map));
    boost::dijkstra_shortest_paths(map, v1,
            boost::weight_map(boost::get(&Highway::distance, map)).
            distance_map(&distance[0]));

    std::cout << "Tokyo-Nagoya : " << distance[v2] << "km" << std::endl;
}
Tokyo-Nagoya : 325.5km


Bundleプロパティを使用したグラフ型の定義は以下:

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    City,    // 頂点のBundleプロパティ
    Highway, // 辺のBundleプロパティ
    Country  // グラフのBundleプロパティ
> Map;

通常のプロパティを使用したグラフ型の定義は以下:

typedef boost::adjacency_list<
    boost::listS, boost::vecS, boost::bidirectionalS,
    // 頂点プロパティ
    boost::property<boost::vertex_name_t, std::string,
    boost::property<population_t, int,
    boost::property<zipcodes_t, std::vector<int> > > >,
    // 辺プロパティ
    boost::property<boost::edge_name_t, std::string,
    boost::property<boost::edge_weight_t, double> >,
    // グラフプロパティ
    boost::property<boost::graph_name_t, std::string>
> Map;


参照:
Bundled Properties - Boost Graph Library