Boost Graph

Boost Graph C++

Boost のグラフ構造を扱うライブラリ．

てことで少しさわり中．確かに，頂点リスト，接続辺リスト，走査処理とか自前で実装するのもなんかな，とは思っていたのでちょいちょい使い方を見てる．


キモは， graph_traits と adjacency_list によって適度に抽象化されてる（きがする
あと property_map でいろいろ属性足せるのもすごいね．頂点の重みづけとか色とか，辺の距離とかもこれつかえばいけるっぽ．


まあまださわりしかみてないけど．

// directed_graph.cpp
//
// 有向グラフのサンプル
// boost の graph つかってみる

#include <iostream>                      // for std::cout
#include <utility>                       // for std::pair
#include <boost/utility.hpp>             // for boost::tie
#include <boost/graph/graph_traits.hpp>  // for boost::graph_traits
#include <boost/graph/adjacency_list.hpp>


using namespace std;
using namespace boost;

int main(int argc, char* argv[])
{
    typedef adjacency_list<vecS, vecS, bidirectionalS> Graph; // 隣接リストを使って有向グラフを定義
    // typedef adjacency_list<vecS, vecS, undirectedS> Graph; // 無向グラフは undirectedS
    typedef pair<int, int> Edge;

    enum {A, B, C, D, E, N};
    const char* name = "ABCDE";

    Edge edge_array[] = { Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C), Edge(C,E), Edge(B,D), Edge(D,E), };
    const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);
    const int num_vertices = N;

    // グラフオブジェクトを宣言
    // コンストラクタでエッジを与えてしまう
    // 引数は，エッジリストの開始ポインタと終点ポインタ，エッジ数
    Graph g(edge_array, edge_array + num_edges, num_vertices);

    // エッジイテレータのコンストラクタを使わずに，
    // オブジェクトを作成してから add_edge で辺を追加 する場合
    /*
    Graph g(num_vertices);
    for (int i = 0; i < num_edges; ++i)
      add_edge(edge_array[i].first, edge_array[i].second, g);
      */

    // 頂点インデックスのためのプロパティマップ
    typedef property_map<Graph, vertex_index_t>::type IndexMap;
    IndexMap index = get(vertex_index, g);

    typedef graph_traits<Graph>::vertex_iterator vertex_iter;
    pair<vertex_iter, vertex_iter> vp;

    // 頂点リストの出力
    cout << "vertices(g) = ";
    for (vp = vertices(g); vp.first != vp.second; ++vp.first)
      cout << name[index[*vp.first]] <<  " ";
    cout << endl;

    graph_traits<Graph>::edge_iterator ei, ei_end;
    // 辺リストの出力
    cout << "edges(g)    = ";
    for (tie(ei, ei_end) = edges(g); ei != ei_end; ++ei) {
        cout << "(" << name[index[source(*ei, g)]]
             << "," << name[index[target(*ei, g)]] << ")";
    }
    cout << endl;

    return 0;
}

vertices(g) = A B C D E
edges(g)    = (A,B)(A,D)(C,A)(D,C)(C,E)(B,D)(D,E)

graphviz での出力

用のapiもあったりなどする． boost/graph/graphviz.hpp

これを使うと，上のを，こんなかんじで出力できる．

// directed_graph_graphviz.cpp

#include <iostream>                      // for std::cout
#include <utility>                       // for std::pair
#include <boost/utility.hpp>             // for boost::tie
#include <boost/graph/graph_traits.hpp>  // for boost::graph_traits
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>


using namespace std;
using namespace boost;

int main(int argc, char* argv[])
{
    typedef adjacency_list<vecS, vecS, bidirectionalS> Graph; // 隣接リストを使って有向グラフを定義
    typedef pair<int, int> Edge;

    enum {A, B, C, D, E, N};
    const char* name = "ABCDE";

    Edge edge_array[] = { Edge(A,B), Edge(A,D), Edge(C,A), Edge(D,C), 
        Edge(C,E), Edge(B,D), Edge(D,E), };
    const int num_edges = sizeof(edge_array)/sizeof(edge_array[0]);
    const int num_vertices = N;

    Graph g(edge_array, edge_array + num_edges, num_vertices);

    write_graphviz(
        cout,
        g,
        make_label_writer(name)
    );

    return 0;
}

digraph G {
0[label="A"];
1[label="B"];
2[label="C"];
3[label="D"];
4[label="E"];
0->1 ;
0->3 ;
2->0 ;
3->2 ;
2->4 ;
1->3 ;
3->4 ;
}


べんりすぐる．

参考