グラフのデータを作成するプログラム「Rudy」

グラフのデータを作成するプログラム「Rudy」を紹介します。

Stanford大学のStefan E. Karischさんが作成したプログラムで、Stanford大学のウェブサイトからダウンロードできます。gb_lib.cとrudy.cをダウンロードすればOKです。

readmeに書いてあるように、以下でコンパイルできます。

$ gcc gb_lib.c rudy.c -lm -o rudy

rudyは色々なグラフのデータを作成できます。

以下は、ノード数5の完全グラフを作成する例です (完全グラフとは、全てのノード(vertex)が、全てのノードとつながっている(辺を持つ)グラフのこと)。

$ ./rudy -clique 5
5 10
1 5 4
1 4 3
1 3 2
1 2 1
2 5 3
2 4 2
2 3 1
3 5 2
3 4 1
4 5 1

一行目はノード数とエッジ数です。二行目以降は、[ノードID　ノードID　エッジの重み]です。ノードIDは1始まりです(0始まりではない)。エッジの重みの最大値は、(ノード数 - 1)で決まります。

以下は、ノード数5の平面グラフを作成する例です (平面グラフとは、辺(エッジ)同士が交差しないグラフのこと)。

$ ./rudy -planar 5 40 3.1415
5 4
1 4 1
1 3 1
2 5 1
3 4 1

40というのは、グラフの密度です。0～100で指定できます。密度が大きいほど、エッジの数が増えます。3.1415というのは、乱数のシード(seed)です。たぶん、適当に指定しても大丈夫です（笑

以下はランダムグラフを作成する例です。

$ ./rudy -rnd_graph 5 60 42221
5 5
1 3 1
1 2 1
2 4 1
3 5 1
4 5 1

引数の意味は、平面グラフのときと同じです(ノード数、密度、シード)。