仕事でアルゴリズムを考える機会があった.生徒のうち互いに兄弟であることを登録する機能を作っている.たとえば,AさんとBさんが兄弟であることをA⇔Bと表す.A⇔BとA⇔Cを登録したとき,自動でB⇔Cを登録できれば便利である.そのとき使うアルゴリズムを「ケビン=ベーコン クエリ」という.「6次の隔たり」で有名なケビン=ベーコンである.
N人兄弟のクリークを家族Fとよぶ.FのメンバーそれぞれにN-1人の兄弟がいる.グラフで書くと,FのノードがそれぞれN-1本のエッジを重複なく持つとき,Fは完全グラフになる.家族Fの値が分かれば,兄弟の数はN-1人とすぐにわかる.これを利用してケビン=ベーコンクエリを考えてみたが,うまくいかなかった.グループG1に兄弟のメンバーN1,N2…を登録したとき,互いをグループIDで認識する仕組みに落ち着いた(この仕組みはDB更新が高頻度で必要なので採用しなかった).
その代わり,buoy法なるものを考案した.buoyとはブイすなわち「浮き」である.Aさんで登録してある兄弟数をA=count(A)と書く.BさんはB=count(B)個登録されてある.浮きは兄弟数の最大値Y=max{A,B,C..}である.この浮きが「水位」によって増加するところがbuoyの由来である.アルゴリズムは,
for(from A){
if(Y>A){A to B}
elseif(Y=A){endif}
}
3人兄弟の場合,次の図のようになる.

4人兄弟のときは以下である.

つまり,buoyの最大値はN-1に過ぎないため,兄弟数を求めるにはbuoy法は最適な方法でもない.現在兄弟数を,家族Fが完全グラフであれば全兄弟登録済,完全グラフでなければ未登録兄弟ありとして開発している最中である.
