スモールワールドとは、ノードからほかのあらゆるノードにできるだけ早く到達できるようにするために、「各ノードがランダムなN本のノードとつながっている」という状態にしたグラフのことを言います。
厳密な特徴は以下のような専門記事を読んでいただくとして、
スモールワールド - @IT
スモールワールドネットワーク（small world network）
Boost.Graphにはスモールワールドグラフを生成するboost::small_world_iteratorというジェネレータクラスが用意されています。
以下は、20頂点を持つグラフで、各頂点がランダムな6頂点と接続されているスモールワールドを作っています。
- 第1引数：乱数生成エンジンへの参照
- 第2引数：頂点数
- 第3引数：接続する頂点数
- 第4引数：辺をランダムに異なる頂点に再配線する確率(デフォルトでは0。1.0が最高)
- 第5引数：自己ループを許可するかどうか(デフォルトではfalse)
#include <fstream> #include <boost/graph/adjacency_list.hpp> #include <boost/graph/small_world_generator.hpp> #include <boost/graph/graphviz.hpp> #include <boost/random/linear_congruential.hpp> typedef boost::adjacency_list<> Graph; typedef boost::small_world_iterator<boost::minstd_rand, Graph> SWGen; int main() { boost::minstd_rand gen; Graph g(SWGen(gen, 20, 6, 0.1), SWGen(), 20); std::ofstream file("test.dot"); boost::write_graphviz(file, g); }
これは、以下のようなグラフを生成します：
参照：
small_world_iterator - Boost Graph Library
Boost 1.52.0のドキュメントで確率のデフォルト引数が記載されていなかったので、バグ報告して修正してもらいました。1.53.0から記載されると思います。
https://svn.boost.org/trac/boost/ticket/7771
