Boost Graph Library:: 任意のノード間にエッジが存在するかを調べる

1. 目的

boost graph library を用いたグラフにおいて任意の２つのノード間にエッジがあるかどうか確認する。

2. 方法

グラフgにおいてノードuからvへのエッジが存在するか確認する時、
edge(u, v, g)
を用いる。これはstd::pair<edge_descriptor, bool>を返り値に持つ関数で、１つ目の要素に該当エッジのedge_descriptor、第2要素にboolを持つ。

※エッジが存在しない場合(第2要素がfalseの場合,第1要素はnullとなる。

2.1 保証

公式ドキュメントより定数時間で返ってくることが保証されている。

3.例

以下の重み付き有向グラフについて、各ノードに対してエッジを持つかどうかを判定し、存在した場合は重みを出力する。

（すべての重みは出次数により正規化されているものとする。）

3.1 コード

参考リンクの記事に基づき生成したノード、エッジにプロパティを持つグラフ。
詳細については割愛。

    vertex_iterator i,j,m,n;
    for (boost::tie(i, j) = vertices(g); i!=j; i++) {
        for (boost::tie(m, n) = vertices(g); m!=n; m++) {
            cout << "The edge[" << g[*i].id << " -> " << g[*m].id << "] " << flush; 
            if(boost::edge(*i,*m,g).second){
                cout << "exsits. The weight is " << g[boost::edge(*i,*m,g).first].weight << "." << endl;
            }else{
                cout << "is nothing." << endl;
            }
        }
    }

vertex_iterator を用い、すべてのノードについてfor文を回している。

3.2 出力

The edge[0 -> 0] is nothing.
The edge[0 -> 1] exsits.[Weight = 0.5]
The edge[0 -> 2] exsits.[Weight = 0.5]
The edge[0 -> 3] is nothing.
The edge[1 -> 0] is nothing.
The edge[1 -> 1] is nothing.
The edge[1 -> 2] exsits.[Weight = 0.5]
The edge[1 -> 3] exsits.[Weight = 0.5]
The edge[2 -> 0] exsits.[Weight = 0.5]
The edge[2 -> 1] is nothing.
The edge[2 -> 2] is nothing.
The edge[2 -> 3] exsits.[Weight = 0.5]
The edge[3 -> 0] exsits.[Weight = 1]
The edge[3 -> 1] is nothing.
The edge[3 -> 2] is nothing.
The edge[3 -> 3] is nothing.

参考

• [c++,boost] boost::graphのお勉強 https://qiita.com/kktk-KO/items/6c53e1c550cae441c969 #Qiita
• Boost Graph LibraryとGraphvizでグラフの可視化 - メモ帳 http://tomov3.hatenablog.com/entry/2016/06/22/103530
• 公式リファレンス https://www.boost.org/doc/libs/1_57_0/libs/graph/doc/graph_concepts.html https://www.boost.org/doc/libs/1_70_0/libs/graph/doc/AdjacencyMatrix.html