グラフの型と基本的な操作

はてダ始めてみました。
Boost Graph Libraryについて勉強したことを書いていきます。
参考サイト↓
Table of Contents: Boost Graph Library - 1.43.0（英語）
Table of Contents: Boost Graph Library（日本語）

グラフ理論に関する基本的な知識はあるものと仮定します。
まず隣接リストで表現されるグラフから。

adjacency_list

とりあえずコード。

#include <iostream>
#include <boost/utility.hpp>             // for boost::tie
#include <boost/graph/graph_traits.hpp>  // for boost::graph_traits
#include <boost/foreach.hpp>    // for BOOST_FOREACH
#include <boost/graph/adjacency_list.hpp>

using namespace boost;
using namespace std;

int main(int,char*[])
{

    // グラフ(隣接リスト)のtypedef
    typedef adjacency_list< vecS,    // 辺用コンテナの指定
                            vecS,    // 頂点用コンテナの指定
                            undirectedS  //　有向/無向グラフの指定
                          > Graph;
    // 頂点数
    const int vertices_num = 5;
    // 辺の定義
    typedef pair<int, int> Edge;
    Edge edge_array[] = { Edge(0, 1),
                          Edge(1, 2),
                          Edge(2, 3) };

    // 辺と頂点数を指定してグラフオブジェクトを作成
    Graph g(edge_array, edge_array + sizeof(edge_array)/sizeof(Edge), vertices_num);
    
    // グラフの出力
    // 頂点イテレータのtypedef 
    typedef graph_traits<Graph>::vertex_iterator vertex_iter;
    // 頂点出力
    cout << "Vertices" << endl;
    cout << "num_vertices(g): " << num_vertices(g) << endl; // 頂点の数
    cout << "vertices(g): ";
    vertex_iter vi, vi_end;
    for(tie(vi, vi_end) = vertices(g); vi != vi_end; vi++){
        cout << *vi << " ";
    }
    cout << endl;
    // 辺イテレータのtypedef
    typedef graph_traits<Graph>::edge_iterator edge_iter;
    // 辺出力
    cout << "Edges" << endl;
    cout << "num_edges(g): " << num_edges(g) << endl;   // 辺の数
    cout << "edges(g): ";
    edge_iter ei, ei_end;
    for(tie(ei, ei_end) = edges(g); ei != ei_end; ei++){
        cout << *ei << " ";
    }
    cout << endl;

    // 頂点記述子の型
    typedef graph_traits<Graph>::vertex_descriptor vertex_d;
    // 頂点の追加
    vertex_d v1 = add_vertex(g);
    cout << "add vertex\t" << v1 << endl;
    vertex_d v2 = add_vertex(g);
    cout << "add vertex\t" << v2 << endl;
    
    // 辺記述子の型
    typedef graph_traits<Graph>::edge_descriptor edge_d;
    // 辺の追加
    edge_d e;
    bool is_added;
    tie(e, is_added) = add_edge(v1, v2, g);
    if(is_added){
        cout << "add edge\t" << e << endl;
    }

    return 0;
}

で出力は以下。

Vertices
num_vertices(g): 5
vertices(g): 0 1 2 3 4
Edges
num_edges(g): 3
edges(g): (0,1) (1,2) (2,3)
add vertex      5
add vertex      6
add edge        (5,6)

以下説明。

adjacency_listは第一・第二テンプレート引数で辺・頂点を格納するコンテナを選択できる。

コンテナの指定用の選択肢型
- vecS -> std::vector を選択
- listS -> std::list を選択
- slistS -> std::slist を選択
- setS -> std::set を選択
- multisetS -> std::multiset を選択
- hash_setS -> std::hash_set を選択

コンテナの違いは頂点・辺の参照/追加/削除に関する計算量や多重辺を許容するかどうか等。

また第三テンプレート引数で有向/無向グラフを選択できる。

directedS -> 有向グラフ(頂点の出辺のみ参照可能）
bidirectionalS -> 有向グラフ(頂点の入出辺を参照可能だが、メモリが多く必要）
undirectedS -> 無向グラフ

実は第四テンプレート引数以降もあるがまた後日書く（多分）。

頂点や辺の設定はコンストラクタでも出来るし後からも追加・削除が可能。
また頂点や辺のオブジェクト型やイテレータなどのグラフに関連する型は
graph_traitsを通して見るらしい（再利用性を高めるため？）
graph_traits一覧については以下参照
Boost Graph Library: Graph Traits

とりあえず今日はここまで。

p_tan's blog

勉強日記です。ツッコミ大歓迎

グラフの型と基本的な操作

adjacency_list