塩田先生のグラフ描画ツール README
動作環境
- Microsoft Windows XP/Vista で動作確認済み。
ただし .NET Framework のインストールが必要な場合があります。
ファイル概要
- readme.html : このファイル
- DrawGraph.exe : 描画ツール本体
- DrawGraph.conf : オプション保存ファイル
- *.dat : サンプルグラフのデータファイル
- *.eps : EPS ファイルのサンプル
- *.tex : TeX ソースファイルのサンプル
主な機能
グラフ選択 /
アニメーション /
グラフ演算 /
グラフ問題
表示 /
入出力 /
迷路 /
オプション /
追加機能
開く
保存してあるグラフを開くことができます。
グラフの種類
コンボボックスからグラフ名を選択し必要なパラメータを入力して
「基本描画」ボタンをクリックするとグラフを描画します。
ランダムなグラフでは「辺（弧）の比率」とは各辺ごとの発生確率（％）を表していて、
例えば完全グラフの辺数に対する比率を表しているわけではありません。
- 頂点のシャッフルアニメーション
- スプリング法による描画アニメーション
頂点間には斥力が、辺・弧にはばねの力が働くと考えてグラフを描画します。
パラメータを変えることができます。
- ３Ｄスプリング法による描画アニメーション
乱数で z 座標を与えてグラフを３次元に持ち上げてスプリング法を実行します。
プラトングラフの描画などに適しています。
- 広さ優先探索 / 深さ優先探索アニメーション
根とする頂点をクリックすると探索が始まります。
広さ優先探索では最新レベルを青色で、
深さ優先探索ではバックトラックを青色で表します。
- 頂点の追加 / 削除
追加・削除は作業位置でクリックします。
- 頂点の移動
フリーハンドで移動するには直接頂点をドラッグします。
ボタンをクリックすると座標を指定して移動させることができます。
- 辺・弧の追加 / 削除 / 縮約
頂点をクリックして作業対象の辺・弧を指定します。
縮約は１回目に指定した頂点を２回目に指定した頂点に重ねるように描画します。
- 補グラフ表示
- 無向グラフの有向グラフ化
- 重み設定 / 変更
重みをクリックすると重み変更画面が現れます。
- 最短路問題
始点と終点をクリックすると探索が始まります。
- オイラー性判定
オイラー・半オイラーの場合はアニメーションで一筆書きを表示します。
ただし辺・弧数が多い場合は時間が掛かりますので、
確認画面でキャンセルすることができます。
（アニメーションが始まるとキャンセルはできません。）
- 平面性判定
別ウィンドウが開き、
平面的な場合には領域に拡張パスを加えて平面グラフとして描く手順が表示されます。
（平面グラフとして描画する機能はありません。）
- 最大フロー
入口と出口をクリックすると最大フローを表す有向グラフを表示します。
- 彩色多項式と彩色数
別ウィンドウが開き、彩色多項式と彩色数を表示します。
再帰的プログラムを用いていますのでグラフが大きいほど時間が掛かり、
更に大きいときはバックグラウンド処理の過程でエラーを起こして答えが出ないことがあります。
- 隣接行列・隣接リスト表示
- 頂点番号表示 On / Off
表示位置は頂点の外側/左上/真上が選択できます。
- ファイル入出力
描画したグラフを保存したり（保存→データ保存）、
保存したファイルを開いたり（開く）することができます。
スプリング法のパラメータも保存されます。
- EPS ファイル出力
保存→EPS保存で、TeX に画像を貼り付けられるよう、EPS ファイルとして保存します。
破線設定もできます。（ただし1種類だけ。画面上では描画の都合上オレンジ色で表示します。）
- 一段階戻る / 進む
３２段階まで履歴を残しています。
頂点の追加・削除・移動、辺（弧）の追加・削除・縮約は１回の操作で、
重みの変更は「OK」ボタンをクリックした時点で一段階とします。
最大フローでは元のグラフを一段階前に保存しています。
- 迷路
最大３０×３０のランダムな迷路を作成し、解を表示します。
- オプション
- アニメーションの描画速度のレベル
- 迷路のサイズ
- EPS 出力の大きさ（A4サイズ一杯、1/2, 1/3, 1/4 の4種類。）
を指定・保存できます。
- 追加機能で次の操作ができます。
- カット点と橋の表示
- 上下反転・左右逆転、回転
- 頂点の円形配置
頂点を円形に再配置します。
- 円形に頂点追加
半径と個数を指定して頂点を追加します。
既存の頂点と重なる場合は少し位置をずらして配置します。
- 実線/破線反転
デフォルトで描けるグラフ
- 完全グラフ
- 完全二部グラフ
- 空グラフ（円形配置、格子配置）
- 閉路
- 車輪
- 星グラフ
- n 次元立方体グラフ
- ピータスングラフ
- プラトングラフ（正四面体、立方体、正八面体、正十二面体、正二十面体）
- 格子（重み付き、有向グラフもあり）
- 二分木
- ランダムグラフ（重み付き、有向グラフもあり）
- ランダムなオイラー・半オイラーグラフ
- ランダムな平面グラフ
データファイルの形式
- テキストファイルとして次のデータが１行に数字ひとつずつ書いてあります：
- 頂点数
- 辺（弧）数
- ループを持つか否か（０：持つ、１：持たない）
- 重みつきか否か（０：重み無し、１：重み付き）
- 有向グラフか否か（０：無向、１：有向）
- 隣接行列の成分
- 頂点の x 座標・y 座標
- スプリング法の引力・斥力
- 破線指定した辺・弧は隣接行列の成分を負にして記録してあります。
EPS ファイルの形式
- 次の Postscript 命令が書いてあります。
- ヘッダ
- 頂点の円を描く命令
- 頂点番号のテキストを書く命令（頂点番号表示 On の場合）
- 辺を表す線分を書く命令（無向グラフの場合）
- 弧を表す線分・三角形を書く命令（有向グラフの場合）
- 辺・弧の重みのテキストを書く命令（重み付きグラフの場合）
TeX への取り込み方
- TeX の書き方は sample.tex を参考にしてください。
EPS ファイルは、次のコマンドを覚えるとかなり自在に編集することができます。
（大文字には実際には数字やテキストが入ります。）
- %%BoundingBox: 0 0 560 560
560×560 の矩形領域で描画することを表します。
左下が (0,0) になり、Windows の座標とは上下が逆になることに注意してください。
- %
ヘッダ以外では % 以降は注釈文になります。
- W setlinewidth
線の太さを W pt に指定します。
- /Courier findfont S scalefont setfont
テキストのフォントを指定します。S はフォントの大きさを pt で表します。
フォントの種類は Web などでお調べください。
- newpath X Y R S E arc fill stroke
点 (X,Y) を中心に半径 R の円を角度 S から角度 E まで描きます。
fill は内部を埋めることを表し、fill を書かなければ円周だけを描きます。
- X1 Y1 moveto X2 Y2 lineto stroke
点 (X1,Y1) から (X2,Y2) への線分を描きます。
- X Y moveto A B rlineto stroke
点 (X,Y) から (X+A,Y+B) への線分を描きます。
rlineto は相対座標の意味です。
- X Y moveto (T) show
点 (X,Y) を左下に持つ箱にテキスト T を表示します。
- X Y moveto A1 B1 rlineto A2 B2 rlineto closepath fill stroke
点 (X,Y), (X+A1,Y+B1), (X+A1+A2,Y+B1+B2) を頂点とする三角形を塗りつぶします。
closepath は閉じた多角形を描くことを表し、点を増やせば四角形、五角形... になります。
絶対座標で頂点を指定するときは rlineto の代わりに lineto を使います。
- [A B] 0 setdash
この行以降の線分描画では (A pt の実線)＋(B pt の空白) を繰り返す破線を用いることを表します。
引数を増やして [A1 B1 A2 B2] 0 setdash のようにすると
(A1 pt の実線)＋(B1 pt の空白)＋(A2 pt の実線)＋(B2 pt の空白)
のようにパターンを変えることができます。
- [] 0 setdash
この行以降は実線に戻します。
- moveto, lineto, rlineto は to が付いているので前置詞のように思いがちですが、
座標の後ろに書くのでお間違えありませんように。
開発環境
- Visual Basic 2005 Express Edition
著作権
- 著作権はわたくし塩田研一が保有しています。
謝辞
- 高知大学理学部情報科学教室の岡本 竜 先生にはマルチメディア技術を始め
数限りないアドバイスを頂きました。ここに感謝の意を表します。
戻る