有向グラフの教科書
Jørgen Bang-Jensen(http://www.imada.sdu.dk/~jbj/)と
Gregory Gutin(http://www.cs.rhul.ac.uk/~gutin/)の書いた有向グラフの教科書、
『Digraphs: Theory, Algorithms and Applications』の第一版が
Springer-Verlagの好意により、無料で読めるようです。
ファイル形式はpdfです。下記リンク先の「 the first edition of the book 」から読めます。
Digraphs: Theory, Algorithms and Applications, 2nd Edition, http://www.cs.rhul.ac.uk/books/dbook/
ざっと読んだんですが、
有向グラフのクラス、分解の方法を紹介していたり知らないことがたくさん載ってたんで勉強になりそうです。
以前紹介した(http://d.hatena.ne.jp/salmonsnare/20090313/1236942950)、
Reinhard Diestelの『Graph Theory』は無向グラフを中心に書かれているんで、
併せて読めばグラフ理論に関して広範な基礎知識を得ることができるように思います。
[追記] 目次を追記しました。 [/追記]
目次
- Basic Terminology, Notation and Results（基本用語、記法等）
- Distances（頂点間の距離を算出するアルゴリズム等)
- Flows in Networks（ネットワークフロー）
- Classes of Digraphs（有向グラフのクラス）
- Hamiltonicity and Related Problems（ハミルトン性と関連問題）
- Hamiltonian Refinements
- Global Connectivity（有向グラフの点連結度、辺連結度について）
- Orientations of Graphs（グラフの向き付け（無向グラフの辺に向きをつけて有向グラフにすること）について）
- Disjoint Paths and Trees（互いに素なパスと木）
- Cycle Structure of Digraphs（サイクル構造と有向グラフ）
- Generalizations of Digraphs（有向グラフの一般化）
- Additional Topics（追加トピック）
PerlモジュールAlgorithm::Line::Bresenhamを使ってtgifの円を円状に配置
はじめに
前回は、Algorithm::Line::Bresenhamの紹介をしたんですが、
「Perlで、グラフをtgifの形式(objファイル)で生成してepsで出力したい。」
という目的がありました。
問題設定を具体的にして、以下のようにしました。
「完全グラフをPerlを使って生成してeps出力したい。」
ということで、
今回は、Algorithm::Line::Bresenhamを使ってtgifの円を円状に配置する方法を考えたのでご紹介します。
完全グラフを生成するためには、辺を全ての頂点間につなぐ必要があるのですがそれは次回に持ち越します。
予備知識
まず、tgifのobjがどのような形式なのか調べる必要がありました。[1]を参考にしたところtgifの仕様は「tgif.pl」というPrologのプログラムで書かれていることを知りました。ただ、僕はPrologに関する知識がほとんどなかったので、円を描画するのに必要な座標の設定がどのようになされているのかを、tgif.plを見ながら学びました。[2]を参考にしました。以下がtgifのovalオブジェクト（楕円）の定義です。
tgif_oval(Obj) :- current_predicate(tgif_file_version,tgif_file_version(_)), tgif_file_version(FileVersion), FileVersion =< 7, !, ( var(Obj) -> OutputObj = true ; OutputObj = false ), Obj = oval(_Color,_LeftTopX,_LeftTopY,_RightBotX,_RightBotY,_ObjFill, _LineWidth,_PenPat), ( OutputObj == true -> call(Obj) ; true ).
コードを書くときに注意した点
「_LeftTopX,_LeftTopY,_RightBotX,_RightBotY」が楕円の座標と、楕円を円にするために必要なパラメータだと判断したので、これらをPerlのヒアドキュメントを用いて座標を円状に配置しました。このときに、Algorithm::Line::Bresenhamで算出した値を用いました。
コード
use strict; use warnings; use Algorithm::Line::Bresenham qw/circle/; use Data::Dumper; my $y = 10; my $x = 10; my $radius = 5; my @points = circle ($x, $y, $radius); open(FH, ">test.obj"); my $msg = <<"EOF"; %TGIF 4.2.1 state(1,37,10.000,0,0,0,16,0,9,1,1,1,0,0,2,1,0,'Times-Roman',0,195840,0,0,1,50,0,0,1,1,0,16,0,0,1,1,1,1,1497,1056,1,17280,2880,0). % % @(#)\$Header\$ % %W% % unit("1 pixel/pixel"). color_info(13,65535,0,[ "magenta", 65535, 0, 65535, 65535, 0, 65535, 1, "red", 65535, 0, 0, 65535, 0, 0, 1, "green", 0, 65535, 0, 0, 65535, 0, 1, "blue", 0, 0, 65535, 0, 0, 65535, 1, "yellow", 65535, 65535, 0, 65535, 65535, 0, 1, "pink", 65535, 49344, 52171, 65535, 49344, 52171, 1, "cyan", 0, 65535, 65535, 0, 65535, 65535, 1, "CadetBlue", 24415, 40606, 41120, 24415, 40606, 41120, 1, "white", 65535, 65535, 65535, 65535, 65535, 65535, 1, "black", 0, 0, 0, 0, 0, 0, 1, "DarkSlateGray", 12079, 20303, 20303, 12079, 20303, 20303, 1, "khaki", 61680, 59110, 35980, 61680, 59110, 35980, 1, "NavyBlue", 0, 0, 32896, 0, 0, 32896, 1 ]). script_frac("0.6"). fg_bg_colors('black','white'). dont_reencode("FFDingbests:ZapfDingbats"). objshadow_info('#c0c0c0',2,2). rotate_pivot(0,0,0,0). spline_tightness(1). page(1,"",1,''). EOF foreach my $point (@points) { my ($px, $py) = ($point->[0] * 50, $point->[1] * 50); my $px2 = $px + 49; my $py2= $py + 46; $msg.= "oval('black','',$px,$py,$px2,$py2,0,2,1,1634,0,0,0,0,0,'2',0,[\n]).\n"; } $msg.= "\n"; print FH $msg; close(FH); exit;
出力されたtest.objの中身
%TGIF 4.2.1 state(1,37,10.000,0,0,0,16,0,9,1,1,1,0,0,2,1,0,'Times-Roman',0,195840,0,0,1,50,0,0,1,1,0,16,0,0,1,1,1,1,1497,1056,1,17280,2880,0). % % @(#)$Header$ % %W% % unit("1 pixel/pixel"). color_info(13,65535,0,[ "magenta", 65535, 0, 65535, 65535, 0, 65535, 1, "red", 65535, 0, 0, 65535, 0, 0, 1, "green", 0, 65535, 0, 0, 65535, 0, 1, "blue", 0, 0, 65535, 0, 0, 65535, 1, "yellow", 65535, 65535, 0, 65535, 65535, 0, 1, "pink", 65535, 49344, 52171, 65535, 49344, 52171, 1, "cyan", 0, 65535, 65535, 0, 65535, 65535, 1, "CadetBlue", 24415, 40606, 41120, 24415, 40606, 41120, 1, "white", 65535, 65535, 65535, 65535, 65535, 65535, 1, "black", 0, 0, 0, 0, 0, 0, 1, "DarkSlateGray", 12079, 20303, 20303, 12079, 20303, 20303, 1, "khaki", 61680, 59110, 35980, 61680, 59110, 35980, 1, "NavyBlue", 0, 0, 32896, 0, 0, 32896, 1 ]). script_frac("0.6"). fg_bg_colors('black','white'). dont_reencode("FFDingbests:ZapfDingbats"). objshadow_info('#c0c0c0',2,2). rotate_pivot(0,0,0,0). spline_tightness(1). page(1,"",1,''). oval('black','',750,500,799,546,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',750,500,799,546,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',250,500,299,546,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',250,500,299,546,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',500,750,549,796,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',500,250,549,296,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',500,750,549,796,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',500,250,549,296,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',750,550,799,596,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',750,450,799,496,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',250,550,299,596,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',250,450,299,496,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',550,750,599,796,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',550,250,599,296,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',450,750,499,796,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',450,250,499,296,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',750,600,799,646,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',750,400,799,446,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',250,600,299,646,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',250,400,299,446,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',600,750,649,796,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',600,250,649,296,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',400,750,449,796,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',400,250,449,296,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',700,650,749,696,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',700,350,749,396,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',300,650,349,696,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',300,350,349,396,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',650,700,699,746,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',650,300,699,346,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',350,700,399,746,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',350,300,399,346,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',650,700,699,746,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',650,300,699,346,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',350,700,399,746,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',350,300,399,346,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',700,650,749,696,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',700,350,749,396,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',300,650,349,696,0,2,1,1634,0,0,0,0,0,'2',0,[ ]). oval('black','',300,350,349,396,0,2,1,1634,0,0,0,0,0,'2',0,[ ]).
まとめ
きれいな円を描くためには、$x, $y, $radius, $px, $pyのさじ加減が難しいです。
とりあえず、円状の円の配置は成功したので辺を全ての頂点間につなぐステップに入ろうと思います。
また、座標パラメータが操作できるテキストファイルの画像ファイルにおいて、その中のオブジェクトはPerlを使って細かく操作できることを実感しました。
参考文献
- Tgif FAQ - Tgif File Format, http://bourbon.usc.edu:8001/tgif/faq/format.html
- Google Code Search, tgif.pl, http://www.google.co.jp/codesearch/p?hl=ja&sa=N&cd=1&ct=rc#A_7OrYkIV6Q/tgif.pl&q=tgif.pl%20lang:Prolog
Algorithm::Line::Bresenham
はじめに
Perlで円を描きたかったんですが、ディスプレイに「円」を描くときにドットで近似するわけですけどもその具体的なアルゴリズムを全然知らなかったんです。そこで、調べたら「ブレセンハムのアルゴリズム」を知りました。CPANにあがっているか探してたらあったんでここで紹介します。
実装する上で僕がつまずいた点
配列の仕組みを僕が良く分かってなくって、そのままアウトプットしたら、「ARRAY(数値)」の形式でだーって画面に出てきたんでこれはまずい。ということで、策を探しました。どうやら、下記コードの@pointsが多重配列になっていて取り出し方が分かってなかったということでした。
コード
use strict; use warnings; use Algorithm::Line::Bresenham qw/circle/; my $y = 10; my $x = 10; my $radius = 10; my @points = circle ($x, $y, $radius); foreach my $point (@points) { my ($px, $py) = ($point->[0], $point->[1]); print "\[$px, $py\]"; }
出力
[20, 10][20, 10][0, 10][0, 10][10, 20][10, 0][10, 20][10, 0][20, 11][20, 9][0, 11][0, 9][11, 20][11, 0][9, 20][9, 0][20, 12][20, 8][0, 12][0, 8][12, 20][12, 0][8, 20][8, 0][20, 13][20, 7][0, 13][0, 7][13, 20][13, 0][7, 20][7, 0][19, 14][19, 6][1, 14][1, 6][14, 19][14, 1][6, 19][6, 1][19, 15][19, 5][1, 15][1, 5][15, 19][15, 1][5, 19][5, 1][18, 16][18, 4][2, 16][2, 4][16, 18][16, 2][4, 18][4, 2][17, 17][17, 3][3, 17][3, 3][17, 17][17, 3][3, 17][3, 3]
まとめ
まだ、具体的にプロットしてpng等に出力してないですが、とりあえず値を求めるのは終了しました。
参考文献
- Algorithm::Line::Bresenham - search.cpan.org, http://search.cpan.org/~osfameron/Algorithm-Line-Bresenham-0.11/lib/Algorithm/Line/Bresenham.pm
C言語で完全グラフの頂点対のリストの生成器を書いた
はじめに
完全グラフの頂点対のリストを自動生成する方法を、先日から考えているGraphviz用のdotファイルの生成を応用して考えた。
コード
/* Graph Generator */ #include <stdio.h> int main(void) { /* 変数の宣言 */ int i, j, n; FILE *fp; /* 完全グラフのnの入力を促す。 */ printf("Please input n:\n"); scanf("%d", &n); /* ファイルに書き込む。 */ fp = fopen ("data", "w"); /* 頂点の総数、辺の総数を書き込む */ for(i = 1; i <= 2; i++) fprintf(fp, "%d\n", n); /* 頂点の隣接関係をどんどん書き込む */ for(i = 1; i <= n; i++){ for(j = i; j <= n; j++){ if(i != j){ fprintf(fp, "%d %d\n", i, j); } } } fclose(fp); return 0; }
実行結果(生成されたファイル data の中身)
nが5のときの実行結果。
5
5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
完全グラフをGraphvizとPerlを使って書く方法
はじめに
前回は、完全2部グラフについて書いたんですが、今回は完全グラフについて書きました。[1]の和訳をこの前購入したんですが、
気に入った箇所があったので引用します。
あたらしい結果がもたらす光明を見逃さず、そこで用いられた手続をくりかえして利用すべきである。成功を探れ！その結果を、または方法を他の問題に利用できないか。
そこで、問いを変形して完全グラフの場合を考えることにしました。
ここで、ポイントとなるのが、「頂点の隣接関係の追記」の部分だけ変更すれば良いということです。
それ以外は、前回のコードをそのまま利用すればよいのです。
ここで私が書いたことを、応用して、
- 任意の長さのパス
- 任意の長さのサイクル
- 任意の星グラフ
を生成するコードをサブルーチンの形で書いてもいいと思います。
完全グラフとは
完全グラフというのは、グラフの頂点集合
の任意の2点間に辺があるようなグラフのことを言います。
として、
と表記します。
コード
use strict; use warnings; print "Input n.: "; my $n = <STDIN>; my $msg; my $msg2; open(FH, ">graph.dot"); $msg = <<"EOF1"; graph G { node [shape = "circle"]; size = "7.0, 7.0"; EOF1 #頂点の隣接関係をどんどん追記。 for(my $i = 1; $i <= $n; $i++){ for(my $j = $i; $j <= $n; $j++){ if($i != $j){ $msg2.= "$i -- $j;\n"; } } } $msg = $msg . $msg2 . "}"; print FH $msg; close(FH); exit;
Graphvizで完全グラフ
を描画した例
参考文献
- G. Polya, How to Solve It
完全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;
Graphvizで完全2部グラフ
を描画した例
自分の泳ぐ海を決めるということ
数年前から並々ならぬ野心があって、
必死に分不相応なサーベイをしてたんだけども。
よくよく考えてたら、自分のレディネス（学習準備性）を超えたことを調べてて
肝心なことがおろそかになっていた。
フィールドの違う人間を比較したところであんまり意味が無いのに。
僕はインターネットという「情報の洪水」を知り、10年経つ。
使い初めたのは、高2くらいからかな。
だんだん、世の中に凄い人がたくさんいることを知って、井の中の蛙になることはなかった。
だけど、
気づいたら、サーベイするときの探索空間がとんでもないことになってて、
「ああ、こりゃまずいわ。」
と思って探索空間の枝狩りを始めた。大分スッキリした。
そして、今の自分の泳ぐ「海」がようやく見えてきた。
もう、泳がなくていい海は泳ぐことはないだろう。
泳ぐ準備運動から、再びやりなおしだ。
