= Boost.勉強会#14 =

日時: 2014/3/1 10:00 ~ 18:00
場所: IIJ@神保町

== cpprefjp を支える技術 ==

 * Google Sites でリファレンスを書くのは結構大変… 統一的な書き方ができるフレームワークがほしい
 * 作業環境を GitHub に移行。
   * プレーンテキストで書きたい
   * バージョン管理しやすくしたい
   * →Markdown
 * Gogle Sites はそのままに… GitHub で書いた Markdown を自動的に HTML に変換して Google Sites に同期する。
 * cpprefjp → HTML → GitHub (MarkDown)
 * GitHub (MarkDown) → (Python) → HTML → cpprefjp
 * cpprefjp → HTML
   * Google Apps Script を使用
   * 何回かに分けた (API 制限)
 * HTML → Markdown
   * Ruby 1.9 の正規表現でがんがった
   * 手動で手直しもしました。→ツールは使い捨て (;_;)
 * GitHub → Google Sites
   * めるぽんさんが作成、運営も…
 * 変換サーバー (andare)
   * GitHub から Markdown 取得し、 HTML に変換
   * Python+Dhango製
   * Markdown という Python ライブラリを使用
 * アップロードスクリプト
   * Google Apps Script を使用
 * シンタックスハイライト
   * Markdown ライブラリにもともとあった。
   * 執筆者指定で特定の文字列をハイライトできるようにしたい。
     * 指定した文字列を検索し、一旦ランダムな文字列を前後に入れてから、その文字列を HTML に置換し直すというやり方をゴリゴリコーディングしましたよ
 * GitHub の差分管理
   * site ブランチ
     * A - B
   * master ブランチ
     * A - B - C - D
   * master ブランチと site ブランチの違いを見て更新ファイルを判断
   * Google Sites 更新後、 master ブランチを site ブランチへ merge (上図の C と D)
 * アップロード
   * スクリプトの制限
     * 実行時間は 5分まで
     * 1ファイル更新に 5秒ぐらいかかる
     * 制限1: 1回あたり 60ファイルぐらいしか更新できない
       * どこまで更新したかをストレージに保存
       * 4分過ぎたら次のタイマーを仕掛けて終了
       * 次の実行では中断したところから再開
     * …では甘かった orz
     * 制限2: ストレージの 1つのキーは 9KB まで…
     * 実行時の情報 (JSON) を格納したら漏れた
       * JSON 文字列を自動的にぶった切って複数のキーに格納
       * 取り出すときは自動的に結合して取得
   * エラー通知
     * GitHub の Issue に自動登録するようにしたよ
     * 次の実行で変換エラーがなくなれば自動で Issue を閉じるようにしてあるよ
     * 一時的なエラーの可能性もあるので失敗しても何度かはリトライ
     * エラーのあったファイルを変換サーバに POST
     * あとは変換サーバ側でいい感じに Issue に登録してくれる

== Boost.Graphの設計と、最短経路アルゴリズムの使い方いろいろ ==

 * Boost Graph Library の設計がメインのお話。
 * グラフのデータ構造とアルゴリズムのライブラリ。STL の概念に基づく。後発のグラフライブラリに大きな影響を与える。
 * グラフとは…
   * 頂点 vertex と辺 edge からなるデータ構造
     * 棒グラフや折れ線グラフとは関係ない。
   * 辺が方向を持つかどうかで有向グラフ(directed)、無向グラフ(undirected) の2つの分類があるよ。
   * ex)
     * 電車の路線
     * 道路
     * network
     * ファイルの依存関係
     * クラス図
     * 行列
       * チェス盤
     * etc...
 * グラフの用途
   * 最短経路を求める
   * 一筆書き
   * ネットワーク分析
     * コミュニティ、情報を広げる中心にいるのは誰か
     * コミュニティ同士を繋ぐ架け橋、またはボトルネックは誰か
   * ページランクの算出 (Google検索)
   * 迷路を解く
 * 文献
   * [http://www.amazon.co.jp/%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E3%81%AE%E6%9C%AC-%E3%83%AC%E3%83%8A%E3%81%AE%E3%81%B5%E3%81%97%E3%81%8E%E3%81%AA%E6%95%B0%E5%AD%A6%E3%81%AE%E6%97%85-P-%E3%82%B0%E3%83%AA%E3%83%83%E3%83%84%E3%83%9E%E3%83%B3/dp/4621061364/ref=sr_1_1?ie=UTF8&qid=1393639481&sr=8-1&keywords=%E6%9C%80%E7%9F%AD%E7%B5%8C%E8%B7%AF%E3%81%AE%E6%9C%AC 最短経路の本]
   * [http://www.oreilly.co.jp/books/9784873115504/ オープンソースで学ぶ社会ネットワーク分析]
 * グラフ型
   * adjacency_list ...隣接リスト
   * adjacency_matrix ... 
 * 操作
   * グラフ型への統一的な操作を提供
   * グラフ型が直接持つインタフェース(メンバ)を使うのではなく、オーバーロード可能なフリー関数を介してグラフを操作。
   * Boost.Graph のコンセプトを満たす、あらゆるグラフ型を適用可能。
     * std::vector もグラフ型として使えるよ
{{{#!c++
std::vector<Hoge> g;
proc_graph(g);
}}}
   * vertices() や edges() といった'''グラフコンセプトのフリー関数'''を、
     グラフ構造とアルゴリズムの中間インタフェースとしている。
     * STL の反復子コンセプトと対を成すもの、と考えればいい。
 * プロパティマップ
   * グラフには様々な種類のデータが付加される。
   * ex) 電車の路線図
     * 頂点 ... 駅名
     * 辺 ... 駅間の距離
     * 全体 ... 路線名
   * adjacency_list のテンプレートパラメータ
     * OutEdgeListS ... グラフの隣接構造を表すためのコンテナ
       * vecS: std::vector
       * listS: std::list
       * setS: std::set
     * VertexListS ... 頂点コンテナ
     * DirectedS ... 有向か無向か
     * VertexProperties ... 頂点
     * EdgeProperties ... 辺
     * GraphProperties ... グラフ全体
   * 取得と設定は boost::get(), boost::set() を使用。
 * 使い方いろいろ…
   * dijkstra_shortest_paths() に絞ってみていくよ
   * 最短経路を求める
   * 先行マップ
     * ある頂点の前に通る頂点を集めた辞書
     * 目的地 Z を与えると、 Z の前を通る頂点 F が取得できる。
     * 逆順の最短経路を頂点のリストとして取得できる。
{{{#!c++
std::deque<Vertex> route;
for(Vertex v  to; v != from; v = parents[v]){
	route.push_front(v);
}
route.push_front(from);
}}}
     * 先行マップは、 dijkstra_shortest_paths() に boost::predecessor_map() という関数を通して渡していた。
       * boost::predecessor_map() : 名前付き引数を使う関数。(使わないバージョンもあるけど引数やたら多くて大変)
   * 最短経路全体でどれくらいの距離があるか知りたい場合は、 distance_map を指定する。
{{{#!c++
boost::dijkstra_shortest_paths(g, from,
	boost::predecessor_map(&parents[0]).
	distance_map(&distance[0]));

int d = distance[to];
}}}
   * イベントビジター ... アルゴリズムの各ポイントで、任意の関数を呼び出せる。
{{{#!c++
struct MyVisitor : dijkstra_visitor<> {
	template <class Vertex, class Graph>
	void discover_vertex(Vertex v, const Graph&)
	{ ...event... }
};

boost::dijkstra_shortest_paths(...
}}}
     * 特定の頂点が見つかったら例外を投げて、アルゴリズムのループを脱出する。
     * 既存のアルゴリズムを使って、新たなアルゴリズムを作る。
       * dijkstra_shortest_paths() は、幅優先探索をイベントビジターでラップして作られている。
     * コルーチンでアルゴリズムを中断
     * アルゴリズム計算状況の可視化。
 * アルゴリズムの設計
   * ユーザビリティとは、その分野に精通していないユーザーにとっての公開されているアルゴリズムインタフェースのわかりやすさ。
     同時に、精通しているユーザーにとってのアルゴリズムを構成できる幅のこと。