Tadachika Oki の日記

私の日々の雑感です。https://sites.google.com/site/tadachikaoki0/

完全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}と表記します。

 

参考文献

[1] Graphviz チュートリアル, http://homepage3.nifty.com/kaku-chan/graphviz/

 

サーベイに関するバイアスの話

はじめに

サーベイに関するバイアスの話をしよう。

 

昔、研究とよばれることをしていた。

大学院生の頃だろうか。

 

研究の中で重要なフェーズに、「サーベイ」というものがある。

これはざっくり言えば、

過去の関連研究に関する資料を探してきて、

きっちり研究の背景を理解したりすることだ。

 

そして、サーベイを行った結果、

自分の現在進行中の研究が関連研究とどのように違うのかを説明する材料にしたり、

新しい問題について考えたりする。

 

本題

研究をやめて、働き出して数年後、

ふとしたきっかけで、「メタ・アナリシス [丹後02]」と呼ばれる分野を知ることになった。

メタ・アナリシスとは、サーベイをして得られた、

複数の資料それぞれの主結果に関する

質のよしあし関して整理して、そこでの知見を情報処理するプロセスだ。

(ここも割とざっくりした説明なので関連書籍を読んでほしい。)

 

メタ・アナリシスの書籍 [丹後02] を読んでいると、

サーベイに関するバイアスの話が書いてあった。

僕は、このことについてほとんど存じ上げなかったので、

驚いてしまった。しかもかなりまとまっている。

 

どれくらいこういう考え方が共有されているかはわからないが、

[丹後02] を参考に、公表バイアス、英語バイアス、及び多重公表バイアスについて、

少しだけここにまとめたい。

 

・公表バイアス

ポジティブなタイプの論文 (e.g. 何かができました、何かを作りました、～であることがわかりました。というようなことを示すようなもの) は公表されやすいが、そうでないものは公表されにくい。結果、これがバイアスとなる分野がある。

 

・英語バイアス

国内外に論文を投稿するわけだが、この際に国内外それぞれにどういうタイプの論文を投稿するか ([丹後02] によれば良い結果は英語で、そうでもない場合は母国語でという分野もあるらしい) というものは分野ごとに異なる。すると、このことはバイアスになる。

 

・多重公表バイアス

良い結果が出た場合、何度も発表されたり出版機会が多くなる分野があるらしい。この場合、これもバイアスになる。

まとめ

研究から離れて、自分が行っていた「サーベイ」というものを遠くから眺めてみると、自分なりのサーベイの技法を確立したつもりだったが、まだまだ質のよい研究をするためにやるべきことがたくさんあるようだった。いつか研究を再開する日に、この周辺についてもう一度考えようと思う。

 

参考文献

[丹後02] メタ・アナリシス入門. 朝倉書店

WWW 上のマトロイド関連の資料の紹介

はじめに

WWW上で見つけたマトロイド関連の資料をご紹介します。

(この記事は、僕のはてなダイアリーに以前記載していたものを若干修正しています。)

マトロイドとは何か。

歴史は「James Oxley, WHAT IS A MATROID?」を参考に、
定義はORWikiのマトロイドの項目を参考に書きます。

歴史

マトロイドは、Whitney が1935年に「線形代数とグラフ理論の独立・従属の概念を統一的に扱うため」に導入しました。
また、同じく1935年に中澤武雄もマトロイドを見つけ出しました。
詳しくは http://atelieraterui.blogspot.jp/2010/11/7.html をご覧ください。
以後、特に、離散数学、および離散最適化の分野で長く取り扱われています。

定義

マトロイドは以下で紹介する公理系を満たすように定義されます。
公理系の例として、「独立集合族の公理」、「交換公理」、「階数関数の公理」等があります。
ここでは、この中から代表して「独立集合族の公理」を説明します。

有限集合 Nとその部分集合族 \mathcal{I}が以下の公理系を満たすとき、
(N, \mathcal{I})はマトロイドと呼ばれます。また、この公理系は「独立集合族の公理」と呼ばれます。

(I0) \emptyset \in \mathcal{I}
(I1) I \subseteq J \in \mathcal{I} \Rightarrow I \in \mathcal{I}
(I2) I, J \in \mathcal{I}, | I| < | J| \Rightarrow \exists j \in J \backslash I: I \cup \{ j \} \in \mathcal{I}

（以降、追記します。）

マトロイドの資料

入門

-室田 一雄, 線形独立性とマトロイド, http://www.misojiro.t.u-tokyo.ac.jp/~murota/lect-kisosuri/matroid041214.pdf
行列の例を用いて基族とサーキット族によるマトロイドを紹介し、いくつかの公理系についても紹介。
-藤重 悟, 劣モジュラ構造と離散凸性, http://www.kurims.kyoto-u.ac.jp/~kenkyubu/kokai-koza/H17-fujishige.pdf
マトロイド、ポリマトロイド、および劣モジュラシステムと一般化の段階を追って説明し、離散凸解析の基礎も紹介。
-James Oxley, WHAT IS A MATROID?, http://www.math.lsu.edu/~oxley/survey4.pdf
マトロイドの公理系、マトロイドの例、マトロイドの操作、マトロイドと組合せ最適化、禁止マイナー、および正則マトロイドの分解の説明。

その他関連する話題 

-谷川眞一, グラフの剛性とマトロイド, http://www.kurims.kyoto-u.ac.jp/~kenkyubu/kokai-koza/H24-tanigawa.pdf

- G, M, Ziegler, Oriented Matroids Today, http://cs.anu.edu.au/publications/eljc/Surveys/ds4.pdf
-Matroidとoriented matroid, http://pantodon.shinshu-u.ac.jp/topology/literature/matroid.html
-Matroidとoriented matroidの基本, http://pantodon.shinshu-u.ac.jp/topology/literature/matroid_basics.html

- 藤重 悟,
離散凸関数のお話,
(ファイル形式: PDF) http://www.kurims.kyoto-u.ac.jp/~fujishig/talk/OR-Hokkaido.pdf

デルタマトロイドに関する資料

デルタマトロイドは、Bouchetが1987年に、ChandrasekaranとKabadiが1988年にそれぞれ提案したマトロイドの一般化です。
マトロイドの交換公理を対称差を用いて緩めることで得られた公理を満たすように定義されます。

ジャンプシステムは、BouchetとCunninghamが1995年に提案したデルタマトロイドの一般化です。

-塩浦昭義,
ジャンプシステム上の最適化問題に対するアルゴリズム,
(ファイル形式: PDF) http://www.dais.is.tohoku.ac.jp/~shioura/talks/slides/d2007-04-14.pdf
内容: ジャンプシステム上での離散凸関数の最小化法が紹介されています。

- Andre Bouchet and Bill Jackson,
Parity Systems and the Delta-Matroid Intersection Problem,
(ファイル形式: PDF) http://www.combinatorics.org/Volume_7/PDF/v7i1r14.pdf

- Andre Bouchet, William H. Cunningham,
Delta-matroids, Jump Systems and Bisubmodular Polyhedra,
(CiteSeerX へのリンク) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.44.4680

- Ando Kazutoshi, Fujishige Satoru, Naitoh Takeshi,
A GREEDY ALGORITHM FOR MINIMIZING A SEPARABLE CONVEX FUNCTION OVER AN INTEGRAL BISUBMODULAR POLYHEDRON,
(CiNii へのリンク) http://ci.nii.ac.jp/naid/110001184398

- László Lovász, The Membership Problem in Jump Systems
(CiteSeerX へのリンク) http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.2094

- Akiyoshi, Shioura,
Neighbor Systems, Jump Systems, and Bisubmodular Polyhedra,
(ファイル形式: PDF) http://www.dais.is.tohoku.ac.jp/~shioura/papers/neighbor-system.pdf

その他

-Matroidのデータから構成できるもの, http://pantodon.shinshu-u.ac.jp/topology/literature/matroid_invariants.html
-Matroidの応用や関連した分野, http://pantodon.shinshu-u.ac.jp/topology/literature/matroid_applications.html
-様々なmatroid, http://pantodon.shinshu-u.ac.jp/topology/literature/matroid_variations.html

ORWikiから

ORWikiは、日本オペレーションズ・リサーチ学会が作成しているWikiです。
この中から、マトロイド関連の資料をご紹介します。
-マトロイド, 《マトロイド》 - ORWiki
-最小木問題, 《最小木問題》 - ORWiki
-デルタマトロイド, デルタマトロイド - ORWiki
-付値マトロイド, 付値マトロイド - ORWiki

Wikipediaから

Wikipedia, マトロイド, http://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%88%E3%83%AD%E3%82%A4%E3%83%89

 

お久しぶりです。

ツイッター等で僕をフォローしていない方々は、

お久しぶりです。 id:salmonsnare です。

 

11 ヵ月前くらいに 31 歳にしてようやく働き出し、どうにか暮らしております。

グラフアルゴリズムの研究とは随分距離を置き、

今は、エンジニア (プログラマ見習い) です。

 

社会に出てからの自身の変化で気づいたものをいくつか書いておきましょう。

 

1. コスト意識が身に着いたこと

僕は学生の頃そういう感覚がほとんどなく、ここ 1 年近くはこういう感覚をどうにか身に着けました。

2. 規則正しい生活が多少できるようになったこと

「朝起きて夜寝て、次の日確実に朝起きる。」というやつですね。

3. 自分の裁量で外食が自由に食べられるようになったこと

社会に出て 3 ヵ月、節約ばかりの学生生活を終え、ひたすら外食しました。 (おかげで一時的に太りましたが。)

 

と、こんな感じで無難な日記を書いてみました。今後は、この場に業務とは離れた学術的・技術的に興味を持ったことをに書けたらなあと思ってます。それじゃあみなさん。また。 ∩(._.)∩