2014-12-03

Facebookのデータセンタネットワーク

これはhttp://www.adventar.org/calendars/440の２日目の記事です．

はじめに

本エントリでは，最近のデータセンタNWのトポロジについて，データセンタNWの最先端を走っているfacebookの事例をベースに，論文/blog等交えて簡単に紹介したいと思います．

一般的なデータセンタNW

まず，現在のDC向けネットワークトポロジの基本となるFat-Treeについて。
Fat-Treeは，一般的なツリーでボトルネックとなる上位階層のリンク帯域を太く/多重化したツリー構成を持つNWトポロジです。
各段のスイッチの上流/下流が同じ帯域幅を提供するように構成することで、Fat-Treeに接続するノードが全体全の通信を一斉に行う最悪のケースにおいても、リンク帯域の食い合いを発生させることなく、ノード間通信の帯域を保証することが出来ます。
このように構成されたネットワークの事をフルバイセクションネットワークと呼びます。
ネットワークがフルバイセクションであることは、特にMPI等のall-to-all通信を頻繁に行うHPC分野では重要な特性ですが、一般的なDCネットワークでは、ノードの収容効率を高めるため下流に比べて上流が細い(oversubscription)構成が一般的でした。
このへんの話はこのスライドがオススメです（Infinibandですが基本的な考え方は変わりません）

ビジネス向けIBネットワークを考える〜HPCクラスタでの経験を踏まえて〜 from Naoto MATSUMOTO

"4-post" Architecture

FacebookのDCにおいても、2013年頃に公開された論文によると，
Fat-Treeにリングを追加した亜種のようなトポロジを採用しており，上流下流の接続だけを見ると，CSWスイッチで10:1,FCスイッチで4:1のoversubscriptionがされています．
このトポロジは，DC内のInter-Clusterの通信帯域を一部犠牲にして，ノードの収容効率を高めたトポロジと言えます．
論文よりトポロジ図を引用します．

論文によると，当時の時点でこの巨大なCSW/FCスイッチに依存するトポロジは以下の点で問題があったと書かれています．

CSW/FCスイッチに障害が発生した場合，それぞれintra/inter clusterの帯域幅が25%失われる
CSWスイッチのサイズがclusterのサイズを決定づける．そのため，非常に大きいclusterとなる
スイッチを提供可能なベンダが限られ，結果としてOPEX/CAPEXの増加を招く
スイッチ内部のfabric自体がoversubscriptionしていることがあり，全てのポートをwirerateで同時に利用できないことがある
巨大なスイッチは数売れるものではないため，ベンダのバグフィックスに時間がかかり，カスタムプロトコルなどの実装も困難

この問題に対して，上記論文では他のHPCなどで利用されているトポロジ等を参考に，柔軟にscale-out可能で，高性能スイッチに依存しないトポロジの検討が行われています．

fabric Architecture

検討の結果が結実したと思われるのが，2014年11月にdeployされたFacebook Altoona Data Centerです．
Altoona DCの新しいネットワークアーキテクチャに関しては，Facebook Engineer blogに情報があります．
この新しいネットワークアーキテクチャでは，4-post architectureに関する論文で指摘のあった問題に加え，指数的に増加するDC内のノード間通信(west-east traffic)に対応するために工夫がされています．

トポロジ構成

トポロジ構成上のポイントは以下のとおりです．

48台のToRを4台のFabricスイッチで束ねた単位(pod)をunit of networkとして定義し，pod単位での柔軟なコンピューティング能力の拡張を可能にした
intra-cluster/inter-cluster/north-south trafficそれぞれについて，Planeという単位で分割を行うことで，それぞれ独立した性能拡張を容易に
指数的に増加するeast-west trafficに対応するため，oversubscriptionを基本的にはしない構成とした(pod内fabric switchは上流下流共に同一ポート数)

以下，blogよりトポロジ構成図を引用します．

この図からは，小さいpodという単位をベースに，intra/inter/north-south traffic用のplaneが分割されていることがわかると思います．
結果，computing resourceを追加する場合はpodを，intra-clusterの帯域を増強するためにはspineスイッチを，north-southの帯域増強のためにはedge pod/uplinkを増強するなど柔軟な機能拡張を行うことが可能になっています．

ネットワーク制御

DC内は，ToRからedgeまですべてBGPベースのL3ネットワークで構成されています．
装置側は一般的なBGP Stackを用いている一方，blogにはcentralized BGP controller というものを開発したとあり，基本的にはBGPの一般的な経路制御を行い，一部集中制御で明示的にパス決定し，BGP経由で注入できる仕組みが入っているようです．
この辺りは詳細の記述がblogにないため，続報が待たれるところです．

物理構成（フロアプラン）

podで小さなクラスタを作ることで，論理トポロジを柔軟に拡張可能であることは前述したとおりですが，
この柔軟性は，物理構成にも同様の柔軟性を与えています．
以下，blogより物理構成図を引用します．

inter-clusterの相互接続を提供するspine-planeがBDF roomと呼ばれる部分に集約されており，実際のコンピューティングノード(pod)が収容されているMDF roomとは直線的に配線されています．
そのため，施工がしやすく，podを追加する場合もMDF roomのBDF roomに近い側から順次サーバラックを増設していくことで物理構成上も見通しの良い拡張が可能となっています．

まとめ

本エントリでは主にFacebookのDCネットワークについて，論文/blogからの引用をベースに紹介を行いました．
今回紹介した内容以外にも，Altoona DCの構成についてはFacebook Engineer blogにその他いろいろ情報があるので，気になった方はblog本体を参照することをオススメします．

おまけ

FacebookのDCネットワークに関しては，SIGCOMM2014で発表されたFastPassなども関連があるようです．
現状productionで動いているわけではない？ようですが，著者にFacebookの方が入っており，評価も実DCでやったような事が書かれています．
詳しくはまだ読んでいないのですが，ネットワークワイドにパケットの送出タイミングを集中制御するアービタを実装することで，パケットがスイッチのキューに貯まることを防ぎ，east-west trafficのRTTを改善するようなもののようです．
アービターというとPCI Busのようなガチガチのタイミング制御を思い浮かべるのでIPネットワークでアービタ？ホントにできるの？という感じが若干していて気になるので，今週末のシステム系論文輪読会３で読もうかなと思ってます．

2012-12-05

Boost::Graphへの独自のproperty追加とdynamic_propertiesを使ったdotファイル読み込み

これはC++ Advent Calendar 2012の5日目の記事です。

はじめに

気づくと最新のエントリが去年のAdvent calenderとなっていて一年ぶりの記事になってますね．
やはりtwitterを始めるとblog書かなくなるというのは本当ですね．（そして迫る修士論文
今回は，去年と同じようにBoost::Graphに関する日本語情報の少ない機能について補完してきたいと思います．
本当であれば実装を追いたかったのですが，少し時間がないため使い方程度の記事としたいと思います．
本エントリでは，

グラフに任意のプロパティを追加
追加したプロパティをdynamic_propertiesを使ってdot(graphviz)形式で入出力

といった話をしようと思います．

グラフに任意のプロパティを追加

Boost::Graphでは，グラフの頂点やエッジに付加情報をつけるために，Boost::propertyを使っています．
デフォルトでは以下のpropertyが定義されています．

  struct vertex_index_t { };
  struct vertex_index1_t { };
  struct vertex_index2_t { };
  struct edge_index_t { };
  struct graph_name_t { };
  struct vertex_name_t { };
  struct edge_name_t { };
  struct edge_weight_t { };
  struct edge_weight2_t { };
  struct edge_capacity_t { };
  struct edge_residual_capacity_t { };
  struct edge_reverse_t { };
  struct vertex_distance_t { };
  struct vertex_root_t { };
  struct vertex_all_t { };
  struct edge_all_t { };
  struct graph_all_t { };
  struct vertex_color_t { };
  struct vertex_rank_t { };
  struct vertex_predecessor_t { };
  struct vertex_isomorphism_t { };
  struct vertex_invariant_t { };
  struct vertex_invariant1_t { };
  struct vertex_invariant2_t { };
  struct vertex_degree_t { };
  struct vertex_out_degree_t { };
  struct vertex_in_degree_t { };
  struct vertex_discover_time_t { };
  struct vertex_finish_time_t { };

いろいろとありますが，いくつかはRead onlyなmapなので(indexなど），
頂点に重みがあるようなグラフ（頂点が都市を表していてその人口など）では，
vertex_weight_tなどわかりやすいpropertyを自分で追加したくなるのではと思います．
例えばvertex_weight_tをグラフに追加するためには以下のようにboost名前空間に自分でタグを追加します．

namespace boost{
  enum vertex_weight_t{vertex_weight};
  BOOST_INSTALL_PROPERTY(vertex,weight);
}

こうして追加したpropertyは，デフォルトで定義されているpropertyと同じように，グラフの定義で追加し，
boost::get/putで操作することができます．

typedef boost::adjacency_list<
  boost::listS, boost::vecS, boost::undirectedS,
  boost::property<boost::vertex_weight_t, int>,
  boost::no_property > MyGraph;//グラフに独自に定義したpropertyを追加

  MyGraph g;
  int num = 0;
  boost::get(boost::vertex_weight,g,0);
  boost::put(boost::vertex_weight,g,0,num);

追加したプロパティをdynamic_propertiesを使ってdot(graphviz)形式で入出力

このように，独自のpropertyをグラフに追加することができましたが，
次はこれを入出力することを考えてみたいと思います．
今回，グラフの表現フォーマットとして，古くからあるdot(graphviz)形式での入出力を考えます．

graph G {//入力したいdotファイル
0[label=A][vweight=1];//各頂点に重み属性が付与されている(vweight)
1[label=B][vweight=2];
2[label=C][vweight=3];
3[label=D][vweight=4];
4[label=E][vweight=5];
5[label=F][vweight=6];
0--1 ;
1--2 ;
3--4 ;
4--5 ;
0--3 ;
1--4 ;
2--5 ;
}

read_graphvizを使ったdotファイルの入力

Boost::graphには，dot形式での入出力用のAPIが用意されています．

namespace boost {

  template <typename MutableGraph>
  bool read_graphviz(std::istream& in, MutableGraph& graph,
                     dynamic_properties& dp,
                     const std::string& node_id = "node_id");

  template <typename MutableGraph>
  bool read_graphviz(std::string& str, MutableGraph& graph,
                     dynamic_properties& dp,
                     const std::string& node_id = "node_id");

  template <typename InputIterator, typename MutableGraph>
  bool read_graphviz(InputIterator begin, InputIterator end,
                     MutableGraph& graph, dynamic_properties& dp,
                     const std::string& node_id = "node_id");

}

上のAPIを見ると，boost::dynamic_propertiesというのが登場していることがわかります．
詳細についてはリファレンスを参照してほしいのですが，簡単なイメージで説明すると，
これは，ファイルからのデータ入力などコンパイル時に入力データの型を静的に決定できないものを
boost::propertyを使って扱うために用意されているシステムです．
boost::propertyをvalue,stringをkeyとしたproperty mapのようなインターフェイスとなっており，
dot形式ファイルをランタイムで読み込む際には，dot形式における属性をkey,その属性をputしたい先の
graphに付与されたpropertyをvalueとしたdynamic propertyをread_graphvizに渡すことで
dotファイル中で属性の記述を発見した時に自動的に指定したpropertyにputしてくれるようになります．

また，APIを使ってdotファイルから読み込みを行う際には，独自に定義した属性だけでなく，
dotファイル暗黙的に存在するnodeidを処理する必要があります．
read_graphvizでは，これを属性として捉えてパースするため，
暗黙的なnodeidをなんという属性名にするか(key側），そしてそれをどのpropertyに紐付けるかの設定が必要です．

int main()
{ 
  MyGraph g;
  boost::dynamic_properties dp;

  //以下gに追加されているpropertyとkeyを関連付け（vertex_node_id/vertex_weightは独自定義タグ）
  dp.property("node_id",boost::get(boost::vertex_node_id,g));//暗黙的なnode_idをvertex_node_idに割り当て
  dp.property("label",boost::get(boost::vertex_name,g));//自分で追加した属性
  dp.property("vweight",boost::get(boost::vertex_weight,g));//自分で追加した属性


  std::ifstream infile("test.dot");
  read_graphviz(infile,g,dp,"node_id");//最後の引数で暗黙的なnodeidを"node_id"というkeyとして扱うと宣言
                                                                                                         
  return 0;
}

上のようにすることで，dotファイルの属性をgraphのpropertyに入力することができます．
上ではやっていませんが，read_graphvizでは，渡されたdynamic_propertiesのkeyとして設定されていない，
属性を発見すると例外を吐くので，try-catchをきちんとするか，もしくはunknown itemを発見した場合に
呼ばれるファンクタを適切に設定してやる必要があります．
また，出力に関してもdynamic_propertiesを同様に使う方法と，エッジ及び頂点の書き出し用関数用オブジェクトを指定する方法の２つが用意されています．

最後に

今回は独自propertyの定義とdynamic_propertiesを使ったdotファイルの読み込みについて解説しました．
本当は，細かい実装や，独自のVisitorで探索アルゴリズムの拡張などまで書きたかったのですが，
いま余裕がないのでまた今度文章にしたいと思います．それでは！

2011-12-21

これはBoost Advent Calendar 2011の21日目の記事です。

はじめに

今回は自分が本格的にBoost.Graphを使う必要ができたときにぐぐっても意外と情報の少なかった
頂点や辺を動的に追加したり削除する方法や注意点について書きたいと思います．
まず，WebでBoost.graphの日本語情報を探すと，以下のようなものが多いと思います．
//ちょうどよかったのでid:futadaさんのコードを引用させて頂きます．

たとえば、3個のvertexからなり、vertex 0 -> 1、0 -> 2、1 -> 2の3個のエッジを持つ有向グラフのデータをBoost.Graphを使って作るには以下のようなコードになります。
#include <vector>
#include <boost/graph/adjacency_list.hpp>

int main()
{
  std::vector<std::pair<int, int> > edge_list = {{0, 1}, {0, 2}, {1, 2}};
    
  typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
				boost::no_property,
				boost::no_property,
				boost::no_property> Graph;

  Graph graph(edge_list.begin(), edge_list.end(), 3); // コンストラクタの引数は、エッジイテレータの最初, 最後, vertex数の順

  return 0;
}
http://d.hatena.ne.jp/futada/20111220/1324389070

上のコードでは，コンストラクタでグラフを構築しています．
執筆者の意図として，より細かいアルゴリズムの適用などを見せたいというのがあるのであれば
グラフの構造についてコード中にstaticに記述してしまうのは妥当だと思いますが，
実際Boost.Graphを使う場合はこのように構造をコード中に記述することはあまりないと思います．
（実際使い始めるときに一番自分が躓いたのはここでした）

コンストラクタ以外で頂点や辺を追加

普通に実用するとコンストラクタでない場所で頂点や辺を追加したくなるわけですが，
それを行うには以下のようにadd_edgeとadd_vertexを使うことになります．

#include <boost/graph/adjacency_list.hpp>

enum {VA,VB,VC};
int main()
{
  typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
				boost::no_property, boost::no_property> Graph;
  
  Graph graph;
  
  for(int i = 0;i < 3;++i)
    boost::add_vertex(graph);
  
  boost::add_edge(VA,VB,graph);
  boost::add_edge(VA,VC,graph);
  boost::add_edge(VB,VC,graph);
  
  return 0;
}

一見これでうまく行っているように見えるのですが，実はこのコードには問題があります．
例えばここで，graphの内部の頂点配列のコンテナをlistSに切り替えた以下のコードはコンパイルエラーになります．

#include <boost/graph/adjacency_list.hpp>

enum {VA,VB,VC};
int main()
{
  typedef boost::adjacency_list<boost::vecS, boost::listS, boost::directedS,
				boost::no_property, boost::no_property> Graph;//２つ目の引数をvecSからlistSに変更
  
  Graph graph;
  
  for(int i = 0;i < 3;++i)
    boost::add_vertex(graph);
  
  boost::add_edge(VA,VB,graph);
  boost::add_edge(VA,VC,graph);
  boost::add_edge(VB,VC,graph);
  
  return 0;
}

bash-3.2$ g++ main.cpp
main.cpp: In function ‘int main()’:
main.cpp:37: error: cannot convert ‘<anonymous enum>’ to ‘void*’ for argument ‘1’ to ‘std::pair<typename Config::edge_descriptor, bool> boost::add_edge(typename Config::vertex_descriptor, typename Config::vertex_descriptor, boost::directed_graph_helper<Config>&) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS, boost::listS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>::config]’
main.cpp:38: error: cannot convert ‘<anonymous enum>’ to ‘void*’ for argument ‘1’ to ‘std::pair<typename Config::edge_descriptor, bool> boost::add_edge(typename Config::vertex_descriptor, typename Config::vertex_descriptor, boost::directed_graph_helper<Config>&) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS, boost::listS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>::config]’
main.cpp:39: error: cannot convert ‘<anonymous enum>’ to ‘void*’ for argument ‘1’ to ‘std::pair<typename Config::edge_descriptor, bool> boost::add_edge(typename Config::vertex_descriptor, typename Config::vertex_descriptor, boost::directed_graph_helper<Config>&) [with Config = boost::detail::adj_list_gen<boost::adjacency_list<boost::vecS, boost::listS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>, boost::listS, boost::vecS, boost::directedS, boost::no_property, boost::no_property, boost::no_property, boost::listS>::config]’

上のエラーはadd_edgeに渡す頂点記述子VA,VB（vertex_descriptor)はintではなくvoid*だよというエラーです．
いままで頂点を指定するのになんとなく０から始まる整数値を使っていたと思いますが，この頂点記述子は常にintではありません．
これを仮定する形でenumを使って簡単に頂点に名前をつけているコードなども見かけますが，
本来は以下のコードのようにadd_vertex()から返される頂点記述子をきちんと保存しておき，それを使ってadd_edgeするべきです．

#include <boost/graph/adjacency_list.hpp>
#include <map>

int main()
{
  typedef boost::adjacency_list<boost::vecS, boost::listS, boost::directedS,
				boost::no_property, boost::no_property> Graph;
  
  Graph graph;
  std::map<int,Graph::vertex_descriptor> desc;//Graph::vertex_descriptorで頂点記述子の型を取得
  for(int i = 0;i < 3;++i)
    desc[i] = boost::add_vertex(graph);
  
  boost::add_edge(desc[0],desc[1],graph);
  boost::add_edge(desc[0],desc[2],graph);
  boost::add_edge(desc[1],desc[2],graph);
  
  return 0;
}

きちんとBoost.Graphのコードを読めていないので単なる推測ですが，
この頂点記述子はgraphが内部的に持っている頂点データのデータ構造を一意に特定できればいいはずなので，
vecSの場合はvectorのindexになっているのではないかと思います（なのでint)

頂点の削除

次に頂点の削除について考えてみます．
頂点の削除はremove_vertexを用いて行います．

#include <boost/graph/adjacency_list.hpp>
#include <map>

int main()
{
  typedef boost::adjacency_list<boost::vecS, boost::listS, boost::directedS,
				boost::no_property, boost::no_property> Graph;
  
  Graph graph;
  std::map<int,Graph::vertex_descriptor> desc;//Graph::vertex_descriptorで頂点記述子の型を取得
  for(int i = 0;i < 3;++i)
    desc[i] = boost::add_vertex(graph);
  
  boost::add_edge(desc[0],desc[1],graph);
  boost::add_edge(desc[0],desc[2],graph);
  boost::add_edge(desc[1],desc[2],graph);

  boost::clear_vertex(desc[0],grapg);//頂点を含む辺を削除する
  boost::remove_vertex(desc[0],graph);//頂点を削除
  
  boost::add_edge(desc[2],desc[1]);//その後辺を追加
  return 0;
}

上のようにすることで，正常に最初に追加した頂点を削除し，その後二，三回目に追加した頂点のを結ぶ辺を作ることができます．
ここで以下のように頂点のデータ構造をvecSに変更してみます．

#include <boost/graph/adjacency_list.hpp>
#include <map>

int main()
{
  typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
				boost::no_property, boost::no_property> Graph;
  
  Graph graph;
  std::map<int,Graph::vertex_descriptor> desc;//Graph::vertex_descriptorで頂点記述子の型を取得
  for(int i = 0;i < 3;++i)
    desc[i] = boost::add_vertex(graph);
  
  boost::add_edge(desc[0],desc[1],graph);
  boost::add_edge(desc[0],desc[2],graph);
  boost::add_edge(desc[1],desc[2],graph);

  boost::clear_vertex(desc[0],grapg);//頂点を含む辺を削除する
  boost::remove_vertex(desc[0],graph);//頂点を削除
  
  boost::add_edge(desc[2],desc[1]);//その後辺を追加...とはならない
  return 0;
}

これは意図したどおりの動作をしません．
先ほど説明したとおり，頂点記述子はgraph内部の頂点データ配列を一意に特定できる何かのはずです．
内部のデータ構造にvecS(vector)を指定した場合，記述子が配列のindexそのままとなるのであれば，
頂点を削除した際に内部のvectorが連続性を保証するため前に１つずつ詰められ，
add_vertexの際に保存した頂点記述子と内部のindexがずれることになります，
そのため，vecSを指定した場合，graphに対して削除などのオペレーションを行ったあとの頂点記述子は無効になります．
実はこの辺はgraphのドキュメントにきちんとまとめて書いてあります．

http://www.boost.org/doc/libs/1_39_0/libs/graph/doc/adjacency_list.html

よって，頂点や辺の削除を行う予定のあるグラフを扱う場合は，
自分のユースケースに応じた適切なコンテナを指定するのが非常に重要です．

最後に自分が少し引っかかったことについて

ここまで読んでいただいて，graphにおける頂点配列コンテナの指定には，パフォーマンス以外にも
動作の違いがあることがわかってもらえたと思います．
最後に，このvecSとlistSの切り替えに関して自分が躓いたトピックについて書いておきたいと思います．

listSにするとvertex_index_tがデフォルトで付加されていない

Graphには指定しなくてもデフォルトで付与されるプロパティがあります．
しかし，指定したコンテナによっては付与されるデフォルトプロパティが異なります．
そのため，以下のgraphviz書き出しを行うコードはvecSの場合追加でプロパティを指定しなくても動作しますが，
listSを指定した場合は，write_graphvizが使用するvertex_index_tプロパティを自分で指定し，
きちんとputしてやることが必要になります．

#include <boost/graph/adjacency_list.hpp>
#include <map>
#include <boost/graph/graphviz.hpp>

int main()
{
  typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
				boost::no_property,boost::no_property> Graph;//vecSの場合はこれでOK
				//boost::property<boost::vertex_index_t,int>, boost::no_property> Graph;//listSの場合は必要
  
  Graph graph;
  std::map<int,Graph::vertex_descriptor> desc;//Graph::vertex_descriptorで頂点記述子の型を取得
    for(int i = 0;i < 3;++i){
    desc[i] = boost::add_vertex(graph);
    //    boost::put(boost::vertex_index, graph, desc[i], i);//listSの場合必要
    }
  
  boost::add_edge(desc[0],desc[1],graph);
  boost::add_edge(desc[0],desc[2],graph);
  boost::add_edge(desc[1],desc[2],graph);

  boost::write_graphviz(std::cout, graph);
  return 0;
}

これは，vecSでは頂点記述子をそのままvertex_index_tをして使っているためだと思います．
このように，割とlistSだと面倒な事が全体的に増えます（個人的な印象）

vecSの際に無効な頂点記述子を指定して辺の追加などを行うと新しい頂点が作成されてしまう

いままでvecSを指定したgraphに対してadd_vertexした後にadd_edgeしていましたが，
実はadd_vertexしなくてもadd_edgeできてしまいます．

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>

int main()
{
  typedef boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS,
				boost::no_property,boost::no_property> Graph;
  
  Graph graph;
  
  boost::add_edge(0,1,graph);
  boost::add_edge(0,2,graph);
  boost::add_edge(1,2,graph);

  boost::write_graphviz(std::cout, graph);
  return 0;
}

どうやら範囲オーバーしたvertex_descriptorが与えられた場合，
新しく頂点が自動的に作成されるようです．
割とこの動作が見つけにくいバグの原因になることがあるので気をつけておくと良いと思います．
（個人的にはassertion failedになってほしい）

最後に

すごく雑多に書きましたが，基本的に自分がgraphを実用するにあたって当たった壁や理解するまで時間のかかった部分をまとめてあります．
前半webの情報は駄目だみたいなことを書いていますが，サンプルコードと実用コードは違うので，
エッセンスを短くまとめる上で頂点記述子の型をintと仮定したりするのは全く問題ないと思っています．
id:futadaさんの記事で基本的な使い方やproperty_mapについてわかりやすい解説があるので，
この記事も併せて初めてgraphを使う人への助けになればと思います．

2010-10-09

Unixからシリアルポートに接続

メモ Unix

個人的なメモとして

cuを使うのでインストール

aptitude install cu

物理COMポートを使う場合は

dmesg | grep tty

などでどこに割り当てられたか確認

cu -l /dev/ttyS0 -s 115200

で接続

permission deniedとか出てきたら
/dev/ttyS0にchmodとかで適切な権限を

cuから抜けるには接続中に

~.

でOK

2010-01-07

Androidのエミュレータがavdファイルを上手く見つけてくれない件について

Android

ちょっとAndroid開発に手を出すことになりそうなので、SDKをセットアップしてエミュレータの起動をしてみることに。

SDK Setup.exeのVirtual Devicesから適当なエミュレータのプロファイルを作り（名前はTestAvdとする）
startボタンから起動しようとしてみるも

emulator: ERROR: unknown virtual device name: 'TestAvd'
emulator: could not find virtual device named 'TestAvd'

とか出てきて起動できない

一応

android list avd

でみると、きちんとavdは登録されているようだし、

emulator @TestAvd

としても同じメッセージが出てくる。

仕方なくぐぐってみると、ちょうど同じ問題を発見
どうやらプロファイルを別ドライブにしていると、avdファイルが作成されるのは移動したドライブ（Dとか）なのに反して
emulatorはそんなこと関係なくCドライブを見に行くので問題が起きるらしい。
そこで、

cd c:\users\<username>\
mklink /D .android d:\<自分で変更したパス>\.android\

みたいにシンボリックリンクを張ってやったら動いた。

netbeansからのエミュレータ起動、ステップ実行も出来たのでこれでいろいろ試せるかな

2009-12-15

Boost.勉強会に参加してきました！

C++ Boost

12/12に開催されたBoost.勉強会に参加してきました。
当日は会場も広く、非常にいい環境だったと思います。
ネット接続については、wifiに繋ぐのに乗り遅れて、外向けのセッションを張れなくなってしまったので（ルータの上限数？）
N82でテザリングしてつぶやいたりしてました。
後半つぶやきが減ってるのは、ソフトバンクにセッションを切断されまくってたからですｗ
では、当日のつぶやきと感想をそれぞれのセッションについて書いておきます。

10:10〜11:00：Boostライブラリ一周の旅(faith_and_brave)

つぶやき

lexical_castってConversionライブラリの一部だったのか。というかlexical_cast以外の型変換系があったことを知らなかった #boostjp
Formatは便利。Qt使ってるとQString.arg()でにたことできるからあんまり最近使わないけど #boostjp
Function Typesは試しに実装してみると楽しそう #boostjp
FusionってLoki::Typelist+実行時にうにゅうにゅみたいなやつだったんだ。使った事ないな #boostjp
Intervalなんてあるんだ。今作ってる計測系のソフトで使えそう #boostjp
後ろに座りすぎてスライド見えないなー。移動しようかな #boostjp
お！Operatorsなんてあるのか！ C#だとやってくれるのにめんどくせーって思ってたけどこれで解決じゃん #boostjp
Parameterはverilogの明示的なモジュール接続みたいな感じ。便利そう #boostjp
Protoなんてあったんだ・・・。偽ETみたいなの自作してたよ・・・ #boostjp
BLASとかもProto使ってるのかな。登場時期からすると使ってないか #boostjp
Range気になってるけど使った事ないなー #boostjp
あーrefってそういう意味合いだったんだ。boost::thread使うときに適当に使ってた記憶が・・・ #boostjp
Signal2だ！Qt5はこういう感じでmocとuicをなくしてほしい #boostjp
Boost::threadってまだスレッド優先度の設定できないんだっけ？ #boostjp
お、uBLASきた！微妙に使うのめんどいけどはやい（らしい） #boostjp
shared_from_thisとかもutilとかに入ってるのかな。 #boostjp

感想

正直boostはライブラリ数多すぎで、「きっと自分が知らない便利な物があるんだろうなー」っていうもやもやがずっとあったので、
一周の旅で全ライブラリを紹介してもらえてすごくありがたかったです。
１ライブラリに割く時間が短かったのですが、非常に用途用例がわかりやすいものが多くて
今の何？　ってこともありませんでした。
とりあえずセッション中につぶやきながら取ったすごくラフな自分用メモを晒しておきます（普段使わないライブラリについて主にメモ）

・Circler Buffer
	  古いもの捨てられていくバッファ
・Concept Check
	  エラーメッセージがわかりやすく
・Convarsion
	lexical_castとその仲間たち
・CRC
	まあCRC
・enable_if
	type_traits使ったオーバーロード
・Flyweight
	Flyweightデザインパターンの実装（リソースの共有）
・foreach
	マクロで実現されたforeach
・Function Types
	   関数の型を取得するメタ関数
・Fusion
	Loki::typelist＋実行時
・Interprocess
	プロセス間共有メモリ
・Interval
	区間計算
・Intrusive
	侵入型のコンテナ
・IO State Server
   	 iostreamの状態管理（出力のhexとかをスコープ抜けた時に戻す）
・Iostreams
	お手軽stream作成
・Iterators
	お手軽Iterator作成
・Math
	数学の特殊関数形が定義されてるよ（クオータニオンとか
・Member Function
	 std::mem_funとstd::mem_fun_refを一般化したもの
・Multi Array
       	多次元配列
・Multi Index
	indexed_by<>で取り出し方法を指定できるindex
・Numeric Conversion
	数値型同士の変換（桁の処理方法とか指定できるっぽい）
・Operators
	関連する演算子の自動生成（C#みたいな感じ）
・Optional
	無効値の統一的な表現
・Parameter
	verilogの明示的モジュール接続みたいな
・Pointer Container
	ヒープオブジェクトのポインタ用コンテナ（スマートポインタより早い）
・Pool
	メモリープール
・Preprocessor
	暗黒面
・Property Map
	iterator_traitsの拡張みたいなもの（要調査）
・Proto
	ETできるよ！
・Python
	ぱいそん！
・Random
	次期標準疑似乱数生成ライブラリ
・Range
	れんじ！
・Ref
	明示的に参照にする（型が値として推論されないように）
・Scope Exit
	スコープ出た時の実行コード（キャプチャできるよ！）
・Serialization
	シリアライズ・デシリアライズ
・Signal2
	しぐなる！
・Smart Pointers
	scoped_pointerとか
・Spirit
	パースできる
・StateChart
	状態マシン
・Static Assert
	0xのstatic_assert()を実現したマクロ
・String Algo
	文字列周りのアルゴリズム（大文字に変換とか右の空白を除去とか）
・Swap
	組み込み配列もswapできる（vectorの場合は専用アルゴリズムを使用）
・System
	各OSのエラーコードをラップして汎用化
・Test
	ゆにっとてすとー
・Timer
	簡単な時間計測（スコープベースとか）
・Tribool
	３値bool
・Tuple
	std::pairの3つ以上版
・Typeof
	0xのautoとdecltypeをエミュレーション
・Units
	単位計算（mとかcmとか）
・Unordered
	ハッシュ表の連想コンテナ（要調
・Wave
	C++のプリプロセッサを拡張できる（要調査）
・Xpressive
	正規表現（コンパイル時にもできるらしい？）

懇親会

1次の懇親会は~~どうみてもキャバクラ~~おしゃれなバー、二次会は国際色豊かなバーでした。
食べ物少なすぎでしたが、いろいろな方とお話しできたので良かったです。
当日はどうせ配らないだろうと思って名刺を10枚しか持っていかなかったので、
twitterで見かけたことのある方に挨拶するのがやっとで、他の方にあまり渡したり出来なかったので残念です。
帰りはTXが無くなったので、ミッドナイトつくば号でバス酔いしながら帰る感じでした。

まとめ

LLの勉強会って本当にたくさんあると思うんですが、C++の勉強会となると驚くほど少なくて、
今回こういう形で集まることが出来てすごく良かったです。
参加してる方のレベルもすごく高くていろいろ勉強になりました。
ATNDの枠の埋まる早さなどを見るに需要はあるみたいなので、今後もどんどん継続してやっていってほしいなーと思います！（次回は大阪らしいです）

2009-12-06

ユーザ定義変換演算子の戻り値型について

C++

どうやらC++の変換演算子（operator ClassName())は、コンパイル時に戻り値の型をチェックしないっぽい。

例えば、

//BからAへの暗黙の型変換
struct A
{
};

struct B
{
	operator A()
	{
		return A();
	}
};

int main()
{
	A a;
	B b;
	a = b;
}

上のコードは普通の暗黙変換。

ここで、例えば下のように間違ってoperator A()でB型を返してしまうと

struct A
{
};

struct B
{
	operator A()
	{
		//Aへの変換演算子がBを返す
		return B();
	}
};

int main()
{
	A a;
	B b;
	a = b;
}

とすると、普通にコンパイルが通って実行時にB::operator A()がBを返し、
再帰的にB::operator A()を呼び出しまくるので、スタックオーバーフローで落ちる。
ちなみに、

struct A
{
};

struct C
{
};

struct B
{
	operator A()
	{
		return C();
	}
};

int main()
{
	A a;
	B b;
	a = b;
}

とかすると、ちゃんとコンパイル時にa=bは変換できないよ！ってエラー吐いてくれる。

とりあえずこの仕様を使って、２つ以上のクラスを経由した暗黙の型変換をやってみた。
まず、普通に非explicitなコンストラクタで暗黙の型変換を行った場合

struct A
{
};

struct B
{
	B(){}
	B(A){}
};

struct C
{
	C(){}
	C(B){}
};

struct D
{
	D(){}
	D(C){}
};

int main()
{
	A a;
	B b;
	C c;
	D d;
	//(1)
	d = b;
}

(1)の部分で２つ以上のクラスを経由して暗黙の型変換を解決することは出来なのいので
コンパイルエラーになる。

これを、変換演算子が返値の型をチェックしないっぽいことを利用して書いてみると

struct D
{
};

struct C
{
	operator D()
	{
		return D();
	}
};

struct B
{
	operator D()
	{
		return C();
	}
};

struct A
{
	operator D()
	{
		return B();
	}
};

int main()
{
	A a;
	D d;
	d = a;
}

こんな感じになって、普通に動く。
まあすべてのクラスがoperator A()を持っているので、ある意味では１ホップの変換と見ることも出来るんだけど
途中で一時インスタンスが２つ以上生成されているので、ここではとりあえず暗黙の型変換と言うことで。

ちなみにこの仕様に気づいたのが、テンプレート使いまくりのポリシークラス間変換だったので、
実は原因を見つけるのにすごく時間がかかったり・・・

しかしなんで変換演算子が返す型をチェックをしない仕様になってるのか正直よくわからないので、
誰か知ってる人いたら教えて！