グラフリテラル

Gordon Woodhull: Introducing MPL.Graph(pdf)

BoostCon 2011のMPL.Graphの資料を見たら、GraphのEDSLの案が出ていたので、似たようなのを作ってみました。

edges = (
    vertex(A) >= vertex(B) &
    vertex(A) >= vertex(C) >= vertex(D)
);

のようにして、

A-B

C

D

のようなグラフを作ります。
operator>=()は辺を表していて、operator&()は辺の区切りに使用します(カンマ演算子がうまくいかなかった)。

Boost.Graphは辺の組み合わせを書いていかないといけないので、リテラルを書くのがめんどくさいと前から思っていて、
adjacency transformのようにして{A, B, C}から{(A,B), (B,C)}を作れば頂点のリストから辺のリストを生成できるな、と考えてそのようにして構築しました。

サンプルコード：

#include <fstream>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <shand/graph_literal.hpp>

enum vertex_type { A, B, C, D, N };
const std::string name = "ABCD";

int main()
{
    typedef
        boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS>
    graph_type;

    using shand::vertex;
    const shand::graph_converter edges = (
                vertex(A) >= vertex(B) &
                vertex(A) >= vertex(C) >= vertex(D)
            );

    graph_type g(edges.begin(), edges.end(), N);

    std::ofstream file("test.dot");
    boost::write_graphviz(file, g, boost::make_label_writer(name.c_str()));
}

出力されるGraphvizのデータ(test.dot)：

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

Graphvizから生成したグラフの画像：

ライブラリのコード：

shand/graph_literal.hpp
shand/fusion/adjacency_for_each.hpp

ちなみに現在のこのバージョンでは、1本の辺は書けません。
それと、頂点の総量がわかっているので、Nを自動的に計算してadjacency_listを直接構築できるようにしようと思ってます(MultiIndexを使って重複あり挿入順リストと、重複なし辞書順リストを同時に持つ予定)。

ちなみに、リテラルなので実際はそんなに使わないと思います。

追記：2011/07/25 19:17
adjacency_listの直接構築に対応しました。

#include <fstream>
#include <string>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <shand/graph_literal.hpp>

enum vertex_type { A, B, C, D, N };
const std::string name = "ABCD";

int main()
{
    typedef
        boost::adjacency_list<boost::vecS, boost::vecS, boost::bidirectionalS>
    graph_type;

    using shand::vertex;
    graph_type g = (
                vertex(A) >= vertex(B) &
                vertex(A) >= vertex(C) >= vertex(D)
            );

    std::ofstream file("test.dot");
    boost::write_graphviz(file, g, boost::make_label_writer(name.c_str()));
}