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

グラフの型と基本的な操作 - p_tanのお勉強日記の隣接リストに続いて隣接行列。
参考サイト↓
Boost Graph Library: Adjacency Matrix（日本語）
Boost Graph Library: Adjacency Matrix - 1.43.0（英語）

adjacent_matrix

サンプルコード。

#include <iostream>
#include <boost/graph/adjacency_matrix.hpp>
#include <boost/graph/graph_utility.hpp>    // for print_edges, print_vertices, print_graph

int main(int argc, char* argv[])
{
    enum { A, B, C, D, E, F, N};   // 頂点インデックス用
    const char* name = "ABCDEFG";    // 頂点名
    // 隣接行列による無向グラフの型宣言
    typedef boost::adjacency_matrix<boost::undirectedS> UGraph;
    UGraph ug(N);   // N頂点のグラフ生成
    // 辺追加
    boost::add_edge(B, C, ug);
    boost::add_edge(B, F, ug);
    boost::add_edge(C, A, ug);
    boost::add_edge(D, E, ug);
    boost::add_edge(F, A, ug);

    // 頂点出力
    std::cout << "頂点数 : " << boost::num_vertices(ug) << std::endl;
    std::cout << "頂点リスト: ";
    boost::print_vertices(ug, name);
    std::cout << std::endl;
    // 辺出力
    std::cout << "辺数: " << boost::num_edges(ug) << std::endl;
    std::cout << "辺リスト: ";
    boost::print_edges(ug, name);
    std::cout << std::endl;
    // グラフ出力
    std::cout << "隣接頂点リスト: " << std::endl;
    boost::print_graph(ug, name);
    std::cout << std::endl;
    // 辺削除
    std::cout << "辺(B, C)を削除" << std::endl;
    boost::remove_edge(B, C, ug);
    std::cout << "辺数: " << boost::num_edges(ug) << std::endl;
    std::cout << "辺リスト: ";
    boost::print_edges(ug, name);
    std::cout << std::endl;
    // 頂点に接続する辺の全削除
    std::cout << "頂点Aに接続する辺の削除(頂点A自体は残る)" << std::endl;
    boost::clear_vertex(A, ug);
    std::cout << "辺数: " << boost::num_edges(ug) << std::endl;
    std::cout << "辺リスト: ";
    boost::print_edges(ug, name);
    std::cout << "頂点数 : " << boost::num_vertices(ug) << std::endl;
    std::cout << "頂点リスト: ";
    boost::print_vertices(ug, name);
    std::cout << std::endl;

    return 0;
}

出力↓

頂点数 : 6
頂点リスト: A B C D E F

辺数: 5
辺リスト: (C,A) (C,B) (E,D) (F,A) (F,B)

隣接頂点リスト:
A <--> C F
B <--> C F
C <--> A B
D <--> E
E <--> D
F <--> A B

辺(B, C)を削除
辺数: 4
辺リスト: (C,A) (E,D) (F,A) (F,B)

頂点Aに接続する辺の削除(頂点A自体は残る)
辺数: 2
辺リスト: (E,D) (F,B)
頂点数 : 6
頂点リスト: A B C D E F

adjacency_listと同じく有向/無向の指定をテンプレート引数で行う。
adjacency_listと違って辺・頂点のコンテナの指定はできない。
また、オブジェクトを生成した後の頂点の追加/削除も出来ない。
（boost 1.43.0現在。ソースを見ると UNDER CONSTRUCTION って書いてるのでそのうち出来るようになるかも。）
その他の操作は大体adjacency_listと同じ。
隣接行列については以上。

utility関数各種

　boost/graph/graph_utility.hpp にprint***関数がそろっているのでコンソールへの出力に便利。
上のサンプルでは頂点の名前を指定して出力してる。

今後の予定

今後やりたい内容は以下の通り。

• グラフ・インタフェイスについて
• 辺や頂点への重みなどのつけ方：プロパティマップ
• 各種グラフアルゴリズムの使用法

本日はここまで。