完全2部グラフをGraphvizとPerlを使って簡単に書く方法 [修正版]

6 年前に私が書いた「はてなダイアリー」の記事から有用そうな記事を、修正・追記した記事です。

[追記: 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 点の関係 (以下、辺) の集まり (以下、辺集合) を表現した数学的な構造としてグラフとよばれるものがある。グラフは、紙に書いたり可視化をするソフトウェア (e.g Graphviz 等) を用いることで視覚的に表現できる。

点集合を 2 分割したとき、同一分割内に辺が存在しない種類のグラフを 2 部グラフ とよぶ。また、 2 部グラフであり、すべての頂点の間に辺があるグラフを完全 2 部グラフ (※1) とよびます。

[動機]

頂点集合のサイズが大きい完全 2 部グラフを紙に手動で書くことは労力がかかるので自動化したいことです。

[技術による解決]

Graphvizのファイル形式である、dotを出力するためのPerl スクリプトを書きました。

Graphvizはグラフを簡単に描画するための便利なツールです。

導入の資料は [1] に紹介したのでご参照ください。

コード

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;

Graphvizで完全2部グラフを描画した例

まとめ

完全 2 部グラフの描画を Perl と Graphviz で自動化する方法について記述しました。応用して、完全 k 部グラフの記述や、このコードを他のスクリプト言語に翻訳することも考えられます。

※1 完全 2 部グラフのもう少し厳密な定義と記法について記述します。 2 部グラフというのは、グラフ $G=(V, E)$ の頂点集合 $V$ を2つの互いに素な集合 $V_1, V_2$ に分割してそれぞれの互いに素な集合内の頂点同士の間には辺が無いようにしてできるグラフのことです。完全2部グラフというのは、 $V_1$ と $V_2$ の任意の2点間に辺があるような2部グラフのことを言います。 $|V_1|=m, |V_2|=n$ として、 $K_{m,n}$ と表記します。