完全2部グラフをGraphvizとPerlを使って簡単に書く方法
[追記: 2010/08/18]
id:ksmemoさんがGraphVizモジュールを使って書かれたコードの方がすっきりしているのでこちらを推奨します。
ケーズメモ, GraphVizを使ってPerlで簡単にGraphvizでグラフを書く方法, http://d.hatena.ne.jp/ksmemo/20090903/p1
CPAN, GraphViz, http://search.cpan.org/dist/GraphViz/
はじめに
「頂点数の大きな完全2部グラフを手で書くより、自動化した方がいいだろう。」
っていう動機で、
Graphvizのファイル形式である、dotを出力するためのPerlスクリプトを書きました。
Graphvizは、グラフ理論でいうグラフを簡単に描画するための便利なツールです。
導入の資料は、[1]に紹介したので参照してください。
完全2部グラフとは
2部グラフというのは、グラフの頂点集合を2つの互いに素な集合に分割してそれぞれの互いに素な集合内の頂点同士の間には辺が無いようにしてできるグラフのことです。完全2部グラフというのは、との任意の2点間に辺があるような2部グラフのことを言います。として、と表記します。
コード
#プラグマ use strict; use warnings; #頂点集合V1の基数|V1|の入力を促す。 print "Input m.: "; my $m = <STDIN>; #頂点集合V2の基数|V2|の入力を促す。 print "Input n.: "; my $n = <STDIN>; #ファイルに書き込むための変数 my $msg; my $msg2; my $msg3; #ファイルを開く。 open(FH, ">bipartite.dot"); #ヒアドキュメント使う。とりあえず、共通する部分だけ先に書いておく。 $msg = <<"EOF1"; graph G { node [shape = "circle"]; size = "7.0, 7.0"; EOF1 #カウンタ用の変数の設定 my $j1 = $m + 1; my $jn = $m + $n; #頂点の隣接関係をどんどん追記 for(my $i = 1; $i <= $m; $i++){ for(my $j = $j1 ; $j <= $jn; $j++){ $msg2.= "$i -- $j;\n"; } } #括弧で閉じる。 $msg3 = <<"EOF3"; } EOF3 #ファイルに書き込む文字列を連結。 $msg = $msg . $msg2 . $msg3; #ファイルに書き込む。 print FH $msg; #ファイルを閉じる。 close(FH); exit;