LEDA_1stStep

LEDA 速習
クイック
・スタート
クイック・
〔
グラフとアルゴリズムの完全理解
C++ 入門書(独習用)としても活用
〕
住商エレクトロニクス(株)
目次
第１章
LEDA について ....................... 1
1.1 概要 と 動作環境 ....................................................... 1
■１■ LEDA とは …… .......................................................................... 1
■２■ LEDA の目標 …… ........................................................................ 1
■３■ LEDA の特徴 …… ........................................................................ 1
■４■ LEDA の動作環境 …… .................................................................... 2
1.2 最も簡単な例題 ......................................................... 2
■ 1 ■ データの入出力 .......................................................................... 2
■ 2 ■ オブジェクト描画用のウィンドウ .......................................................... 3
■ 3 ■ オブジェクトとは？ ...................................................................... 4
1.3 ウィンドウについて ..................................................... 4
第２章
基本 と データ構造 .................. 5
2.1 無限桁数の整数 ......................................................... 5
2.2 有理数 ................................................................. 5
2.3 REAL による任意精度の計算 (√、π) ..................................... 6
■１■
17 を１万桁まで計算する .............................................................. 6
■２■ πを１万桁まで計算する .................................................................. 6
2.4 辞書型配列 (柔軟な疎配列) .............................................. 7
■１■ 辞書型配列とは .......................................................................... 7
■２■ 辞書型配列の応用例（電話帳）............................................................. 7
2.5 スタック／キュー／リスト −その応用 (迷路脱出) ......................... 8
■１■ Stack / Queue ........................................................................... 8
■２■ 優先順位付き Queue − PQueue<p, i>(PriorityQueue) ......................................... 8
■３■ 連結リスト構造（双方向）− List .......................................................... 8
■３■ PQueue の応用 ........................................................................... 9
■４■ Stack ／ Queue の応用（迷路の経路探索）................................................... 9
第３章
グラフ と アルゴリズム ............. 11
3.1 グラフとは (パラメータ付グラフ、Static グラフ) ......................... 11
3.2 グラフの基本性質 ...................................................... 11
■１■ グラフのプロパティ ..................................................................... 11
■２■ グラフの構造 ........................................................................... 12
■３■ グラフ・アルゴリズム ................................................................... 12
3.3 グラフの応用 .......................................................... 13
■１■ 伝送障害シミュレーション ............................................................... 13
■２■ トポロジカル・ソート ................................................................... 13
■３■ プロジェクト管理 ....................................................................... 14
3. ４ 最短経路探索−その応用 (駅スパート) .................................. 14
■１■ 基準点から各ノードへの最短経路 ......................................................... 14
■２■ 駅スパートへの応用 ..................................................................... 15
3. ５ 最大フロー (油田のパイプライン問題) .................................. 16
第４章
幾何データの扱い ................... 17
4.1 幾何オブジェクトの表現 (点､線､円､多角形、) ............................. 17
■１■
■２■
4.2
4.3
4.4
4.5
点／線分オブジェクト .................................................................. 17
円／多角形オブジェクト ................................................................ 17
幾何図形間の関係 ......................................................
幾何の応用−正ｎ角形の作図 ............................................
幾何の厳密な計算 (有理数カーネル) .....................................
一般ポリゴン (穴明き多角形) の計算 ....................................
17
19
20
20
第５章
LEDA での日本語の扱い .............. 22
5.1
5.2
5.3
5.3
グラフ・エディタ で グラフ を作成 .....................................
プログラム で グラフ を作成 ...........................................
メッセージ を ウィンドウ に書く .......................................
GUI メニュー を 作成 ..................................................
22
22
23
24
第６章
ｙ Files の概要 .................... 26
6.1 yFiles のインストール ................................................ 26
■１■
■２■
Java のインストール ................................................................... 26
yFiles の解凍 と コピー ............................................................... 26
■３■
yFiles の実行 ......................................................................... 26
6.2 yFiles の デモ・アプリ の起動 と 使い方 .............................. 26
■１■ animated algorithm の デモ ............................................................ 26
■２■ visual programming の デモ ............................................................ 28
■３■ UML エディターのデモ .................................................................... 30
6.3 yFiles の サンプル・ソース の 実行 ................................... 31
■１■ GraphDemo の実行 ....................................................................... 31
■２■ ListDemo の実行 ........................................................................ 31
■３■ ShortestPath の実行 .................................................................... 31
6.4 yFiles の 概要 について .............................................. 32
■１■ yFiles とは ............................................................................. 32
■２■ yFiles について ......................................................................... 32
■３■ yFiles の特徴 ........................................................................... 32
■４■ yFiles の特徴 ........................................................................... 32
■５■ yFiles のメリット ....................................................................... 33
■６■ 使用例 ................................................................................. 33
■７■ 基本コンポーネント ..................................................................... 33
■８■ ビュワー（可視化）コンポーネント ....................................................... 33
■９■ レイアウト（配置）コンポーネント ....................................................... 33
6.5 yFiles の 活用事例 ................................................... 36
■１■
■２■
WEB ショッピングの傾向分析 ............................................................. 36
WEB サーバー上のグラフ・アプリをブラウザより利用 ....................................... 36
■３■
マセマティカよりグラフ機能を活用 ...................................................... 37
第７章
ＬＥＤＡ の 発展 ................... 38
7.1 多くのユニークな追加モジュール群 ...................................... 38
■１■ AGD（version 1.2） < レイアウト・マネージャ > ............................................
■２■ CGAL(version 2.3) < 高機能・幾何図形アルゴリズム > .....................................
■３■ BALL(1.0 beta) < 分子モデル開発・検証用アルゴリズム > ..................................
■４■ yFiles(version 2.1) < グラフ・アルゴリズム＋レイアウト・マネージャ > ...................
■５■ LEDAGraphAlgo(version 1.0) < グラフ・アルゴリズム > ....................................
■６■ yWays(version 1.0) < バイオケミカル（分子モデル）用の可視化ライブラリ > ................
38
38
38
38
38
38
7.2 レイアウト・マネージャを使う .......................................... 39
■１■
■２■
直交レイアウト ........................................................................ 39
階層レイアウト ........................................................................ 40
第８章
ＬＥＤＡ の インストール ........... 41
8.1
8.2
8.3
8.4
Windows 環境（Microsoft VC++）..........................................
Windows 環境（Borland BCC）.............................................
Windows 環境（Cygwin g++）..............................................
Linux / Unix 環境 ......................................................
41
42
45
45
第１章
LEDA について
この解説書「LEDA速習 −クイック・スタート−」については、別途 サイエンス社から発行されている「LEDA
で始める C/C++ プログラミング −入門からコンピュター・ジオメトリまで−」
（浅野哲夫・小保方幸次＝
共著）と一緒に読まれるととをお勧めします。
「LEDA で始める ..」では、グラフ理論や幾何アルゴリズムの
理論的背景が詳しく、かつ分かり易く説明されています。
「LEDA 速習 ..」では、LEDA が適応され得る種々
の事例の紹介や豊富なサンプルについての操作を通して、
グラフ理論や幾何アルゴリズムについて体験して
頂くのに重点を置いています。サンプルは、LEDA：version-4.2.1 に基づいていますが、再コンパイルす
れば LEDA：version-4.4 でも動作します。また、別冊「LEDA 速習 ＝デモ・サンプルの操作＝」をも共に
参照して下さい。
1.1 概要 と 動作環境
■１■ LEDA とは ……
LEDA は、ドイツのザールブリュッケンにあるマックスプランク研究所で開発されたソフトウェアで、
”Library of Efficient Data types and Algorithms” の各ワードの頭文字を取ったものです。LEDA は、
「アルゴリズム ＋ LEDA ＝ プログラム」の実現を目指したソフトウェア・ライブラリですが、単なるラ
イブラリでなく、新たな高級言語とも見なすことができるもので、世界中の関心を集めています。
LEDA は人工的な名前ですが、英語辞典を引くと、
「ギリシア神話に登場するレダ（LEDA）をテーマとして
いる。 [ギリシア神話] レダはスパルタの王妃で、白鳥の姿をしたゼウスと交わり、 絶世の美女であるヘ
レネを生んだ。. 」とあります。参考文献の ”LEDA Book”(*1) の表紙には、白鳥とその女性の絵が描か
*1 Title: •u
LEDA: A platform for combinatorial and geometric computing•v
れています。
Author: K.Mehlhorn & Stefan Naher, Cambridge University Press, 1999.
■２■ LEDA の目標 ……
アルゴリズムに対する問題点としては、次の３つが良く指摘されます。
・アルゴリズムは難解で、解析が難しい
・アルゴリズムの記述は簡単だが、コード化は難しい
・データ構造については、さらに、コード化は困難
ＬＥＤＡの目標（開発意図）としては、上記の問題点を克服するため、以下の５つが挙げられます。
・擬似言語によるアルゴリズムの記述とプログラムのギャップを埋めること。
擬似言語のような書き方もできること。
・できるだけ多くのアルゴリズムをクラス（Ｏｂｊｅｃｔ）の形で提供
・様々なデータ・タイプを提供
・代表的なデータ・タイプを使いやすい形で提供
・計算誤差に影響されないこと。
■３■ LEDA の特徴 ……
・Ｃ ++ のクラス・ライブラリ であり、殆どのコンパイラが使える
・直感的に、プログラムが書けるように工夫されている
・豊富なデータ・タイプと制御構造 が提供されている
分かりやすいプログラム（アルゴリズム記述との差が少ない）
・様々なデータ構造 が用意されている（List,PQueue,D_array)
・代表的なアルゴリズム は クラスとして利用可能（最短経路 ,)
- 1 -
・高機能ＧＵＩが種々のウィンドウ（グラフィック・ウィンドウ、グラフ・ウィンドウ、幾何ウィンドウ）
で利用可能です。
・頑強性： 万全の計算誤差対策が配慮されています。例えば、 桁数制限なしの整数型（Integer）,有理数
型（Rational）が用意されています。
・高信頼性： バグのない成熟したソフトウェアです。
・高効率： コードが洗練されているので、容易に高速化が可能です。
■４■ LEDA の動作環境 ……
以下に示すように、殆どのマシンとコンパイラの環境で動作します。
マシン
SGI (Silicon Graphics)
SUN Sparc
ＯＳ
IRIX64
SunOS, Solaris
コンパイラ
CC-7.3, g++(2.95, 3.1)
SunPRO 5.2, 5.3 (Forte 6)
g++(2.95, 3.1, 3.2)
aCC-03.33
cxx(6.2, 6.5)
Hewlett Packard
DEC
HP-UX 11
OSF1(Tru64-5.1, 5.1A)
80x86, Pentium
80x86, Pentium
Solaris
Linux
80x86, Pentium
MS Windows NT/2000
MS Windows 95/98, XP
g++(2.95.x, 3.0.1)
g++(2.95, 2.96, 3.1, 3.2)
INTEL C++ 5.0.1
MS Visual C++ (6.0,7.0, .NET)
Borland C++(bcc32 5.5.1, 5.6)
80x86, Pentium
NEC SX-5, SX-6
Cygwin
SUPER-UX 11.1
g++(2.95, 3.1, 3.2)
c++ SX 1.0
1.2 最も簡単な例題
本マニュアルに示すサンプルの大半は、別途配布します”LEDA セミ
ナー CD-ROM”に ソース・ファイルと実行ファイルを収録しています
ので、ご参考にして下さい。
また、LEDA-4.4 以降では、ソース･ファイルの始めに次の１行が必要
です。その１行が抜けているサンプルには追加して下さい。
using namespace leda; //LEDA-4.4 用
#include <LEDA/window.h>
using namespace leda; //LEDA-4.4用
void main(){
list<polygon> pl;
ifstream fin(
“myfile”
);
window W(600,600); W.display();
■ 1 ■ データの入出力
#include <LEDA/window.h>
using namespace leda; //LEDA-4.4用
int main(){
ofstream fout("myfile");
window W(600,600);
W.display();
fin >> pl; W << pl; ...ファイル入力
...`Welcome`を表示
↑リスト-1.2.1
”myfile”の内容
(2.16614, 66.1505) (7.33154,33.9917)
(11.3306,33.9917) (14.9963,54.3201)
(38.8239,56.3196) (27.9932,56.3196)
}
list<polygon> pl; polygon p;
while(W>>p){ W<<p; pl.push_back(p); }
//W >> pl;
fout << pl;
}
W.read_mouse();
W.close();
return 0;
リスト-1.2.2
データの作成
各種入出力のコーディングが簡易で洗練されている。
右の例題では、
”Welcome”の文字が複数個のポリゴン
(多角形) の外形で形づくられている。
”myfile”は、ポ
リゴン・データ ファイルです。
”myfile”から複数の
- 2 -
ポリゴン・データをメモリー (pl：ポリゴン・リスト) に取込み、ウィンドウ・オブジェクト (W) に出
力 (描画) している。
ファイル出力は、 ofstream fout(”myout”
);
参考までに、標準入出力は、
fout << pl;
cin >> x; cout << x;
また、ポリゴン・データ ファイルを作成するためのプログラムを リスト -1.2.2 に示します。
リスト -1.2.2 を実行すると、キャンバスが現れますので、まず ‘W’ を一筆書きで書き、右クリックし
て‘W’の形を閉じて１つのポリゴン（凹多角形）を作成します。
次に、E, L, C, O, M, E を順に書いて、最後に右クリックす
#include <LEDA/stream.h>
using namespace leda; //LEDA-4.4用
int main(){
int x, sum=0;
ifstream fin("filein.dat");
ofstream fout("fileout.dat");
while(fin>>x)
fout<<sum;
return 0;
sum+=x;
}
リスト -1.2.3
ファイル入出力
ると（最後は‘E’を閉じるための右クリックと合わせて、2
回連続して右クリックします）
、W>>P のループから脱出しま
す。fout<<pl でファイルに出力します。
次に、ディスク上のデータ・ファイルに対する入出力のサン
プルを リスト -1.2.3 に示します。
以下に、サンプルの実行結果を示します。
> cat filein.dat
// 入力ファイルの内容
1 2 3 4 5 6 7 8 9 10
> ./app
> cat fileout.dat
// 出力ファイルの内容
55
リスト -1.2.1、リスト -1.2.2 のソース・ファイルは、”LEDA セミナー CD-ROM”の
Leda1¥Leda_src¥Source¥Seminar¥new_geo¥welcome.c にあります。また、操作方法については、別冊「＝
デモ・サンプルの操作＝」の P2.「■ 1 ■ P5: C++ 言語と LEDA」にあります。
■ 2 ■ オブジェクト描画用のウィンドウ
リスト -1.2.4 に、点、線、円などの基本オブジェクトを、ウィンドウに次々とマウスから入力して、描
画するサンプルを示します。
まず、ウィンドウ・オブジェクト(W)と幾何の基本オブジェクトの”点”を生成する。
window W(400,400);
point p;
次に、左マウス･ボタンでウィンドウ・オブジェクト(W) 上に、点
を入力し (W >>p)、
その点を ウィンドウ上に描画する (p >>W)。
右マウスをクリックすると、点入力を終了する。同様にして、線分
(s)、円(c)、多角形(P)を入力して描画する。多角形の入力方法は、
左マウスで順に多角形の頂点を入力し、最後に右クリックして多角
形を閉じる。
最終ステップの”W.read_mouse()”は、マウスからの何らかの入力
を待ち続ける。このステップがないと、複数個の多角形を入力し
た直後にウィンドウを閉じてしまい、ウィンドウ上の図形を表示
し続けられない。
↓リスト -1.2.4
point p; while(W
segment s; while(W
circle c; while(W
polygon P; while(W
W.read_mouse();
}
- 3 -
↑実行結果
#include <LEDA/window.h>
void main(){
window W(400,400); W.display();
>>
>>
>>
>>
p)
s)
c)
P)
W
W
W
W
<<
<<
<<
<<
p;
s;
c;
P;
■ 3 ■ オブジェクトとは？
簡単なオブジェクトの例を以下に示します。
class Counter{
// オブジェクトの宣言
int Cnt;
// オブジェクト変数
public:
// コンストラクター
Counter( ){ Cnt=0;
}
int main( ){
Counter Cnt1, Cnt2;
// オブジェクトの生成
for(int i=0; i<10; i++){
// オブジェクト操作の実行
Cnt1.Inc();
// ３つのメソッド
// オブジェクト変数に対する操作
void Inc ( ) { if(Cnt< 999) Cnt++; }
void Dec ( ) { if(Cnt>0)
int
Val( ) { return Cnt;
Cnt2.Inc();
}
// オブジェクト操作の実行
for(i=0; i<5; i++)
Cnt--; }
}
Cnt2.Dec();
// オブジェクト変数の取出
cout<<“1:”<Cnt1.Val()<<endl;
};
上記は、Counter オブジェクトのクラス定義です。
オブジェクト内に、カウント値を保持するための変数
Cnt があり、次の３つの Method があります。
Inc() … １だけカウント・アップする
}
cout<<“2:”<Cnt2.Val()<<endl;
return 0;
リスト -1.2.3
Dec() … １だけカウント・ダウンする
Val() … オブジェクト内のカウント値を返す
上記右側に、Counter オブジェクトが呼出される様子を示す。オブジェクト内の変数や、操作は、オブジェ
クトの中だけで有効で、オブジェクト毎に、独立なため、互いに影響しない。従って、クラスの再利用が容
易です。
本サンプルのソースは、
”LEDA セミナー CD-ROM”の Leda1¥Leda_src¥Source¥Seminar¥my_demo¥Counter.c
にあります。コンパイル方法については、別冊の「LEDA 速習 == デモ・サンプルの操作 ==」を参照下さい。
1.3 ウィンドウについて
LEDA のウィンドウには 次のような多種のオブジェクトを描くことができる。 夫々のサンプルについ
ては 第５章を参照下さい。
１ . 幾何オブジェクト
２ . グラフ・オブジェクト
３ . メッセージ
４ .GUI オブジェクト (ボタン、選択リスト、テキスト・ボックス等)
５ . 画像データ (BMP, XPM フォマット)
リスト -1.2.4 のソース・ファイルは、”LEDA セミナー CD-ROM”の
Leda1¥Leda_src¥Source¥Seminar¥my_presen¥05_1_zukei.c にあります。また、操作方法については、別
冊「＝デモ・サンプルの操作＝」の P2.「■ 2 ■ P7: ウィンドウ」にあります。
- 4 -
第２章
基本 と データ構造
2.1 無限桁数の整数
f (n) =
2
f ( n −1 )
は、再帰型定義によって、初期
値 (ｎ = 0 の時の値) が決ま
れば、以降は順次計算される。
ここで、Integer は無限桁数を扱える整数です。ハードウェア
のリソース（メモリ容量等）が許す限り桁数の制限はない。初
期値 f(0)=2 とすると、f(4) は約 19000 桁の整数となる。
f ( 0 ) = 2,
f (2) =
f (3) =
f (4) =
2
f (1 )
f (2)
2 f (3)
2
f (0)
2
= 2
f (1) =
=
=
4
=
2
2
= 4
= 16
16
2 65536=
2
integer f(int n){
integer m, limit, i;
if(n==0) return 2;
limit= f(n-1); m= 1;
for(i=0; i<limit; i++)
m= m*2;
return m;
}
void main(){
int n;
while(1){
n= read_int("正整数を入力:");
if(n<0) break;
cout<<"f("<<n<<")="<<f(n)<<endl;
}
}
リスト-2.1
65536
= 約 19000 桁
リスト -2.1 のソース・ファイルは、”LEDA セミナー CD-ROM”の
Leda1¥Leda_src¥Source¥Seminar¥my_presen¥05_2_integer.c にあります。また、操作方法については、別
冊「＝デモ・サンプルの操作＝」の P2.「■３■ P8： 基本部分： 数値型 ...Integer」にあります。
2.2 有理数
Rational（有理数） は、分数で表され、そ
の分母､分子として Integer を持つ。従っ
て、分数表記のままで計算を行うと計算誤
差は常に ０ である。計算結果の値が必要
であれば、Method x.to_float() により近
似値を得る。
Rational ‚É‚Í•Âȉº‚̂悤
‚È—L—p‚È Method ‚ª
—pˆÓ‚³‚ê‚Ä‚¢‚é•B
Rational q;
q.denominator() -- 分母を返す
#include <LEDA/rational.h>
void main() {
rational q1(117,315), q2; // q1= 117/315
cout <<" 有理数を入力して下さい（一例：48/228）:";
cin>>q2;
cout << q1 << " の分母＝ " << q1.denominator() << endl;
cout << q1 << " の分子＝ " << q1.numerator() << endl;
cout << "q1+q2 ＝ " << q1+q2 << endl;
cout << "(約分) 117 / 315 ＝ " << q1.normalize() << endl;
cout << q2 << " の逆数＝ " << q2.inverse() << endl;
cout << q2 << " の近似値＝ " << q2.to_float() << endl;
read_int("OK");
}
↑ リスト -2.2
↓ その実行結果の画面
q.numerator() -- 分子を返す
q.normalize() -- 通分した値を返す
q.inverse()
-- 逆数を返す
リスト -2.2 に、サンプルを示し、その下
に実行結果を示す。
リストからも分かるように、変数 q 2
(rational) に、コンソールから分数形式
（48/228）のデータを直接入力できます。
cin >> q2; （ここで、cin= 48/228）
リスト -2.1 のソース・ファイルは、”LEDA セミナー CD-ROM”の
Leda1¥Leda_src¥Source¥Seminar¥my_presen¥06_1_rational.c にあります。
- 5 -
2.3 REAL による任意精度の計算 ((√、
√、
π)
√、π
■１■
17
#include <LEDA/real.h>
main(int argc, char *argv[]){
real x = 17.0;
real y = sqrt(x);
bigfloat z;
int keta= atoi(argv[1]);
を１万桁まで計算する
Real（実数）型の計算結果を、必要な有効桁数を指定し
て Bigfloat で求められる。リスト -2.3.1 を実行する
real::io_dec_precision = keta;
cout <<"io_dec_precision="<<keta<<endl;
cout << y << endl;
と、以下の結果が得られる。
サンプルでは、有効桁数を指定するのに次の２通りで
行っているが、得られる結果は同じです。
bigfloat::set_output_precision(keta);
z = y.to_bigfloat();
cout <<"set_output_precision="<<keta<<endl;
cout << z << endl;
1) real::io_dec_precision = keta;
2) bigfloat::set_output_precision(keta);
リスト -2.3.1 を実行すると、以下の結果が得られます．
}
> ./app 10000
リスト -2.3.1
4.1231056256176605498214098559740770251471992
25373620434398633573094954346337621593587863
65081068429668454404093921414161530142084041
58683630795481457469069776770232664362408630
877905675723857082255213807.................
リスト -2.3.1 のソース・ファイルは、”LEDA セミナー CD-ROM”の
Leda1¥Leda_src¥Source¥Seminar¥pai200¥root17.c にあります。
■２■ πを１万桁まで計算する
マーチンの公式（1）に , グレゴリー級数（2）を適用すると、無限級数（3）が得られる。
......（1）
......（2）
.....（3）
リスト -2.3.2 に示すように、計算過程を Rational で行い、最後に値を得る段階で 有効桁数指定した
Real を用いる。 以下の例では 級数展開を１万項目まで行い、１万桁のπの値を求める。
パソコン（CPU 200MHz, Memory 64MB）で計算すると、有効桁数が 500 桁で 45 分程かかる。参考までに、
東大・金田研究室のスーパーπ
http://www1.coralnet.or.jp/kusuto/PI/
rational f(int n){
super_pi.html
//再帰型関数
rational r5, r239; int minus= 1;
integer n21= 2 * n + 1;
//n21= 2n + 1
if(n % 2==1)
minus= -1;
//n: ODD
r5= rational(16, n21* pow(5,n21));
r239= rational(4, n21* pow(239,n21));
if(n==0)
return(rational(16,5) - rational(4,239));
if(minus==1)
return(f(n-1) + r5 - r239 );
else return(f(n-1) - r5 + r239 );
では、100 万桁でも数分で結果が得られます。
リスト -2.3.2, リスト -2.3.3 のソース・ファイルは、
”LEDA セミナー CD-ROM”の
Leda1¥Leda_src¥Source¥Seminar¥pai200¥pai200.c
にあります。
void main( ) {
real::io_dec_precision=10000;
real x= f (10000);
cout<< x <<endl;
}
リスト -2.3.2
- 6 -
}
リスト -2.3.3
2.4 辞書型配列 ((柔軟な疎配列
柔軟な疎配列
)
柔軟な疎配列)
■１■ 辞書型配列とは
・インデックスとして、任意の変
数の型（int,string,,,）が使え
ます。
・インデックスとして、非連続の
数が使える。以下の例では、予め
[通常の配列]
int A[5] は、A[0]∼ A[4]の５つの
整数値を格納する。この 0 ∼ 4 はインデックスです。
[辞書型配列] キー、デーダー
d_array<int, string> Int_toYen;
d_array<string, int> count(0); // 全要素を初期化
d_array<string, string> dials;
配列要素を 1001 個確保する必要
はなくて、最小限の３個分の要素をシステムが自動的に確保してくれます。
Int_toYen[1]=”一”; Int_toYen[1000]=”千”; Int_toYen[10000]=”万”;
・インデックスとして、文字が使える。文字をキーにして値を参照できる
・配列のサイズを､最初に宣言する必要がない。
――＞ 値を格納すると、自動的に必要なサイズを確保する。
・forall_defined(s, Int_toYen)
cout << s <<
<< Int_toYen(s) << endl;
図 2.4
――＞ 全ての要素について繰返し処理を簡単にできる。
図 2.4 は、
”LEDA セミナー CD-ROM”の Leda1¥Leda_src¥Source¥Seminar¥my_presen¥int_d_array.c を実
行した結果を示します。始めに、 d_array への登録を行い（登録の終了は‘-1’です）、次に、キーを指
定して d_array の内容を呼出しています。
■２■ 辞書型配列の応用例
（電話帳）
辞書型配列の応用例（
電話帳データ を読込み、
名前の出現頻度をチェックし、
void main(){
一覧表を表示する。実行結果を以下に示す。
d_array<string,int> count(0); // 名前、頻度
d_array<string,string> dials; // 名前、説明
string name, dial;
ifstream fin(典elephone.dat");
F:¥Leda> d_array.exe
" 佐野 ":" サノ ____:03-5228-5525";
" 平山 ":" ヒラヤマ:042-395-7407";
" 山本 ":" ヤマモト:0721-85-8053";
" 山下 ":" ヤマシタ:06-2331-1234";
" 菊池 ":" キクチ __:03-5225-1221";
" 井口 ":" イグチ __:0742-44-3414";
" 佐野 ":" サノ ____:03-5228-5525";
" 山下 ":" ヤマシタ:06-2331-1234";
" 佐野 ":" サノ ____:03-5228-5525";
" 平山 ":" ヒラヤマ:042-395-7407";
名前 と
" 井口 "
" 菊池 "
" 佐野 "
" 山下 "
" 山本 "
" 平山 "
その出現頻度
＝1
＝1
＝3
＝2
＝1
＝2
名前 と
" 井口 "
" 菊池 "
" 佐野 "
" 山下 "
" 山本 "
" 平山 "
OK ？
そのコメント
＝ " イグチ __:0742-44-3414"
＝ " キクチ __:03-5225-1221"
＝ " サノ ____:03-5228-5525"
＝ " ヤマシタ:06-2331-1234"
＝ " ヤマモト:0721-85-8053"
＝ " ヒラヤマ:042-395-7407"
while(!fin.eof()){
fin >> name >> dial;
cout << name <<":"<< dial <<";"<<endl;
count[name]++;
dials[name]= dial;
}
forall_defined(name, count)
// 名前、頻度
cout<< name <<" ="<<count[name]<< endl;
forall_defined(name, dials) // 名前、説明
cout<< name <<" ="<<dials[name]<< endl;
}
リスト -2.4.1
リスト -2.4.1 のソース・ファイルは、”LEDA セミナー CD-ROM”の
Leda1¥Leda_src¥Source¥Seminar¥my_presen¥07_2_d_array.c に
あります。
- 7 -
Telephone.dat
電話帳データ
キー、デーダー
“佐野” "サノ
:03-5228-5525"
“平山” "ヒラヤマ :044-593-1407"
“山本” "ヤマモト :0721-85-8053"
“山下” "ヤマシタ :06-2331-1234"
“菊池” "キクチ
:03-5225-1221"
“井口” "イグチ
:0742-44-3414"
“佐野” "サノ
:03-5228-5525"
“山下” "ヤマシタ :06-2331-1234"
“佐野” "サノ
:03-5228-5525"
“平山” "ヒラヤマ :044-593-1407"
2.5 スタック／キュー／リスト −その応用 ((迷路脱出
迷路脱出
)
迷路脱出)
■１■ Stack / Queue
図 2.5.1 に示すように、Stack や Queue は、データを積み上げていくようにし
てデータを蓄える。データを追加する時は、最後に積み上げたデータの後ろに
追加する。そして、データを取り出す時は、Stack と Queue で次のような違
いがある。
Stack は、最も新しいデータから順に取り出します。それに比べて、Queue は、
最も古いデータから順に取り出す。夫々主な Method は以下のようです。
stack<string> S;
S.push(string s);
データ格納
s= S.pop();
s= S.top();
データ取出（Ｓｔａｃｋ より削除）
データ読出（Ｓｔａｃｋ に残る）
S.clear();
S.empty()
S.size()
Ｓｔａｃｋ をクリア
Ｓｔａｃｋ は空か？
Ｓｔａｃｋ の中の要素数を返す
queue<string> Q;
Q.append(string s);
データ格納
s= Q.pop();
データ取出（Ｑｕｅｕｅ より削除）
s= Q.top();
データ読出（Ｑｕｅｕｅ に残る）
Q.clear();
Ｑｕｅｕｅ をクリア
Q.empty()
Ｑｕｅｕｅ は空か？
Q.size()
Ｑｕｅｕｅ の中の要素数を返す
図 2.5.1
Stack と Queue
■２■ 優先順位付き Queue − PQueue<p, i>(PriorityQueue)
Stack や Queue は、単にデータのみを格納するが、PQueue は、データの値と一緒に、キーの値を格納す
る。PQueue<p, i> の ｐ は、キー値、i はデータ部 です。これらの対になったものは pq_item という型
をもつ。身近な例では、以下のように PQueue が多く見られる。
[ 例 ]＜最高気温、都市名＞：＜ 32, 東京＞、＜ 30, 仙台＞、＜ 28, 長野＞
＜得点、学科名＞
：＜ 68, 国語＞、＜ 90, 数学＞、＜ 100, 英語＞
p_queue<int,string>PQ;
...PQueue の宣言
PQ.insert(68,”外国語”
);
... データの挿入
pq_item it= PQ.find_min();
... 最小データを取出す
cout<<PQ.inf(it)<<PQ.prio(it); ... データ部と、キー値を取出す
PQ.del_item(it);
...PQueue の要素を削除
PQ.clear();
...PQueue をクリア
PQ.empty()
PQ.size()
...PQueue は空か？
...PQueue の中の要素数を返す
図 2.5.2
■３■ 連結リスト構造
（双方向）− List
連結リスト構造（
図に示すように、Listは要素と要素をポインターでリンクしたデータ構造を持ち、
以下に示す多様なMethod
を持つ。すなわち、List は、Stack としても、Queue としても使え、大変柔軟なデータ構造となっている。
LEDA では、オブジェクトの基本要素として、良くこの List が用いられている。
list<int> L;
...List の宣言
list_item L.first();
...List L の先頭の項目
list_item L.last();
list_item L.pred(it);
list_item L.succ(it);
...List L の末尾の項目
...List 項目 it の直前の項目
...List 項目 it の直後の項目
- 8 -
L.contents(it); or L[it]
L.push_front(x)
...List 項目 it のデータ部の値
... データ x を List L の先頭に挿入
L.push_back(x)
... データ x を List L の末尾に挿入
L.push_insert(x,it,before/after) ... データ x を List 項目 it の前または後に挿入
L.del_item(it)
...List 項目 it を削除
#include <LEDA/p_queue.h>
void main(){ //名前(英語)をラストネームでソート
p_queue<string, string> PQ;
string first_name, last_name;
cout << “名前を入力して下さい ¥
（終は end end）
”<< endl;
do{
cin >> first_name >> last_name;
if(first_name==”end” break;
PQ.insert(last_name, first_name);
}while(true);
while(!PQ.empty()){
pq_item it= PQ.find_min();
cout<<PQ.inf(it)<<“ ”<<PQ.prio(it)<<endl;
PQ.del_item(it);
}
}
リスト -2.5.1
■３■ PQueue の応用
名前（英語名）を、LastName
でソートする例を示す。右
の画面は、その実行結果で
す。
プログラム内容は、
リスト-2.5.1に示すように
PQ.find_min() で最小値を
求めて、その要素の内容を
表示した後に、PQ.del_item
(it) で最小値を削除する。
この作業を要素がなくなる
まで繰返す。
図 2.5.3
リスト -2.5.1 のソース・ファイルは、”LEDA セミナー CD-ROM”の
Leda1¥Leda_src¥Source¥Seminar¥my_presen¥09_1_p_queue.c にあります。
■４■ Stack ／ Queue の応用
（迷路の 経路探索）
の応用（
Stack ／ Queue の応用例として、迷路を脱出するアルゴリズムを考えます。図 2.5.4 で、
（S)は出発点、
（G)
はゴールです。迷路探索の作業用のバッファとして Stack を用いた手順を以下に示す。
<1> まず（S)の廻り（上下左右）の４つのセルを調べ、その中に（G)があれば終了する。
図 2.5.4
<2> 廻りの４セルに（G)がない場合は、４セルを上下左右の順に Stack に積む。
<3> Stackよりセルを取出
し、次の探索用の（S)とす
る。この時取出されたセ
ルは最後に積まれた[ 右]
のセルである。
<4> 新しい（S)について、
上記の<1>∼<3>を実行す
る。
<5> 図 2.5.4（左側）に示
すように、新しい出発点
（S)は、右方向に伸びる傾
向がある。図でピンクのセ
ルは（S)の廻り４セルの集
合である。
<6> （G)を見つけた時点で
探索を終了して、繰返し
ループの中で設定された
（S)を逆順に辿って答（脱
出経路：シアン色）が得ら
れる。
図 2.5.5
- 9 -
図 2.5.4（左側）は、探索バッファとして Stack を用いた場合ですが、探索バッファとして Queue を用いた
結果は図 2.5.4（右側）のように、最初の出発点（S)に対して探索範囲が同心円上に広がったものとなる。
探索バッファとして Queue を用いた場合も、探索手順は、Stack の場合と同様であるが、<2> と <3> の手順
が若干異なり、以下のようになる。
<2> 廻りの４セルに（G)がない場合は、４セルを上下左右の順に Queue に積む。
<3> Queue よりセルを取出し、次の探索用の（S)とする。この時取出されたセルは最初に積まれた[上]の
セルである。
−−−壁がゴールのすぐ右にある場合−−−
図2.5.5に、壁がゴールのすぐ右にある場合を示す。左側が探索バッファとしてStackを用い、右側がQueue
を用いた場合を示す。Stackでは右方向に探索範囲を伸ばして行き、全て探索し終えると、次に最初の出発
点（S)の[下]のセルをチェックする。このようにして、右下のセルまで、全セルを探索し尽くし、ゴール
（G)が見つからなければ、Stack を遡って、最初の出発点（S)の[上]のセルの廻りをチェックして、やっと
（G)を見つける。
−−− PQueue（優先順位付き Queue）を用いた場合−−−
探索バッファとして、PQueue を用いると、Stack や Queue のように、壁などの条件に影響されず、常に効率
の良い探索を行うことができる。PQueueのデータ部は、StackやQueueと同様にセルのxy座標値である。そ
して、PQueue のキー部は、各セルからゴールまでの距離です。キーの値を常に最小にするように探索を行
います。PQueue を用いた場合も、探索手順は、Stack の場合と同様であるが、<2> と <3> の手順が若干異な
り、以下のようになる。
<2> 廻りの４セルに（G)がない場合は、４セルを上下左右の順に PQueue に積む。
<3> PQueueよりセルを取出し、次の探索用の（S)とする。この時取出されたセルは、４つのセルの中でキー
（セルからゴールまでの距離）の値が最小のセルである。
図 2.5.6 のソース・ファイルは、”LEDA セミナー CD-ROM”の
Leda1¥Leda_src¥Source¥Seminar¥my_presen¥new_maze.c にあります。また、操作方法については、別冊
「＝デモ・サンプルの操作＝」の P2.「■４■ P19： Stack ／ Queue の 応用・迷路の経路探索」にありま
す。
- 10 -
第３章
グラフ と アルゴリズム
3.1 グラフとは ((パラメータ付グラフ、
パラメータ付グラフ、
Static グラフ
)
パラメータ付グラフ、Static
グラフ)
グラフとは、右図のように、複数のノード（点）と、それらを結ぶエッ
ジ（線分）で構成されるデータ構造を示します。グラフ・クラスを、そ
の構造を見えるように機能拡張したものが GraphWin クラスです。こ
れは、グラフの性質にウィンドウ属性（座標値、大きさ、色など）を
付加して、グラフの振る舞いを常に見る事により、アルゴリズムのデ
バッグを容易にします。 リスト -3.1 で、gw.display() メソッドを
実行すると、ウィンドウ上に表示されます。
多くの種類のグラフがあり、その２∼３を紹介します。
パラメータ付グラフ：
パラメータ付グラフ
：
ノードやエッジに、複数のパラネータを関連付ける事ができます。
#include <LEDA/graphwin.h>
void main(){
GraphWin gw("Gra Editor");
gw.display();
gw.edit();
}
リスト-3.1
例えば、グラフの最短経路を求めるような場合は、エッジに重み（距
離）を関連付けると好都合です。また、同じ例題で、スタート・ノー
ド（基準ノード）からの累積距離を各ノードに関連付けると、アルゴリズムが大変スッキリとします。
グラフ：
Static グラフ
：
グラフを生成する時に、グラフの構成（ノードやエッジの数 と 接続方法など）が決まり、それ以降は
グラフの構成が変化しないで、参照されるだけと言うケースは良く見られます。前例の”最短経路探索”も
そうです。このような場合、Static グラフ を用いると、処理が大変高速になり、メモリー使用量も最小
に抑える事ができます。
リスト -3.1 のソース・ファイルは、”LEDA セミナー CD-ROM”の
Leda1¥Leda_src¥Source¥Seminar¥my_presen¥11_1_graph1.c にあります。操作方法については、別冊「＝
デモ・サンプルの操作＝」の P3.「■５■ P21： グラフ：グラフ構造 ...Graph の生成」にあります。
3.2 グラフの基本性質
■１■ グラフのプロパティ
グラフのノードやエッジは、次のような種々のプロパティ（属性）を持ちます。
Node：ラベル（Font、色）
位置、サイズ
隣接 Node リスト
入力 Edge リスト
出力 Edge リスト
接続される全 Edge リスト
選択されている（Selected）
ユーザ・プロパティ
Ｅｄｇｅ： ラベル（Font、色）
線幅、線種（直線 ,Dot,Dash）
有向、無向（bool 値）
選択されている（Selected）
ソース Ｎｏｄｅ
ターゲット Ｎｏｄｅ
ユーザ・プロパティ
ユーザ・プロパティは、ユーザが自由に付加出来る属性で、種々のデータ型（整数、文字列、
、、
）を割当て
ることが出来ます。”LEDA セミナー・サンプル”の中にある”プロジェクト管理”のサンプルでは、エッジ
に Ready と言うフラッグを付加して、エッジのソース・ノードが処理済みの時に Ready=ON として、そ
のエッジのデスティネーション・ノードの処理が可能であることを明示します。
- 11 -
■２■ グラフの構造
リスト-3.2 に示すように、４つのノードと、４つのエッジを生成すると、各ノードにの出次数や入次数が
自動的に設定される。
〔
次数：Node に接続される Edge の数
出次数： Node から出る Edge の数
入次数： Node に入る Edge の数
例えば、ノード１（V[1]）
の出次数は２
で、入次数は１
〕
です。
void main(){
graph G; node v[4]; int i;
for(i=0; i<4; i++)
v[i]= G.new_node();
edge e01= G.new_edge(v[0], v[1]);
edge e02= G.new_edge(v[0], v[2]);
edge e12= G.new_edge(v[1], v[2]);
edge e13= G.new_edge(v[1], v[3]);
for(i=0; i<4; i++){
cout<<i<<“の出次数=”<<G.outdeg(v[i])<<endl;
cout<<i<<“の入次数=”<<G.indeg(v[i]) <<endl;
}
リスト -3.2 のソース・ファイルは、”LEDA セミナー CD-ROM”の
Leda1¥Leda_src¥Source¥Seminar¥my_presen¥11_2_graph2.c にあります。
■３■ グラフ
・アルゴリズム
グラフ・
LEDA では、以下に述べるような多くのアルゴリズムがクラスとして用意されています。
流れ（
（１）流れ
（フロー）に関するアルゴリズム
（４）最短経路アルゴリズム
・MAX_FLOW_T( )：”s”,”t”間の最大流量を計算
graph G; ...
edge_array<int> capacity(G);
edge_array<int> flow(G); //flow: 結果
MAX_FLOW_T(G,s,t,capacity,flow);
・MIN_COST_FLOW（ ）
： ...
各辺に費用を割当て、
最小フローを求める
・M I N _ C O S T _ M A X _ F L O W （ ）： . . .
”s”,”t”の間の費用最小、
流量最大の流れ
・max_flow_gen_rand( )：
最大フロー問題を生成
（２）最小木に関するアルゴリズム
・SPANNING_TREE(G)：
全域木
・MIN_SPANNING_TREE(G,cost)：
費用が最小の全域木
graph G; ....
edge_array<int> cost(G); ...
list<edge> L=
MIN_SPANNING_TREE(G,cost);
実行後 銑 にはツリーが入る。
... 種々の手法がクラスとして提供されてる
・ダイクストラ
DIJKSTRA_T(Graph,start_node,cost,dist);
・ベルマン・フォード
BELLMAN_FORD_B_T(Graph, ,, );
・全節点対最短経路
ALL_PAIRS_SHORTEST_PATHS_T(Graph, ,,);
‘ダイクストラ法’では、頂点’s’から始まる
全ての最短経路を計算する
graph G; ...
edge_array<int> cost(G);
node_array<int> dist(G);
DIJKSTRA_T
(G,s,cost,dist);
計算完了後は 租 ist に距離
の値が入る。
（５）マッチング
・アルゴリズム
マッチング・
・MAX_CARD_MATCHING(G)：最大個数マッチング
・MAX_WEIGHT_MATCHING(G)：
重み付最大個数マッチング
・MAX_CARD_BIPARTITE_MATCHING(G)：
２部グラフの最大個数マッチング
・MAX_WEIGHT_BIPARTITE_MATCHING_T(G)：
２部グラフの重み付最大個数マッチング
（３）グラフ描画アルゴリズム
・SPRING_EMBEDDING(G,)：バネ埋め込み
・STRAIGHT_LINE_EMBEDDING(G,)：
平面グラフの直線による埋め込み
・VISIBILITY_REPRESENTATION(G,)：
平面グラフの視覚表現
・ORTHO_DRAW(G,)：
平面グラフの直行埋め込み
（６）トポロジカル
・ソート
トポロジカル・
全ての有向辺（u,v）に対して
接点 u の番号 ＜ 接点 v の番号
となるように、接点に番号をつけよ。
GIT_TOPOSORT<OutAdjIt, Indeg, Queuetype >
- 12 -
(７）
それ以外に、
次のアルゴリズムをクラスとして提供
７）それ以外に、
それ以外に、次のアルゴリズムをクラスとして提供
１．グラフの平面性判定 ･･･ i= PLANAR(graph&, bool embed=false)
もし、グラフが平面なら、エッジの交差なく描画します。
２．平面グラフの３角分割 ･･･ TRIANGULATE_PLANAR_MAP( )
平面地図を表すグラフG が与えられた時、 Gの全ての面をエッジ
の挿入により三角形にします。
３．平面グラフを５色で彩色します ･･･
FIVE_COLOR(graph& G, node_array<int>& C)
４．深さ優先探索･･･有向グラフの始点から、各ノードに対し計算、DFS()
５．幅優先探索･･･ BFS( )
６．強連結成分･･･ STRONG_COMPONENTS( )
７．２連結成分･･･ BICONNECTED_COMPONENTS( )
８．推移的閉包･･･ TRANSITIVE_CLOSURE( )
3.3 グラフの応用
■１■ 伝送障害シミュレーション
・イントラネット（社内 LAN）を想定し
ています。東京、大阪などの拠点の下に
ルータ（A,B,..,A1,..）があり、各ルー
タの下にクライアント（パソコンのホ
スト名が Yama,Kawa,..）があります。
・各ノードに接続される隣接ノード・
リストを手繰って行くことにより、経
路を求める事ができます。
・一例として、D1.Lion ∼ A2.Kumo
の 2 点を接続する伝送経路を求める。(赤色の経路)
・このサンプル のソース・ファイルは、”LEDA セミナー CD-ROM”の
Leda¥demo¥shortPath¥Network.java にあります。
また、操作方法については、別冊「＝デモ・サンプ
ルの操作＝」の P3.「■６■ P23： グラフの応用・
伝送障害シミュレーション」にあります。
・グラフに関する多くのクラスと Method を
利用して簡潔なコーディングが可能です。
Edge getEdge(n1, n2);
Edge getEdge(target_node);
list<Node> nl= node.neighbors();
・簡単な入出力
G.write(“ファイル名”);
G.read(“ファイル名”);
次に、グラフの応用例として、いくつかのアルゴリズムを紹介します。
トポロジカル・
■２■ トポロジカル
・ソート
トポロジカルソートの定義： とは、全ての有向辺（u,v）に対して
”接点 u の番号 ＜ 接点 v の番号 ”となるように、接点に番号をつけよ。
上図において、Node4->Node2 が、このルールに反しています。ノード番号を上から順に 1,3,4,2,5
と付け直すと、ルールに則します。この新しいノード番号を得ることを、トポロジカル・ソートと言う。
ソート手順は、図に示すように、グラフから入次数 =0 のノードを取り除きます。この操作をグラフの
ノードがある限り続けます。そして、取り除いたノード番号の順番が、欲するソート結果です。
- 13 -
この手順を、コーディングし
たのが ”リスト -3.3”です。
また、LEDA では、
GIT_TOPOSORT<OutAdjIt,
Indeg, Queuetype> と言う
クラスが用意されています
ので、トポロジカル・ソー
トを 1 回の呼び出しで実行
する事が可能です。
void main(){
graph G;
queue<node> Q;
int count= 1;
G.read("graph1.gw");
node_array<int> ord(G);
node_array<int> IN(G);
node v, w; edge e;
リスト -3.3
リスト -3.3 のソース・ファイ
ルは、”LEDA セミナー CD-ROM”の
forall_nodes(v,G)
if((IN[v]=G.indeg(v))==0) Q.append(v);
while(!Q.empty()){
v= Q.pop();
ord[v]= count++;
forall_out_edges(e,v){
w= G.target(e);
if(--IN[w]==0) Q.append(w);}
}
cout <<"Node number= ";
forall_nodes(v,G)
cout<<ord[v]<<" ";
cout << endl;
}
Leda1¥Leda_src¥Source¥Seminar¥my_demo¥topology.c にあります。また、操作方法については、別冊「＝
デモ・サンプルの操作＝」の P5.「■
８■ P26： グラフ： グラフ構造 ...
トポロジカル・ソート」にあります。
■３■ プロジェクト管理
・”技術、営業、営業補助、業者”の
４つのチームがセミナー開催に向け
てプロジェクトを組み、その進捗を
管理するのを想定しました。各ノー
ドは、作業または会議を示し、左か
ら右のゴールへと処理を進めます。
また、各エッジは、そのソース・ノー
ドの状態を表し、ノードの作業または会議が完了すれば、Ready 状態（赤色）にセットされます。
・ノードを選択（クリック）し、
”完了”ボタンをクリックすると、選択されたノードの作業が完了します。
シフト・キーを押しながら複数ノードをクリックする事により、複数ノードの処理を同時に実行できます。
・会議ノード（八角形）の全ての入力エッジが Ready でないと、そのノードを完了できません。例えば、
”
キックオフ”の３つの会議ノードに対しては、夫々の３つの入力エッジの全てが Ready でないと、実行
できません。また、１つの作業ノード（四角形）に、入力エッジが複数個ある場合は、その全ての入力エッ
ジが Ready でないと、作業を実行できません。
（例えば、
”ＤＭ e-mail 発送”ノード）
・このサンプルは、グラフのエッジに Ready と言うユーザ定義プロパティを付加して、簡潔にコーディン
グできました。
・このサンプル のソース・ファイルは、”LEDA セミナー CD-ROM”の
Leda¥demo¥shortPath¥Project.java にあります。また、操作方法については、別冊「＝デモ・サンプルの
操作＝」の P4.「■７■ P24： グラフの応用・プロジェクト管理」にあります。
3. ４ 最短経路探索−その応用 ((駅スパート
駅スパート
)
駅スパート)
■１■ 基準点から各ノードへの最短経路
・グラフの基準ノードから、その他の各ノードに至る最短
経路を求める事ができます。
・右図で、Node ０が基準ノードで、エッジの横にある数字がエッジの長さ（距離）です。２つのグラフの
右側で赤色のエッジが最短経路を示します。
・例えば、Node ０∼ Node ４への最短経路は、0-3-5-4 となります。見た目は 0-1-4 の方が最短経路のよ
うに見えますが、その時の合計は 41(= 9+32) となり、 0-3-5-4 の合計 39 より大きくなり、0-3-5-4 が
最短経路である事が分かります。
- 14 -
・ここで、１∼４の長さを 29（← 32）に変更すると、0-1-4 の合計が 38 となり、最短経路となります。
・コーディング例を リスト -3.4 に示します。
このサンプル のソース・ファイルは、”LEDA セミナー CD-ROM”の
Leda¥demo¥text4¥ShortPath_3.java にあります。また、操作方法については、別冊「＝デモ・サンプルの
操作＝」の P5.「■９■ P29： グラフ： 経路アルゴリズム」にあります。
do{
dmin= MAXDOUBLE;
forall_nodes(v,G)
if(!visited[v] && dist[v] < dmin){
dmin= dist[v]; u= v;
}
if(dmin==MAXDOUBLE) break;
visited[u]= true;
forall_out_edges(e,u){
v= target(e);
if(dist[u]+cost[e] < dist[v])
dist[v]= dist[u]+cost[e];
}
}while(true);
forall_nodes(v,G)
cout<<"node"<<index(v)<<
"distance="<dist[v]<<endl;
#include <LEDA/graphwin.h>
void main(){
array<int> cos1(11);
GRAPH<int, int> G;
G.read(
“ShortPath.gw");
node s= G.first_node();
edge_array<int> cost(G);
cost= G.edge_data();
node_array<double> dist(G, MAXDOUBLE);
node_array<bool> visited(G,false);
node u=s,v=s; edge e;
double dmin;
dist[s]= 0;
リスト -3.4
}
↑ 図 3.4-1
図 3.4-2 →
■２■ 駅スパートへの応用
・例えば、東京の山手線の中央線
から南半分をグラフとして扱う事ができます。ノードには「駅名」を割当て、エッジのプロパティとして
は、
「駅間の所要時間」と「駅間の距離」の２つを割当てる事ができます。
・
「出発駅」と「到着駅」を指定して、
「所要時間で」のボタンをクリックすると、指定した条件での最短経
路を求める事ができます。また、
「所要距離で」のボタンをクリックすると、指定条件を変更して、最短経
路を再検索する事ができます。
・このサンプルは、yFiles（Java 環境）で開発され、次のクラスが呼び出されています。
経路探索用クラス dijkstra.setDirdijkstra.setDirectedMode(false);
list<Edge> path = dijkstra.getShortestPath(graph, from, to, weightMap);
LEDA でも、同様なクラスが用意されています。
・
「乗換駅」については、ダミーの駅を経由するようにして、処理を簡素化しました。図 3.4-1 にその様子
を示します。
・このサンプル のソース・ファイルは、”LEDA セミナー CD-ROM”の
Leda¥demo¥shortPath¥Expert.java にあります。また、操作方法については、別冊「＝デモ・サンプルの
操作＝」の P6.「■ 10 ■ P31： 経路探索の応用・駅スパート」にあります。
- 15 -
3. ５ 最大フロー ((油田のパイプライン問題
油田のパイプライン問題
)
油田のパイプライン問題)
・油田（Source）から港（Target）へ 向けて複
数のパイプラインを経由して石油を流す時、その
最大流量を得るため、各中継所でバブルを制御す
る
・Edge の数字は現在の流量／キャパシティ（最大
量）を表します。
GRAPH<int,int> G;
node s = G.first_node(); // 油田
node t = G.succ_node(s); // 港
edge_array<int> f(G,0); // 結果
MAX_FLOW(G,s,t,G.edge_data(),f);
このサンプル のソース・ファイルは、”LEDA セミナー CD-ROM”の
Leda1¥Leda_src¥Source¥Sample¥graph_alg¥gw_max_flow.c にあります。また、操作方法については、別
冊「＝デモ・サンプルの操作＝」の P16.「■８■ <graph_alg> gw_max_flow： 最大フロー」にあります。
- 16 -
第４章
幾何データの扱い
4.1 幾何オブジェクトの表現 ((点
点､線､円､多角形、)
■１■
点／線分オブジェクト
点 オブジェクト
・point p(x, y);
... 点の生成
・p.xcoord(), p.ycoord();
・p1.distance(p2);
・p= center(p1, p2);
... 点の X 座標、Y 座標
...2 点 p1, p2 の距離
...2 点 p1, p2 の中点
・i=orientation(p1,p2,p3);
...i=1:反時計、0:一直線、−１:時計方向
線 オブジェクト
・segment s1(p1, p2); s2(x1,y1,x2,y2); ... 線分の生成
・p1=s.start(); p2=s.end();
・s.length();
・s.contains(p);
・s1.intersection(s2,p);
・s.distance(p);
■２■
... 線分の始点、終点
... 線分の長さ
... 線分 s 上に、p があるか？（bool 値）
... 線分 s1 と s2 の交点 を p
... 線分 s と p の距離
円／多角形オブジェクト
円 オブジェクト
・circle c(p1,p2,p3); c(p1,p2); c(p,r); c(x,y,r); ... 円の生成
・c.center(), c.radius();
... 円の中心座標、半径
・c.inside(p); c.contains(p);
... 点 p は円の内部？、円の上？
・c1.intersection(c2); c.intersection(s);
... 円 c1,c2 の交点
・c.distance(p); c.distance(l);
... 円と点の距離、円と線の距離
多角形 オブジェクト
・polygon P(list<point> pl);
・P.is_simple();
・P.inside(p); P.outside(p);
... 多角形の生成
... 多角形は単純化？
... 点 p は、多角形の中か？、外か？
・P.on_boundery(p);
・P.is_convex();
・P.rotate90(p);
... 点 p が多角形の境界上にあるか？
... 多角形は凸か？
... 点 p の周りに多角形を９０度回転
4.2 幾何図形間の関係
ウィンドウ上に星形を描く場合を考える。星形は、正５角形の頂点を 2 つ目毎に結んで得られる。5 つの頂
点は、次のように円周を５等分して得られる。
（図 4.2.1 参照）
double t = to_radian(360 / 5); // 度→ラジアン
point p = point(r * cos(t * n), r * sin(t * n) ); //n=1,..,5
このデモ（star.exe）については , 別冊「＝デモ・サンプルの操作＝」で詳しく説明しています。次のよう
に各種パラメータを変更できる。
(1) 頂点の数、図形の位置と大きさ
- 17 -
(2) 線の色、幅
(3) 頂点の接続方法
右側にあるメニューはユーザ定義によるクラス・オブジェクト
ですが、代わりに LEDA システムの「GUI クラス」を用いるこ
ともできる。
また 図 4.2.2 に示すように種々の図形や文字を表示できる。
これは、図形や文字を複数ポリゴン（多角形）の集合としてデー
タ・ファイルを作成
して、そのデータ・
図 4.2.1 正ｎ角形
ファイルを読込んで
表示している。表示
は、次の Method を呼
出しています。
W.draw_polygon(P, black);
W.draw_filled_polygon(P, blue);
図 4.2.1、図 4.2.2 のソース・ファイルは、”LEDA セミナー CDROM”の
Leda1¥Leda_src¥Source¥Seminar¥my_demo¥star.c にあります。
また、操作方法については、別冊「＝デモ・サンプルの操作＝」
図 4.2.2 文字の表示
の P6.「■ 11 ■ P35： 幾何図形の作図・Star ／ Moji」にあり
ます。
ランダムに描いた多数の線分の中から、
任意の基準点からの距離
が最も近い線分を選び出すことが出来る。
多数の線分の代わりに、
多数の点や円を用いることも出来る。また、基準点の代わりに、
基準線分を用いることが出来る。その様子を 図 4.2.3 に示す。
基準点 p0 と：
点群との距離
p0.distance(pX);
線群との距離
sX.distance(p0);
円群との距離
cX.distance(p0);
基準線分 s0 と：
点群との距離
s0.distance(pX);
線群との距離
s0.distance(sX);
円群との距離
cX.distance(s0);
図 4.2.3 点に一番近い線を求める
点、線分、多角形や円の中から任意の２つを描き、その２つのオブジェクトの関係（内包、接する、交わる
等）や、交点を求めることが出来る。また、円などのオブ
ジェクトに対して、
任意の線分を軸とした鏡像を求めるこ
とが出来る。
（図 4.2.4 参照）
図4.2.3、図4.2.4 のソース・ファイルは、”LEDAセミナー
CD-ROM”の
Leda1¥Leda_src¥Source¥Seminar¥my_demo¥distance.c と
Leda1¥Leda_src¥Source¥Seminar¥my_presen¥what_zukei.c
にあります。また、操作方法については、別冊「＝デモ・
サンプルの操作＝」の P6.「■ 12 ■ P37： 幾何アルゴ
リズム・Distance ／ --------」
、及び P7.「■ 13 ■ P37：
幾何アルゴリズム・------- ／ What_zukei」にあります。
図 4.2.4 ２つの図形の関係
- 18 -
4.3 幾何の応用−正ｎ角形の作図
あたかも、定規とコンパスだけを使って作図するように、基本図形
（点、線分、円など）の豊富な Method を使って、正ｎ角形を描くこ
とが出来る。
図 4.3.1 に、与えられた任意の１辺（CD）を含む正 5 角形を描く様
子を示す。以下のような５つの関数を使っています。
Edge getEdge(p1,p2)…線分（p1,p2）の垂直二等分線
Edge getEge(s)
…線分（s）の垂直二等分線
Edge getEdge(c,s)
…円と線分とで出来る弦
Edge getEdge(c1,c2) …2 円の交点で作られる弦
Edge getEdge(s1,s2) …２線分がなす角の二等分線
このデモ（SakuzuA.exe）については第 8 章(8.3.13)で詳しく説明
図 4.3.1 正５角形− 1
しています。
次に、与えられた円に内接する正５角形の作図のようすを図4.3.2
及び 図 4.3.3 に示す。
このデモ（SakuzuB.exe,
SakuzuC.exe）については
第 8 章(8.3.14)で詳しく説
明しています。
図 4.3.4 に、与えられた任
意の１辺（AO）を含む正７
角形を描く様子を示す。こ
のデモ（SakuzuD.exe）に
ついては第 8 章(8.3.15)で
詳しく説明しています。手
順通りに実行すれば、正 7
角形らしき図形が描かれ
る。手順の最後に各辺に対
する内角を次の関数で求める。
図 4.3.2 正５角形−２
図 4.3.3 正５角形−３
double getAngle(p1,p2,p3);
7 番目の内角が、他の６つより僅かに小さいと言うことで、擬似
生７角形だと分かる。
「辺数３，４，５，６，８，10，12，15，16 の正多角形は作図で
きますが、辺数７，９，11，13，14 の正多角形は作図できない」
ことが知られています。
ガウスは19才のときに正17角形の作図を思いつき、のみならず、
ｎが素数の正ｎ角形について、ｎ＝２ 2^m ＋１が素数の場合に限
り定規とコンパスだけで作図可能であることを発見しています。
上記の４つのサンプル のソース・ファイルは、”LEDAセミナーCDROM”の
図 4.3.4 擬似正７角形
Leda1¥Leda_src¥Source¥Seminar¥new_geo¥get5Kaku.c と get7Kaku.c 及び
Leda1¥Leda_src¥Source¥Seminar¥my_geo¥get5KakuB.c と get5KakuA.c
にあります。また、操作方法については、別冊「＝デモ・サンプルの操作＝」の P7.
「■ 14 ■ P38： 幾何アルゴリズムの応用・正５角形 - １」
、
「■ 15 ■ P39： 幾何アルゴリズムの応用・正５角形 - ２、３」及び
「■ 16 ■ P41： 幾何アルゴリズムの応用・正７角形」にあります。
- 19 -
4.4 幾何の厳密な計算 ((有理数カーネル
有理数カーネル
)
有理数カーネル)
２つの線分をランダムに発生して、その交点を求める。そして、交点が元の２
つの線分上にあるかを判定し、元の線分上にないとエラー・カウンターを１つ
増加する。この操作を十万回行うと、9000回近くはエラーとなる。その原因は、
2つの線分が作る角度が鋭角になるほどに、計算誤差の
影響が出るからです。リスト -4.4.1 を実行すると、下
void main(){
float int count=0, max_coord=10000;
for(int i=0; i<100000; i++){
point a,b,c,d,p;
random_point_in_square(a,max_coord);
random_point_in_square(b,max_coord);
random_point_in_square(c,max_coord);
random_point_in_square(d,max_coord);
line L1(a,b), L2(c,d);
if(L1.intersection(L2,p) &&
(!L1.contains(p)￨￨!L2.contains(p)))
count++;
}
cout<<"100000 中に、"<<count¥
<<" 回エラー"<<endl;
記のメッセージが出ます。
100000 回中に、89191 回エラー
処理時間 = 2.072 秒
OK?
point と line の代わりに、rat_point と rat_line
を使って書き直し（リスト -4.4.2）
、実行すると、以下
のメッセージが得られる。
100000 回中に、0 回エラー
処理時間 = 9.463 秒
OK?
rat_point と rat_line は、
Rational型の幾何オブジェ
クトで、オブジェクトの座標値などをRationalで持つ。
Rational（有理数）は、分母､分子に無限桁数を持った
分数であり、
分数のまま計算を続ければ誤差はいつまで
も出ない。
この事から、Rational 型幾何オブジェクトを用いる事
により計算時間は少し余分にかかるが、
誤差のない幾何
演算を行うことが出来る。
リスト -4.4.1、4.4.2 のソース・ファイルは、”LEDA セ
ミナー CD-ROM”の
Leda1¥Leda_src¥Source¥Seminar¥my_presen¥22_1_intersect1.c
及び 22_2_intersect2.c にあります。また、操作方法
については、別冊「＝デモ・サンプルの操作＝」の P8.
「■17■ P42： 幾何アルゴリズム ...線分の交点 line」
及び「■ 18 ■ P43： 幾何アルゴリズム ... 線分の交
点 rat_line」にあります。
図 4.4.1
}
リスト -4.4.1
void main(){
float int count=0, max_coord=10000;
for(int i=0; i<100000; i++){
rat_point a,b,c,d,p;
random_point_in_square(a,max_coord);
random_point_in_square(b,max_coord);
random_point_in_square(c,max_coord);
random_point_in_square(d,max_coord);
rat_line L1(a,b), L2(c,d);
if(L1.intersection(L2,p) &&
(!L1.contains(p)￨￨!L2.contains(p)))
count++;
}
cout<<"100000 中に"<<count¥
<<" 回エラー "<<endl;
}
4.5 一般ポリゴン ((穴明き多角形
穴明き多角形
) の計算
穴明き多角形)
リスト -4.4.2
ポリゴン（多角形）の L i s t 集合を G E N _ P O L Y G O N
（Generalized Polygons：一般ポリゴン）と言う。ポリゴンには 向き（方
向）がある。ポリゴンを構成する点の並びが反時計方向の時’正方向’と
言い、点の並びが時計方向の時’負方向’と言う。図 4.4.2 のように、正
方向と負方向の２つからなる一般ポリゴンは、
ドーナツのように穴明きポ
リゴンとなる。
２つの一般ポリゴンの演算が GEN_POLYGON クラスの Method として定義
されている。
list<point> L1, L2;
gen_polygon P1(L1), P2(L2),
P3= P1.intersection(P2),
// AND 演算
P4= P1.unite(P2),
P5= P1.diff(P2),
// OR（合成）
// 差
- 20 -
図 4.5.1
P6= P1.sym_diff(P2);
// 排他和
図 4.5.2 に、サンプル・デモの様子を示します。２つの「一般ポ
リゴン」があり、形状は同一で、ともに複数の短冊状のスリット
が開いています。２つの「一般ポリゴン」を、A,B とすると、次
の４つの演算の様子が良く理解できます。
１） Intersection（AND） … A,B の重なり合った部分が得られ
る
２） Unit（OR） … A,Bの少なくても一方を含む部分が得られる
３） Diff（SUB） … Aから Bを取り除いた部分が得られる
４） Sym_diff（EXOR） … Unit（OR） から Intersection（AND）
を差し引いた部分が得られる
このサンプル のソース・ファイルは、”LEDAセミナーCD-ROM”の
図 4.5.2
Leda1¥Leda_src¥Source¥Sample¥d2_geo¥polygon_holes.c にあ
ります。また、操作方法については、別冊「＝デモ・サンプルの操作＝」の P14.「■４■ <d2_geo>
polygon_holes： 一般ポリゴン (穴明きポリゴン)」にあります。
- 21 -
第５章
LEDA での日本語の扱い
5.1 グラフ
・エディタ で グラフ を作成
グラフ・
・グラフ・エディター で、インターラクティブ にグラフを書きます。
その時に、ノードに日本語のラベルを擬似的に割り当てることが出来ます。
・LEDA-4.3 では、ノードのラベルは、英数字に限られます。
（日本語ラベルを使えるよう、メーカーには要望中）
・ノードに、ｘｐｍ 形式の画像を割り当てることが出来ます。 （図１ 参照 ）
図 5.1-1
その画像に、日本語イメージを使う手順を、以下に示します。
リスト１．GraphEdit.c
・リスト１．
（GraphEdit.c） に示す
図 5.1-2
グラフ・エディターを起動します。
・この時、環境変数で、ｘｐｍ 画像
を参照するパスを指定します。
（リスト２．GraphEdit.bat を参照）
・グラフ・エディターのウィンド上で
５つの ノード を描き、各 ノード を
エッジ で接続する。
（図２ 参照）
#include <LEDA/graphwin.h>
int main(){
GraphWin gw("LEDA Graph
Editor");
gw.display();
gw.edit();
return 0;
}
リスト２．GraphEdit.bat
set GW_XPM_PATH= C:¥Japanese¥xpm
GraphEdit.exe
←
図 5.1-3
→
図 5.1-4
図 5.1-5
・ノード１ を選択して、右ボタンを押すと ポップアップ・メニューが現れます。
（図３）
・ポップアップ・メニューの setup を選ぶと、ノードの プロパティ・ウィンドウ が現れます。
（図４）
・プロパティ の Label 項目の type で、
「user」 を選択、
（
「index」 をオフ）
user の 編集欄に、
「@north.xpm」 をセットすると、ノード１ に、
「北」 が表示される。
XPM 画像ファイル の 作成
・この例では、north.xpm, south.xpm, west.xpm, east.xpm の４つの XPM 画像ファイルを用いています。
XPM 画像ファイルは、次の画像エディターで、作成できます。
・Gimp for Windows 、The GIMP（for Linux）
・Xpaint ( Linux ) 、 ImageMagic ( Linux )
5.2 プログラム で グラフ を作成
・プログラム で、グラフを作成する時に、ノードに、ｘｐｍ 形式の
画像を 割り当てることが出来ます。（図１ 参照 ）
その画像に、日本語イメージを使う手順を、以下に示します。
- 22 -
・グラフ・エディタ の時に使用した ｘｐｍ 画像ファイルを用います。
リスト １． NodeLabel.c
リスト ２． news_xpm.h
#include <LEDA/graphwin.h>
#include <LEDA/d_array.h>
#include "news_xpm.h"
#include "xpm¥south.xpm"
#include "xpm¥east.xpm"
#include "xpm¥west.xpm"
#define set_pixmap(V,S) ¥
gw.set_pixmap(V,W.create_pixrect(S))
int main(){
graph G;
GraphWin gw(G);
window& W = gw.get_window();
gw.set_node_label_type(user_label);
gw.display();
#include
#include
#include
#include
・５つの ノードの ｘ、ｙ座標を以下の用に設定します。
0:(200,300), 1=west:(100,300), 2=south:(200,200),
3=east:(300,300), 4=north:(200,400)
・配列 xy[] は、ノードの座標値を格納します。
node v[5];
int xy[]= ¥
{200,300, 100,300, 200,200, 300,300, 200,400};
int eg[]= ¥
{0,1, 0,2, 0,3, 0,4, 1,2, 2,3, 3,4, 4,1};
・配列 eg[] は、８つの エッジ の対応する ノード
番号 を格納します。
for(int i=0; i<5; i++)
v[i]= gw.new_node(point(xy[i*2],xy[i*2+1]));
for(i=0; i<8; i++)
gw.new_edge(v[ eg[i*2] ],v[ eg[i*2+1] ]);
set_pixmap(v[1],
set_pixmap(v[2],
set_pixmap(v[3],
set_pixmap(v[4],
"xpm¥north.xpm"
"xpm¥south.xpm"
"xpm¥west.xpm"
"xpm¥east.xpm"
west);
south);
east);
north);
・gw.new_node(x,y) で、５つの ノード を作成し、
gw.new_edge(n1,n2) で、８つの エッジ を作成します。
・set_pixmap(node, xpm) で、ノード に ｘｐｍデータ
を対応させます。
set_pixmap(node, xpm) は、マクロ定義です。
gw.redraw();
gw.edit();
return 0;
リスト ３． north.xpm
}
・各ｘｐｍファイル を、リスト３．に示します。
・ｘｐｍデータは、文字列配列に対する ポインター
として記述されています。
・ 左のリストに示すように、ポインターのラベルを
長い名前（ファイル・パス） から、シンプルな ラ
ベルに変更しています。
/* XPM */
//static char * C:¥Japanese¥xpm¥north_xpm[] = {
static const char *north[] = {
"50 50 11 1",
" c None",
". c #FFFFFF",
"+ c #1D1D1D",
"@ c #555555",
"# c #727272",
"$ c #000000",
"% c #C7C7C7",
"& c #AAAAAA",
5.3 メッセージ を ウィンドウ に書く
・プログラム で、ウィンドウに 日本語メッセージを表示できます。
・実行時に フォントを指定すると、画面に正しく表示されます。
以下に、その手順を示します。
- 23 -
リスト １． MyMessage.c
・リスト１． の MyMessage.exe を実行すると、
画面に、次のメッセージが表示されます。
#include <LEDA/graphwin.h>
"F12 -> select 'text.font', then 'done'"
・F12 キー を押すと、
「ファイル・オープン・ダ
イアログ」が現れます。
int main(){
GraphWin gw("LEDA Graph Editor");
window& W = gw.get_window();
gw.display();
gw.message("F12-> select'text.font',then 'done'");
gw.edit();
//do untile press 'done'
gw.message(" 日本語のメッセージです。");
W.draw_text(250,300," これが読めますか？ ",pink);
gw.edit();
//do untile press 'done'
・ファイル一覧から、’text.font’を選択して「開
く」を押す。
return 0;
}
リスト ２． C:¥temp¥leda_fonts
ファイル名
------------bold.font
button.font
fixed.font
italic.font
text.font
サイズ
-------0 KB
0 KB
0 KB
0 KB
0 KB
・フォント選択ダイアログが現れますので、例え
ば MS 明朝 −＞ 太字 -> 18 の順に選択します。
・次に、アプリケーション・ウィンドウ の右上の
‘done’
をクリックすると、図１．の日本語メッ
セージが現れます。
・F12 キー を押した時に現れる ’leda_fonts’ディレクトリは、通常 ’C:¥temp¥leda_fonts’です。
・’leda_fonts’ディレクトリがない時は、作成して下さい。
（場所は任意です）
そのディレクトリの内容は、リスト２．に示すように、５つのフォント・タイプ のリストです。
これは、ファイル名のみで、サイズが ０ のものを作成して下さい。
5.3 GUI メニュー を 作成
リスト １． MyMenu.c
・LEDA を用いて、図１．のような
各種 GUI 部品 を使えます。
（ demo¥window¥panel_demo.c 参
照 ）
・ボタン のラベルには、以下に示
すように日本語 を使うことが出来
#include <LEDA/window.h>
enum {RESET, QUIT, NEXT};
int do_menu();
void set_color(int n);
window W(900,800);
ます。
int main(){
int n= 0;
W.button(" 次の色 ",NEXT);
W.button(" 終 了 ",QUIT);
W.display();
W.set_line_width(2);
W.message("F12 -> select 'text.font' and ¥
'button.font'");
W.message("< 次の色 > を押して下さい ");
circle c;
int n= 0;
W.del_message();
W.draw_text(50,50, " 円を描いて下さい。¥
(右クリック で終了)");
while(W>>c)
W<<c;
W.message("< 次の色 > を押して下さい ");
}
return 0;
}
図 5.3-1
int do_menu(){
point p;
for(;;){
int k= W.read_mouse(p);
if(k==NEXT ￨￨ k==QUIT){
return k;
}
}
}
void set_color(int n){
static color col[]={black,red,green,blue,yellow,
violet,orange,cyan,brown,pink,green2,blue2,
grey1,grey2,grey3};
W.set_color(col[n % 15]);
}
- 24 -
・リスト１．の MyMenu.exe を実行
前ページの「メッセージをウィンドウに書く」と
同様にして、日本語フォントを設定 する。
・図２．のように、２つのボタン「次の色」
、
「終了」
が表示される。
・
「次の色」をクリックして、次に指示に従って、円を描
く。右クリックして、円を終了する。
・上の操作を繰り返すと、図３．のように、色んな色で
次々と円を描きます。
図 5.3-3
- 25 -
図 5.3-2
第６章
ｙ Files の概要
LEDA の関連商品として、yFiles があります。LEDA は、C++ 環境で用いられるグラフ理論関連のライブラ
リー（クラス・ファイル集合）ですが、yFiles は、Java 環境で用いられるグラフ理論関連のライブラリー
（クラス・ファイル集合）です。
yFiles は、LEDA のグラフ・モジュールのサブ・セットです。さらに、AGD（次章にて説明）のようなレ
イアウト・モジュールの機能が付加されています。
6.1
yFiles のインストール
■１■
Java のインストール
Java を Sun のサイトからダウンロードして、インストールします。 ........ 今後の説明のため、Java
は、F:¥jdk1.3.1 にインストールされているとします。DOS の 環境変数の CLASSPATH に、Java を追加し
ます。
CLASSPATH = F:¥jdk1.3.1¥lib¥tools.jar;
CLASSPATH を追加するのは、Windows95/98 では、Autoexec.bat に 1 行を追加します。WindowsNT の場合
は、
「システムのプロパティ」で、システム環境変数（S) に 項目を追加します。また、このように シス
テム変数に追加しないで、実行する時だけに追加する方法もあります。
（後に説明します）
■２■
yFiles の解凍 と コピー
yFile のCD-ROM の yFilesCD.zip を解凍して、
任意のディ
レクトリにコピーします。今後の説明のため、ｙFiles は、
F:¥math¥yFiles1.3 の下に全てコピーされていると仮定し
ます。
F:¥math¥yFiles1.3 の下に、３つのディレクトリーと２つ
のファイルが見えます。
add-ons￥presentation￥yFiles￥
COPYRIGHT.txt
README.html
■３■
yFiles の実行
yFiles の実行は、DOSのコマンド・モードから実行します。
または、適当なディレクトリー に、バッチ・ファイルを作
成し、 Ｗｉｎｄｏｗｓ から、そのバッチ・ファイル をダ
ブル・クリックすることにより実行する事ができます。
6.2 yFiles の デモ・アプリ の起動 と 使い方
■１■
animated algorithm の デモ
① デモの起動
Windows 環境において、
”F:¥math¥yFiles1.3¥add-ons¥anim” の下の anim.jar を、左マウスで、ダブルク
リックする。または、CLASSPATH が設定されていない環境で起動する場合は、次のバッチ・ファイル”anim．
bat”を作成して
set CLASSPATH=%CLASSPATH%;F:¥jdk1.3.1¥lib¥tools.jar
- 26 -
cd F:¥math¥yFiles1.3¥add-ons¥anim
java -jar anim.jar
Windows 環境において、
”anim．bat” を、左マウスで、ダブルクリックする。そうすると、広いキャンバ
スを持ったメニューが現れる。
② デモ用グラフ図形の作成
← キャンバス上で、左マ
ウスをクリックする
と、上図のように、点（黄
色の B O X ）が作成されま
す。上図のように、12個の
点を作成します。
→
点１の上で左クリックし、
続いて点２の上で左ク
リックすると、上図のよ
うに点１から２に線が引
ける。それを繰り返し、点
と点を任意につなぐ。た
だし、線がクロスしたり
（青色）、孤立した点がな
いようにする。
各辺（edge）に、重みを付けます。
①[Edit] より、<EdgeWeight> を選び
②現れた[Options]で、Type <Random> を左
クリックし、<Distance> を選ぶ。
③最後に、[Options]の[OK] ボタンを押します
各辺（edge）を、無方向にします。
①[Edit] より、<DefaultEdge> を選び
②現れたダイアログで、
[Query] ボタンを押す
③[Basic]->[TargetArrow] を左クリックし、現れ
た線の種類から４つめの線を選ぶ。
③最後にダイアログの[Exit] ボタンを押します
作成した「グラフ図形」を保存します。
①[File] より、<Save> を選び
②現れた[保存]で、適当なディレクトリを選ぶ。
（この例では
F:¥math¥yFiles1.3¥add-ons¥anim¥）
③ファイル名を入力する
④最後に、
[保存] ボタンを押します
- 27 -
左図は、
今回
作成した簡
単なグラフ
図形、
右図は、
サン
プルとして
用意されて
いる複雑な
グラフ図で
す。
（ドイツ
の高速道路
網）
③ デモの実行
あるノード（例えば No.3）よりスタートして、一番スパンの短い経路を選択するデモをアニメーションし
ます。
①[Ａｎｉｍａｔｉｏｎｓ] より、< ＭｉｎｉｍｕｍＳｐａｎｎｉｎｇＴｒｅｅ > を選び
②現れた[Ｏｐｔｉｏｎｓ]で、
[OK]ボタンを押す
③開始するノード（例えばＮｏ．３）を選ぶと、経路選択を開始します。
経路選
択が始まると、関連するプログラムのステップを指示
しながら計算が進行します。計算結果は右図です。
■２■
visual programming の デモ
① デモの起動
Windows環境において、
”
F:¥math¥yFiles1.3¥add-ons¥loop”の下の loop.jar
を、左マウスで、ダブルクリックする。または、CLASSPATH が設定されてい
ない環境で起動する場合は、次のバッチ・ファイル”loop．bat” を作成し
て
set CLASSPATH=%CLASSPATH%;F:¥jdk1.3.1¥lib¥tools.jar
cd F:¥math¥yFiles1.3¥add-ons¥loop
java -jar loop.jar
Windows 環境において、
”loop．bat” を、左マウスで、ダブルクリックする。そうすると、広いキャンバ
スを持ったメニューが現れる。
LOOP 言語 は、ｙＦｉｌｅｓ が提供する プログラム言語です。その特徴 は、
・グラフィカルなフローチャートを描くことができて、
・その フローチャート上で、実行できます。
- 28 -
・そして、実行過程を ビジュアルに表示します。
LOOP 言語 の活用事例としては、
・プログラミングの学習・教育用とか、
・ある モデリングの動作のシミュレーションを行わせる事ができます。
左図のような、簡単なフローチャートを作成します。[x0]、
[x1] の２つのレジ
スターがあります。
’ZERO x1’ は、[x1] をクリアします。
（ [x1] =0 ）
’LOOP x0’−’END’ は、そのループ内を [x0] の値だけ繰り返します。
’INC x1’ は、[x1] の値に ＋ 1 を行います。
左図のフローチャートを、実行すると、結果として
[x1] = [x0]
となります。
次に、上図のフローチャートの作成方法と、その実行方法について説明します。
②
①
②
③
デモ用フローチャートの作成
[Instruction Chooser]で、
’ＬＯＯＰ’を選択する
[Instruction Chooser]で、
’x0’を選択する
メイン・ウィンドウで、
’右クリック’すると、
’insert’
の指示が現れます。
’insert’の枠内で、
’左クリック’すると、
’ＬＯＯＰ’−’ＥＮＤ’のフローが描かれます。
① [Instruction Chooser]で、
’ＺＥＲＯ’を選択する
② ’x1’を 選択する
③ メイン・ウィンドウの’ＬＯＯＰ ｘ０’
の上で、
’右クリック’すると、
’メニュー’が現れます。
’Inser beforet’を選択（’左クリック’）
すると、
’ＺＥＲＯ ｘ１’のフローが描かれます。
① ’INC’ を選択する
② ’x1’を 選択する
③ メイン・ウィンドウの’ＬＯＯＰ ｘ０’
の上で、
’右クリック’すると、
’メニュー’が現れます。
’Inser into Loop’を選択（’左クリック’）すると、
’INC ｘ１’のフローが描かれます。
② デモ用フローチャートの実行
① [x0]のＶａｌｕｅ蘭で、’左ダブルクリック’し、５を入力
（[x0] = 5 となる）
② [Start] を’左クリック’すると、実行メニューが現れる
③ 実行メニューの’開始’
（▼）を押すとフローチャートを実行する。
そして、最終的に [x0] = [x1] となる。即ち、 [x0] = 5 となる。
④ このフローチャートをマクロとして登録できる。例えば、マクロ
名を”MOV X0 X1”とすると、[x0] =
[x1] を計算するマクロとなる
マクロを、いくつか組合わせて、より大きなマクロを作れます。
右図は、マクロ”MOV X0 X1”を用いて、新たにマクロ”ADD X0 X0 X2”を
定義した例です。
（レジスター名はマクロ呼出し時に指定します）
- 29 -
さらに、マクロ”ADD X0 X0 X2”を用いて、新たにマクロ”MULT X0 X1 X2”を定義している様子を図
6.2-1 に示します。図 6.2-2 は、２つのマクロ（”ADD X0 X0 X2”と”MOV X0 X1”
）を展開して表示して
います。
■３■
UML エディターのデモ
① デモの起動
次のバッチ・ファイル”uml．bat” を作成して
set CLASSPATH=%CLASSPATH%;F:¥jdk1.3.1¥lib¥tools.jar
cd F:¥math¥yFiles1.3¥add-ons¥uml
java -jar JarInspector.jar F:¥math¥yFiles1.3¥yFiles¥demo¥yed¥yed.jar
Windows 環境において、
”uml．bat”
を、左マウスで、ダブルクリックす
る。そうすると、５つのパーツを
持ったウィンドウが現れる。
① メニュー・バー： File、View、
Mode、Layout、Options、Help の各
コマンドがある。
② ツール・バー： ’拡大’、
’縮小’
などのツール・ボタンがある。
③ 概観 ビュー： キャンバスに表
示されているイメ−ジの概観を示
す。
④ ツリー・ビュー： JAR ファイル
に含まれるパッケージ、クラスをツ
リー状に表示する。
⑤ キャンバス： ツリー・ビューで、
選択されたノードの詳細を表示す。
② デモの内容
・ツリー・ビューには、’yed.jar’ファイルの構造が表示される。最初は、
’Model’だけが見えます。
・ ’Model’を、クリックすると、それが展開されて、次の６つのパッケージが現れます。
yed、java、y、javax、com、yext
- 30 -
・ 各パッケージは、ツリー構造を持っていて、そのツリーの最後に クラス名が表示される
下の説明図では、分かりやすいように、クラス名は […] の中に記述されています。
・各パッケージの内容は次のようです。
yed … … … … …アプリケーション
y 、yext … … … yFiles の システム
java 、 javax 、com … java から提供される システム
・各パッケージ 間の関連 または クラス間の関連 が矢印で示されます。
6.3
yFiles の サンプル
・ソース の 実行
サンプル・
■１■ GraphDemo の実行
次のバッチ・ファイル（ graph．bat ）を作成して実行する。
cd F:¥math¥yFiles1.3¥yFiles
java -cp "y.jar;." demo.base.GraphDemo
次の出力が表示される。
The nodes of
node index:0
in edges #0
out edges #4
node index:0
node index:0
node index:0
node index:0
the graph
->
->
->
->
node
node
node
node
index:1
index:2
index:3
index:4
node index:1
in edges #1
node index:0 -> node index:1
out edges #3
node index:1 -> node index:2
node index:1 -> node index:3
node index:1 -> node index:4
・・・・・・・・・・・・・・・
図のようなグラフを作成し、各種情報
を、画面に出力する。
グラフは、５つのノード（0 ∼ 4）を持
ち、各ノードは互いに エッジ（方向性
有）で接続されている。
■２■ ListDemo の実行
次のバッチ・ファイル（ List．bat ）を作成して、
cd F:¥math¥yFiles1.3¥yFiles
java -cp "y.jar;." demo.base.ListDemo
”List．bat”を実行すると、以下のような結果が得られる。
各ステップの説明
実行結果（画面の内容）
0 ∼ 19 までの List
を作成する
List elements from front to back
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
0 ∼ 19 までの List
の並びを反転する
List elements from front to back
19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
語句順に並べる
（数字順でない）
Lexicographically sorted list
0 1 10 11 12 13 14 15 16 17 18 19 2 3 4 5 6 7 8 9
0 ∼ 9 までの要素を
取り除く
list after element removal
[10,11,12,13,14,15,16,17,18,19]
10 ∼ 19 までの List2
を作成する
list2 after creation
[10,11,12,13,14,15,16,17,18,19]
List2
の並びを反転する
list2 after reversal
[19,18,17,16,15,14,13,12,11,10]
List と List2 を
結合する
list after splicing
[10,11,12,13,14,15,16,17,18,19,19,18,17,16,15,14,13,12,11,10]
結合された後の
List2（空） を示す
list2 after splicing
[]
■３■ ShortestPath の実行
次のバッチ・ファイル（ shortpath．bat ）を作成して実行する。
cd F:¥math¥yFiles1.3¥yFiles
java -cp "y.jar;．" demo.base.ShortestPathDemo 6 9
- 31 -
・２つの変数は、次のようなパラメータを指定します。
６＝ グラフが持つノード（接点）の数 （ノード ID = ０ ∼ ノード ID = ５）
９＝ グラフが持つエッジ（ 辺 ）の数
・指定された２つのパラメータに従って、ランダムにグラフが自動生成される。
・次に、スタート・ノード（ID= ０） から エンド・ノード（ID= ５） に至る経路の中で最短経路を計算す
る。 計算は、エッジが有方向性の場合と、無方向性の場合について行われる。
・下の例では、 有方向性、無方向性の場合ともに最短経路は、同じでノード IDが ０ --> ２ --> ５ とな
り、その経路距離は ８２．０ となります。 次の出力が表示される。
EdgeCount= 9
node index:0
node index:4
node index:0
node index:2
node index:1
node index:5
node index:3
node index:4
node index:3
->
->
->
->
->
->
->
->
->
node
node
node
node
node
node
node
node
node
ndex:2::69.7
ndex:0::65.0
index:1::92.8
index:5::12.3
index:2::5.6
index:4::99.7
index:4::75.0
index:1::16.3
index:1::31.5
node id:0 -> node index:2 weight = 69.7
node id:2 -> node index:5 weight = 12.3
UNDIRECTED PATH LENGTH = 82.0
=== directed case ===
node id:0 -> node index:2 weight = 69.7
node id:2 -> node index:5 weight = 12.3
DIRECTED PATH LENGTH = 82.0
図のようなグラフを作成し、ノード０ から
ノード５へ行く時の最短経路を求める。
グラフは、６つのノード（0 ∼５）を持ち、各
ノードは互いに エッジ（方向性有）で接続さ
れている。
Auxiliary distance test
Distance from first to last node is 82.0
6.4
yFiles の 概要 について
■１■ yFiles とは
ソフトウェア工学
データベース管理
データベース・モデル
WWW- 可視化
1998: ingen 大学研究プロジェクトグループが Y
プロジェクト開始 .
目標: アニメーション可能なグラフ状構造の可
視化、編集、レイアウトを行う Java のクラス・パッ
ケージの開発
ビジネス・プロセス・エンジニアリング
インターネットのユーザ挙動解析
サイトマップ自動生成 凵 X.
展開: 新会社設立 - yWorks GmbH が2000年９月
に設立された .
■４■ yFiles の特徴
■２■ yFiles について
インターネットに適した Java アプリケーション エディタ／ビューア機能は ...
直感的で容易に習得できます .
のカーネルとなります .
豊富な支援機能を備えています。例えば:
ピュア Java で書かれています .
節点や辺（さらには複数辺ラベルまでも）の自己
２次元グラフ描画の広い範囲にわたるアルゴリズ
ループ ,
ムを提供します .
直交グラフ描画のグリッド格子モード ,
効率がよく効果的な可視化アルゴリズムが使えま
一つのグラフのマルチ・ビュー ,
実行時にローディング可能な拡張パッケージ ,
エディタ／ビューアと拡張パッケージ間のイン
す.
複数のグラフを見やすく配置するための高品質な
アルゴリズムを備えています .
ターラクション , 等 .
■３■ yFiles の特徴
yFiles は以下のような分野のアプリケーションに最 インターフェースは ...
描画属性を完全にサポートします .
適です
- 32 -
■５■ yFiles のメリット
yFiles は、
次の３つのコンポーネントから構成され
yFiles は ...
広範 .
ます。
■７■ 基本コンポーネント
グラフ・アルゴリズムとデータ構造が含まれます。
基本データ構造 (List, Graph, AVL-Tree, ...)
先進 .
使い易い .
柔軟で拡張可能 .
グラフ横断アルゴリズム (Dfs, Bfs)
最短経路アルゴリズム (Dijkstra, Bellmann-Ford)
最小木アルゴリズム (Prim)
最新の設計手法 .
■６■ 使用例
ネットワーク・フロー（流れ） (Max-Flow, MinCost-Flow)
例１： ビジュアルなループプログラムのエディタと
グラフ連結問題 (connected, biconnected)
シミュレータ .（”6.2 □２□ Visual Programming
幾何アルゴリズム(凹含 , 多角形の交差)
のデモ”を参照）
例２： クイックソートアルゴリズムのアニメーショ
（可視化）コンポーネント
ビュワー（
■８■ ビュワー
ン.
ビュワーは、グラフを表示したり、編集する GUI コ
ンポーネントです。
モデル・ビュー制御のデザイン・パターンに沿う
強力で、直感的で、理解し易い
Java2D API と Swing に基づいています
豊富な機能をサポートします（例えば、
）
ズーム、パン、../cut,copy,paste
直交グラフ描画に対する格子モード
グラフのマルチ・ビュー対応
全グラフ属性をサポート
■９■ レイアウト
（配置）コンポーネント
レイアウト（
自動的に最適なグラフ描画を行います。
多様なレイアウト・スタイルを提供します
直交配置、階層配置、木構造配置、環状配置
力学バランス・モデル
最適自動ラベル配置が可能
強力なカスタマイズが可能
機能の拡張が容易です
例３
： 生化学的経路 .
例３：
例４
： UML ダイアグラム
例４：
（”6.2 □３□ UML エディターのデモ”を参照）
- 33 -
○ 直交（Orthogonal）レイアウト
○ 階層（Hierarchic）レイアウト
○ 環状（Circular）レイアウト
- 34 -
○ ツリー（Tree）レイアウト
○ 組織（Organic）レイアウト
○ Force Directed レイアウト
○ ランダム（Random）レイアウト
○ Nested Graph レイアウト
＊ノードにグラフを割当てることができ、その
グラフを展開した状態でも表示できる
- 35 -
6.5
yFiles の 活用事例
■１■
WEB ショッピングの傾向分析
図 6.5-1
・右図の iCandyは、yFiles
の強力なレイアウト機能を
生かしたアプリです。
・WEB上のショッピング・サ
イトのログ・ファイルを取
込み、ユーザの購買傾向を
ビジュアルに表示します。
・各ノードは、CD アルバム
のタイトルとアーティスト
名を示します。
・エッジは、WEBサイト上で
の購買者を示し、その線幅
は購入数を示します。
・エッジの矢印（→）は、購
買の向きを示す。
■２■
WEB サーバー上のグラフ
・アプリをブラウザより利用
サーバー上のグラフ・
図 6.5-2
・図 6.5-2 は、WEB サーバー上で、yFiles で
開発したアプリ（トポロジカル・ソート）を
走らせています。
次の技術を利用しています。
・WEBサーバー（WebLogic、Tomcat、Resin等）
・JSP
・実行モジュールは JavaBean として呼出
← 図 6.5-3
・左の図 6.5-3 は、yFiles
で開発したアプリ（最短経
路探索）を、アプレットと
して走らせています。
・このように、WEB ブラウザから yFiles で開発したアプリを利用する事により、大変手軽にグラフ・ア
ルゴリズムを活用することが出来ます。
- 36 -
■３■
マセマティカよりグラフ機能を活用
マセマティカ（Mathematica）では、
JLink モジュールを通して、Java の
クラスを呼出すことができます。このよ
うにして、マセマティカから yFiles で
開発したサンプル・アプリ（グラフ描画）
を呼出し、実行しているようすが 右図
に示されています。
- 37 -
第７章
ＬＥＤＡ の 発展
7.1 多くのユニークな追加モジュール群
LEDA は、
「データ構造・計算アルゴリズム」、
「グラフ・アルゴリズム」
、
「幾何図形アルゴリズム」の３つ
のアルゴリズム用のライブラリーで構成されますが、その機能を補うための豊富なモジュール群がありま
す。
■１■ AGD
（version 1.2
） < レイアウト
・マネージャ >
AGD（
1.2）
レイアウト・
・ＬＥＤＡで作成されたグラフ・データを Windowsオブジェクトとして可視化する。
さらに、そのレイアウトを解析して、構造化されたシンプルな構成に再構築する。次のようなレイアウト・
タイプがあります。
１．直行レイアウト：
要素を接続する線は、水平または垂直線で構成されできるだけ交差を少なく配置する。
２．階層レイアウト：
要素を接続する線を、ツリー上に構成して、要素の階層を明確にする。
３．混合モデル・レイアウト：
直行レイアウト と 階層レイアウト の両方の性質をもつ配置を行う。
■２■
CGAL(version 2.3) < 高機能
・幾何図形アルゴリズム >
高機能・
・LEDA の３ D アルゴリズムについて、その機能をさらに強化
・次のような応用分野があります。
計算幾何、地形情報システム（ＧＩＳ）
、ＶＲ、３Ｄ形状認識システム
■３■
BALL(1.0 beta) < 分子モデル開発
・検証用アルゴリズム >
分子モデル開発・
・ＤＮＡ、ＲＮＡ、蛋白質 や 分子について、その構造、機能、相互作用 及び 進化
を理解したり、予測するのは、生命科学にとって大変重大なことです。
・BALL は、分子モデル開発・検証のための手順を実施するに必要な全てのツールを 提供します。
・BALL を活用できる分野は、
‘分子生化学の計算’ のような基盤化学に限定されるものではありません。
■４■
yFiles(version 2.1) < グラフ
・アルゴリズム＋レイアウト
・マネージャ >
グラフ・
アルゴリズム＋レイアウト・
・ＬＥＤＡ の グラフ・モジュール のサブ・セットです。
（Java 環境で動作）
さらに、ＡＧＤ のような レイアウト・モジュールの機能が付加されています。
・
「第 6 章 yFiles の概要」を参照下さい。
・WEB サーバーで動作し、WEB ブラウザから利用できるアプリケションを開発できます。
・JLink を通して、Mathematica より モジュールを呼び出すことができます。
■５■
LEDAGraphAlgo(version 1.0) < グラフ
・アルゴリズム >
グラフ・
・ＪＮＩ のインターフェイスを利用して、ＬＥＤＡ のグラフ・モジュールのクラスを yFiles から利用
できる ライブラリーを提供します。
・これを用いることにより、 yFiles から ＬＥＤＡ の殆どの グラフ機能を利用できます。
■６■
yWays(version 1.0) < バイオケミカル
（分子モデル）用の可視化ライブラリ >
バイオケミカル（
・yFiles で開発されたアプリケーションです。 BALL のような統合開発環境ではなくて、分子モデルの可
視化のみを行うための Java 環境用のライブラリです。
- 38 -
7.2 レイアウト
・マネージャを使う
レイアウト・
AGD は、次のような用途に適しています。
・IT、財務ソフト関連。 例えば、柔軟で拡張性のある組織図を手軽に描けます。
・ソフトウェアの開発。 例えば、UML ダイアグラムや ER ダイアグラムを扱えます。
・OR 関連分野。 例えば、ワークフロー・ダイアグラムを優雅に描画できます。
AGD は、次のような機能を提供します。
・グラフの平面化描画（エッジが交差しないように描画する）
・グラフをコンパクトに描画（エッジの長さが出来るだけ最短になるように配置する）
・グラフを簡潔に描画（エッジの交差数が最小になるように配置する）
・エッジの折れ曲がりをできるだけなくすように配置する
・エッジとノードに対して最適なラベリングを行う
■１■
直交レイアウト
図 7.2-2
図 7.2-1
図 7.2-3
AGD（レイアウト・マネージャ）の使用例を示します。例え
ば、在庫管理システムにおいて、各アイテム（仕入、商品、
在庫など）の関連付けを、図 7.2-1 や 図 7.2-2 のように
して、線分で結びます。これらの入力レイアウトに対して、
「直交レイアウト」処理を実行すると、図7.2-3 が得られま
す。各アイテムの相互関連が明瞭に把握できます。
図 7.2-4
図 7.2-5
図 7.2-4 は、
”グラフ・ゼネレータ”にて、
「ランダム平面グラフ」を生
成した結果です。それに対して、
「直交レイアウト」処理を実行すると、
図 7.2-5 が得られます。この出力では、エッジの交差は１つもありません。
- 39 -
図 7.2-6
図 7.2-7
■２■
階層レイアウト
図 7.2-6 は、
「仰裁・申請」ワーク
フローを示します。このワークフ
ローでは、３つの審査部門A,B,C に
て審査が行われ、最終的に次の３つ
の判定がなされます。
1) 申請を受理する
2) 申請を却下する
3) 申請を差し戻す
図7.2-6 では、作業の流れを示す線
分が複雑に入り乱れているが、それ
に対して、
「階層レイアウト」処理を
実行すると、図7.2-7 のように大変
簡素な分かり易いワークフロー・
ダイアグラムが得られます。
図 7.2-8 と 図 7.2-9 は別なサンプルです。
図 7.2-8
図7.2-9
- 40 -
第８章
ＬＥＤＡ の インストール
8.1 Windows 環境
（Microsoft VC++
）
環境（
VC++）
（１）「LEDAで始めるプログラミング」 のセミナー資料 3ページ
Windows 系のインストールの 2 番目の make_demo の実行 について
・make_demo は、DOS のバッチ・ファイルです。その中で、VC++ の nmake や cl 等のコマンドを呼出
しますが、VC++ 用の環境変数、コマンド・パスが設定されていないと、次のエラーを出します。
コマンドまたはファイル名が正しくありません．
・・・・・
・VC++6.0 は、通常のインストールでは、DOS 環境 で使用できるような設定にはなっていません。
Windows の GUI 環境 では、後に述べる操作により使用できます。
・DOS 環境 で、VC++6.0 を使用するための設定
１．
”C：¥Program Files¥Microsoft Visual Studio¥VC98¥Bin¥Vcvars32.bat” を、作業ディレクトリにコ
ピーする。
（VisualStdio6.0 が、C：ドライブに、デフォルトで、インストされていると、仮定しています）
例えば、LEDA を、C：ドライブに、デフォルトで、インストしたと、しますと、
＞ CD ¥Algorithmic Solutions¥Leda-4.2.1
＞ COPY "C：¥Program Files¥Microsoft Visual Studio¥VC98¥Bin¥Vcvars32.bat" C：
２．＞ Vcvars32
（バッチの実行）
Setting environment for using Microsoft Visual C++ tools.
（左のメッセージを出力します）
・その後、make_demo を実行すると、demo¥ 以下の各サブ・ディレクトリの下に、実行モジュールが作成
されます。
（２） SSEホームページに置いてあるサンプル curves.cpp の実行について
・次の手順で、コンパイルして下さい。
＞ Vcvars32
（バッチの実行、最初に１回実行すればＯＫです。 autoexec.bat での実行も可能です。
）
＞ cl -c -nologo -MLd -I..¥incl curves.cpp
＞ cl -nologo -MLd curves.obj user32.lib gdi32.lib comdlg32.lib shell32.lib advapi32.lib
wsock32.lib ..¥¥libW.lib ..¥¥libP.lib ..¥¥libG.lib ..¥¥libL.lib
・LEDA のインスト・ディレクトリ（¥Algorithmic Solutions¥Leda-4.2.1）の下に、サブ・ディレクトリ’
samples¥’を作り、
その下に、curves.cpp を置いたと、仮定しています。
- 41 -
・”libW.lib
libL.lib”は、ＬＥＤＡ で必要とされる’グラフィック・ツール・ラ
libW.lib libP.lib libG.lib libL.lib
イブラリ’です。
その他は、システム側で必要とされるライブラリです。
・上記のように、直接キーボードより、コマンドを入力するより、バッチ・ファイル もしくは Ｍａｋｅ
ｆｉｌｅ を作成した
方が、何回も コンパイルする時は、効率的です。
8.2 Windows 環境
（Borland BCC
）
環境（
BCC）
（1）LEDA のインストール
・LEDA-4.3-win32-bcc551-complete.exe … 15.1MB (15,890,324)
をダブル・クリックすると、インストーラが起動されます。インストール・ディレクトリを指定して続
行します。
・以下の説明では、LEDA は C:¥Leda-4.3B
あるとします。
に、Borlanc C++ は C:¥bcc55
に、インストールして
・次のライブラリ（太字 ） を コピーする。
> cd C:
:¥Leda-4.3B
> copy libGeoW_lib.lib libGeoW.lib
・C:
:¥bcc55¥Bin¥bcc32.cfg を編集する。
[ bcc32. ｃｆｇ の内容 ] …… 太字 を追加
-I"C:
: ¥bcc55¥include;C:¥Leda-4.3B¥incl "
:¥bcc55¥lib;C:
:¥bcc55¥lib¥PSDK;C:¥Leda-4.3B "
-L"C:
（2）Borland 用の設定
・Borland 用のバッチ・ファイルを作成
:¥bcc55 に置く
[ bcc55.bat の内容 ] …… C:
set PATH=%PATH%;C:
:¥bcc55¥Bin
バッチの実行は、最初に１回実行すればＯＫです。 autoexec.bat での実行も可能です。
・プログラムのコンパイルは、次の２通りの方法があります。
１．バッチ・ファイル を用いて実行
２．Makefile を用いて実行
[ bcc_make.bat の内容 ] …… C:
:¥bcc55¥Bin に置く
if "%2" == "" goto :help
if "%1" == "-L" goto :L
if "%1" == "-G" goto :G
if "%1" == "-P" goto :P
if "%1" == "-W" goto :W
- 42 -
if "%1" == "-D3" goto :D3
if "%1" == "-Geo" goto :Geo
:L
bcc32 -P -w- %2.c libL.lib
goto :end
:G
bcc32 -P -w- %2.c libG.lib libL.lib
goto :end
:P
bcc32 -P -w- %2.c libP.lib libG.lib libL.lib
goto :end
:W
bcc32 -P -w- %2.c libW.lib libP.lib libG.lib libL.lib
goto :end
:D3
bcc32 -P -w- %2.c libD3.lib libW.lib libP.lib libG.lib libL.lib
goto :end
:Geo
bcc32 -P -w- %2.c libGeoW.lib libD3.lib libW.lib libP.lib libG.lib libL.lib
goto :end
:help
echo [使用法] bcc_make -L/G/P/W/D3/Geo app
echo
goto :bat_end
:end
del %2.obj
:bat_end
[ Makefile の内容 ] …… ソース・ファイルのある所に置く
LFLAGS = $(WFLAG)
DFLAGS = -DWINMAIN
DOSLIB = libD3.lib libW.lib libP.lib libG.lib libL.lib $(XLIB)
DOSLIB1 = libGeoW.lib
WINDOW_APP = 1
!include ..¥Make.pro
[ Makefile.dos の内容 ] …… ソース・ファイルのある所に置く
DOSLIB = libD3.lib libW.lib libP.lib libG.lib libL.lib $(XLIB)
!include ..¥Make.pro
[ Make.lst の内容 ] …… ソース・ファイルのある所に置く
ソース・ファイル名の一覧を記入して下さい。
PROGS = ¥
test_draw$(e) ¥
test_integer$(e) ¥
test_graph$(e)
（3）プログラム の コンパイル
- 43 -
・ソース・ファイルは、どこにあっても OK ですが、説明のため、次のディレクトリに置くとします。
C:
:¥Leda-4.3B¥demo¥my_test （ my_test は、新規に作られたディレクトリです ）
次の３つのソース・ファイルがあるとします。
<1>．test_draw.c
<2>．test_integer.c
<3>．test_graph.c
…… ウィンドウ上に、点、直線、円、多角形を描く。
…… 桁数制限なしで、１万桁の計算をする。
…… グラフ構造の問題（例えば、最短経路の計算）を解く。
まず、bcc55.bat を実行する。次に、下記の[1] [2] のいずれかを選択します。
[１]．バッチ・ファイル を用いて実行
次の６通りのオプションがあります。下は、上のオプション機能を含みます。すなわち、
-G は、-L のオプション機能 （integer や rational などの数値の計算） を含みます。
> bcc_make -L < ソース・ファイル >
> bcc_make
> bcc_make
> bcc_make
> bcc_make
> bcc_make
ブラリ
-G < ソース・ファイル >
-P < ソース・ファイル >
-W < ソース・ファイル >
-D3 < ソース・ファイル >
-Geo < ソース・ファイル >
…… integer や rational などの数値の計算をする
…… グラフ構造を扱う
…… 平面幾何ライブラリ
…… グラフィック・ツール ライブラリ
…… ３次元幾何ライブラリ
…… さらに機能を強化した幾何用グラフィック・ツール ライ
どのオプションを選んで良いか分からなければ、-Geo を選んで下さい。コンパイルは正しく完了します
が、最適なオプションを選んだ場合に比べて、実行ファイルが少し大きくなります。
先の３つの ソース・ファイル に対しては、次のようになります。
> bcc_make -W test_draw
> bcc_make -L test_integer
> bcc_make -G test_graph
[２]．Makefile を用いて実行
・Makefile、Makefile.dos、Make.lst は、ソース・ファイルと同じディレクトリに置いて下さい。
また、１つ上のディレクトリには、Make.pro が必要です。もし、Make.pro がなければ、
C:
:¥Leda-4.3B¥demo¥Make.pro をコピーして使って下さい。
・Makefile は ２つあり、次のように使い分けます。
> make < ソース・ファイル >.exe
> make -f Makefile.dos < ソース・ファイル >.exe
…… ウィンドウを使ったアプリ
…… コマンド・モードのままで実行されるアプリ
target が
・< ソース・ファイル > 名 は、Make.lst に追加しておいて下さい。一覧の中にないと、”target
見つかりません”というエラーが出ます。
先の３つの ソース・ファイル に対しては、次のようになります。
- 44 -
> make test_draw.exe
> make -f Makefile.dos test_integer.exe
> make test_graph.exe
8.3 Windows 環境
（Cygwin g++
）
環境（
g++）
省略（[email protected] へお問合せ下さい。）
8.4 Linux / Unix 環境
（１） Leda のインストール について
・適当なディレクトリーにて、モジュールを展開する
＄ cd /usr/local
＄ tar xvfz LEDA-4.2.1-i386-RedHat6.2-g++.tgz
または、
$ unzip LEDA-4.2.1-i386-RedHat6.2-g++.zip
$ gzcat LEDA-4.2.1-i386-RedHat6.2-g++.zip ￨ tar xvf 'gzcat' の代わりに 'gunzip -c' or 'gzip -cd' でも可
・LEDA-4.2.1-i386-RedHat6.2-g++/Install/unix.txt の内容を参考にして下さい
・LEDAROOT と PATH の設定を行います。例えば、.bachrc に、次の２∼３行を追加します。
export LEDAROOT=/usr/local/LEDA-4.2.1-i386-RedHat6.2-g++
export PATH=$PATH:$LEDAROOT/Manual/cmd
export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:$LEDAROOT （必要に応じて）
・LEDAROOT と PATH の設定を有効にします。例えば、再ログインするか、次を実行する。
＄ ． /.bashrc
・システム・ライブラリを作成する
＄ cd $LEDAROOT
＄ make shared
（２） サンプル の make について
・多くのサンプルがあります。 必要な個所だけ make できます。 全てを make するには、
＄ cd $LEDAROOT
＄ make xlman
＄ make demos
（デモ用のメニューです。必要に応じて実行）
（３０ 分ほどかかります）
・場合によっては、demo/ 及び demo_cout/ の下の Make.pro を、編集する必要があります。
次の２箇所です。必要に応じて、参考にして下さい。
１．（旧)
LROOT = ../..
- 45 -
（新） LROOT =/usr/local/LEDA-4.2.1-i386-RedHat6.2-g++
２．（旧) XLIB_PATH = -L/opt/X11R6.3/lib
（新） XLIB_PATH = -L/usr/X11R6/lib
（３） サンプル の 実行 について
・demo/ 及び demo_cout/ の下に、多くのサブ・ディレクトリーがあり、その中に実行ファイルがありま
す。
・＄xlman を実行すると、デモ用の 「メニュー」が、表示されます。
マウスの左ボタンで、
「Run」 をクリックすると、サンプルのツリーがポップアップしますので、
任意の 「サンプル」を選択してください。
・＄xlman 「メニュー」の 「．C」 をクリックすると、サンプルのツリーがポップアップしますので、
任意の 「サンプル」を選択してください。 その ソース・ファイルが編集できます。
（４） ユーザ用の 作業環境 について
$LEDAROOT/-+--demo/---+--Make.pro
Make.pro
￨
+--animation/---+--Makefile
Makefile
￨
￨--Make.lst
Make.lst
￨
￨--demo_cout/
+--user/---+--Make.pro
Make.pro
+--geowin.c
+--test1/-------+--Makefile
Makefile
￨--Make.lst
Make.lst
￨--mytest1.c
+--mytest2.c
・例えば、＄LEDAROOT の下に、user/ を作り、さらに下に、test1/ を作り、user/test1/ で作業する場
合を
想定します。次の３つのファイルをコピーまたは、作成して下さい。
＄ cd $LEDAROOT; cp demo/Make.pro user
＄ cp demo/animation/Makefile user/test1
＄ cd user/test1; vi Make.lst
----------------------------------PROGS = ¥
mytest1$(e) ¥
mytest2$(e)
----------------------------------・mytest1.c mytest2.c をコンパイルするのは、次を実行して下さい。
＄ cd user/test1; make
（５） その他 について
- 46 -
・また、弊社の HomePage に、参考資料がありますので、是非ご覧下さい。
http://www.sse.co.jp/leda/index.html −＞「関連ファイルダウンロード」
Install.zip ･･････ LEDA インストール・ガイド
LEDA.zip
･･････ LEDA セミナー用サンプル （2001.11.20 実施）
・myLEDA.ppt を実行してください。
・各シートの中の 「青い Box」 を左クリックすると、関連するサンプルが起動します
Source.zip ･･････ myLEDA.ppt の サンプルのソース・ファイル
- 47 -
第 1 版： 2003 年 7 月 18 日 発行
- 48 -