LEMON Graph Libraryで有向グラフを作成

前回,LEMON Graph Libraryのインストールに成功したので,今回は有向グラフの作成をやってみる.

悪名高いBoost.Graphでは,使いはじめる前にひたすらtypedefをしていく作業(もしくはよくわからないままtypedefをコピペする作業)が待っているが,LEMON Graph Libraryはシンプル.

#include <lemon/list_graph.h>

をインクルードして

lemon::ListDigraph g;

でOK.

頂点の追加は

lemon::ListDigraph::Node a = g.addNode();
lemon::ListDigraph::Node b = g.addNode();

辺の追加は

lemon::ListDigraph::Arc ab = g.addArc(a,b);

でOK.
非常にわかりやすくて簡単.

頂点も辺も同じようにプロパティを割り当てることができる.
それをするのがMap.
頂点ならNodeMap,辺ならArcMapを使う.
これはテンプレートクラスなので,プロパティの型をテンプレートで渡す.
例えばdouble型で表現される辺の重みと,std::string型で表現される頂点の名前なら以下のようになる.

lemon::ListDigraph::ArcMap<double> weight(g);
lemon::ListDigraph::NodeMap<std::string> name(g);

weight[ab]=1;
name[a]="NodeA";
name[b]="NodeB";

まとめると,

#include <lemon/list_graph.h>

int main(){
    lemon::ListDigraph g;
    
    auto a = g.addNode();
    auto b = g.addNode();
    auto c = g.addArc(a,b);

    lemon::ListDigraph::ArcMap<double> weight(g);
    lemon::ListDigraph::NodeMap<std::string> name(g);

    weight[ab]=1;
    name[a]="NodeA";
    name[b]="NodeB";

    return 0;
}

次回はこれをファイルに保存したり,読み込んだりするところの説明をする予定.