BGLでプロパティを設定する

boostjp.github.io

を参考にさせていただいた．とても分かりやすかった．

任意のプロパティの設定

BGLのグラフ構造（adjacency_listやadjacency_matrix）は，ノードやエッジのプロパティを自分で設定することができる．プロパティはstruct構造体で設定する．

//ノードのプロパティ
struct City {
    std::string name;
    int population;
    std::vector<int> zipcodes;
};

//エッジのプロパティ
struct Highway {
    std::string name;
    double distance; // km
};

//グラフのプロパティ
struct Country {
    std::string name;
};

上記はノードとエッジをそれぞれ街と道路にみたてた例である．
プロパティによって，任意のグラフを設定することができる．

使用例

上記のページのサンプルをそのまま転載させていただいた．

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

このグラフを可視化すると次のようになる (ノードのname以外のプロパティは省略した）．

このようにプロパティを自分で設定することで，任意のグラフを扱うことができる．
この例では，街とその間の道路を表すグラフを表現することができた．

おまけ

グラフの可視化はGraphvizを用いた．

tomov3.hatenablog.com

出力部分のコードは以下のようになる．

template <class WeightMap,class CapacityMap>
class edge_writer {
public:
  edge_writer(WeightMap w, CapacityMap c) : wm(w),cm(c) {}
  template <class Edge>
  void operator()(std::ostream &out, const Edge& e) const {
    out << "[label=\"" << wm[e] << "\", taillabel=\"" << cm[e] << "\"]";
  }
private:
  WeightMap wm;
  CapacityMap cm;
};

template <class WeightMap, class CapacityMap>
inline edge_writer<WeightMap,CapacityMap> 
make_edge_writer(WeightMap w,CapacityMap c) {
  return edge_writer<WeightMap,CapacityMap>(w,c);
}

std::ofstream file("test.dot");
boost::write_graphviz( file, map, boost::make_label_writer( boost::get(&City::name, map) ),
    make_edge_writer( boost::get(&Highway::distance, map), boost::get(&Highway::name, map) ) );

このコードは

c++ - How to print a graph in graphviz with multiple properties displayed - Stack Overflow

の記事を参考にした（make_edge_writer()の部分）．