グラフアルゴリズムの可視化 数理科学コース　福永研究室 高橋　優子 2018/12/29

目次 研究背景・目標 ダイクストラ法 クラスカル法 OpenGLを用いた実装 まとめ 2018/12/29

OpenGLを用いて 三次元のグラフアルゴリズムを可視化 1.研究背景・目標 グラフアルゴリズムの学習 C言語にてダイクストラ法・クラスカル法を実装 処理結果をPGM形式にして出力 OpenGLを用いて 三次元のグラフアルゴリズムを可視化 結果だけでなく過程も見えるようにする 2018/12/29

2.ダイクストラ法 2.1 ダイクストラ法とは Edsger Wybe Dijkstra による(1959) 2.1　ダイクストラ法とは Edsger Wybe Dijkstra による(1959) グラフ理論における最短経路問題を解く手法 スタートノードからゴールノードまでの最短距離を求める ダイクストラ法の利用先 カーナビゲーションの経路探索 鉄道の経路案内　など 今回はゴールノードを指定しない 全ノードへの最短距離を求められる 2018/12/29

2.ダイクストラ法 2.2 アルゴリズム 全ノード間のコスト(距離)を＋∞に初期化し さらに状態を「未使用」としておく. 2.2　アルゴリズム 全ノード間のコスト(距離)を＋∞に初期化し さらに状態を「未使用」としておく. 全ノードの座標と, 辺の有無とをランダムに決定し 辺がある場合はその長さをコストとする. また, スタートノードSを指定する. 1 3 4 S 2 【現時点でのコスト】 ノード１…１ ノード２…３ ノード３…＋∞ 2018/12/29

2.ダイクストラ法 2.2 アルゴリズム ③ Sからのコストが最小となる未使用ノードXを探す. 【現時点でのコスト】 ノード１…１（確定） 2.2　アルゴリズム ③　Sからのコストが最小となる未使用ノードXを探す. また, Xにつながる全てのノードYに対し, 「Yの現在のコスト」＞（「X→Yの距離」＋「Xのコスト」） を満たした場合, Yのコストを更新する. アルゴリズムを終了する． 1 3 4 S 2 【現時点でのコスト】 ノード１…１（確定） ノード２…２（コスト更新） ノード３…５（コスト更新） 2018/12/29

2.ダイクストラ法 2.2 アルゴリズム ③ Sからのコストが最小となる未使用ノードXを探す. 【現時点でのコスト】 ノード１…１（確定） 2.2　アルゴリズム ③　Sからのコストが最小となる未使用ノードXを探す. また, Xにつながる全てのノードYに対し, 「Yの現在のコスト」＞（「X→Yの距離」＋「Xのコスト」） を満たした場合, Yのコストを更新する. アルゴリズムを終了する． 1 3 4 S 2 【現時点でのコスト】 ノード１…１（確定） ノード２…２（確定） ノード３…５ 2018/12/29

2.ダイクストラ法 2.2 アルゴリズム ③ Sからのコストが最小となる未使用ノードXを探す. 【現時点でのコスト】 ノード１…１（確定） 2.2　アルゴリズム ③　Sからのコストが最小となる未使用ノードXを探す. また, Xにつながる全てのノードYに対し, 「Yの現在のコスト」＞（「X→Yの距離」＋「Xのコスト」） を満たした場合, Yのコストを更新する. アルゴリズムを終了する． 1 3 4 S 2 【現時点でのコスト】 ノード１…１（確定） ノード２…２（確定） ノード３…５（確定） 2018/12/29

2.ダイクストラ法 2.3　実装 ノードの構造体 2018/12/29

2.ダイクストラ法 2.3　実装 確定ノード決定・コスト更新 確定ノード決定 コスト更新 2018/12/29

3.クラスカル法 3.1 クラスカル法とは Joseph Kruskal による(1956) グラフ理論における最小全域木問題を解く手法 3.1　クラスカル法とは Joseph Kruskal による(1956) グラフ理論における最小全域木問題を解く手法 全てのノードを閉路が含まれないように結合し, 辺の重みの総和が最小となるような木を求める. 貪欲アルゴリズムの一種 2018/12/29

3.クラスカル法 3.2 アルゴリズム グラフの各頂点がそれぞれの木に属するように 森（木の集合） F を生成する. 3.2　アルゴリズム グラフの各頂点がそれぞれの木に属するように 森（木の集合） F を生成する. グラフの全ての辺を含む集合 S を生成する. 11 4 7 8 1 14 6 c e d a b 2018/12/29

3.クラスカル法 3.2 アルゴリズム ③ S が空集合になるまで以下を繰り返す. S から重みが最小の辺を削除する. 3.2　アルゴリズム ③ S が空集合になるまで以下を繰り返す. S から重みが最小の辺を削除する. その辺が2つの木を連結するものならば それを森に加え, 2つの木を1つにまとめる. そうでない場合は単に捨てる. 11 4 7 8 1 14 6 c e b d a 2018/12/29

3.クラスカル法 3.2 アルゴリズム ③ S が空集合になるまで以下を繰り返す. S から重みが最小の辺を削除する. 3.2　アルゴリズム ③ S が空集合になるまで以下を繰り返す. S から重みが最小の辺を削除する. その辺が2つの木を連結するものならば それを森に加え, 2つの木を1つにまとめる. そうでない場合は単に捨てる. 11 4 7 8 1 14 6 c e b d a 2018/12/29

3.クラスカル法 3.2 アルゴリズム ③ S が空集合になるまで以下を繰り返す. S から重みが最小の辺を削除する. 3.2　アルゴリズム ③ S が空集合になるまで以下を繰り返す. S から重みが最小の辺を削除する. その辺が2つの木を連結するものならば それを森に加え, 2つの木を1つにまとめる. そうでない場合は単に捨てる. 11 4 7 8 1 14 6 c e b d a 2018/12/29

3.クラスカル法 3.2 アルゴリズム ③ S が空集合になるまで以下を繰り返す. S から重みが最小の辺を削除する. 3.2　アルゴリズム ③ S が空集合になるまで以下を繰り返す. S から重みが最小の辺を削除する. その辺が2つの木を連結するものならば それを森に加え, 2つの木を1つにまとめる. そうでない場合は単に捨てる. 11 4 7 8 1 14 6 c e b d a 2018/12/29

3.クラスカル法 3.3　実装 辺の構造体 2018/12/29

3.クラスカル法 3.3　実装 最小経路を発見・木を結合 重みの配列をソート 最短経路発見 2018/12/29

4.OpenGLを用いた実装 4.1　ノードの描画 例：ダイクストラのノード描画 不確定ノードは水色 確定ノードは青 2018/12/29

4.OpenGLを用いた実装 4.2　エッジの描画 例：クラスカルの辺 最短経路は黄色 使ってない経路は水色 2018/12/29

4.OpenGLを用いた実装 4.3　視点変更 図を回転表示するときの工夫 視点の位置によって 画面の上方向を変える 2018/12/29

4.OpenGLを用いた実装 4.4 ダイクストラ ランダムに ノードを10個生成 エッジを ランダムに生成 黄色は スタートノード 4.4　ダイクストラ ランダムに ノードを10個生成 エッジを ランダムに生成 黄色は スタートノード 2018/12/29

4.OpenGLを用いた実装 4.4 ダイクストラ マウスを クリックするごとに １ステップ進める 確定ノードは 青く塗る 4.4　ダイクストラ マウスを クリックするごとに １ステップ進める 確定ノードは 青く塗る 使用するエッジは 黄色く塗る 2018/12/29

4.OpenGLを用いた実装 4.4　ダイクストラ 全てのノードへの最短経路を 見つける 2018/12/29

4.OpenGLを用いた実装 4.4　ダイクストラ キーボード操作によって回転 2018/12/29

4.OpenGLを用いた実装 4.4　ダイクストラ キーボード操作によって拡大・縮小 2018/12/29

4.OpenGLを用いた実装 4.5 クラスカル ランダムにノードを10個生成 全てのノードを つなぐエッジを生成 4.5　クラスカル ランダムにノードを10個生成 全てのノードを つなぐエッジを生成 道を増やすため さらにランダムに エッジを生成 2018/12/29

4.OpenGLを用いた実装 4.5 クラスカル マウスを クリックするごとに １ステップ進める 確定エッジを 黄色く塗る 4.5　クラスカル マウスを クリックするごとに １ステップ進める 確定エッジを 黄色く塗る 2018/12/29

4.OpenGLを用いた実装 4.5 クラスカル マウスを クリックするごとに １ステップ進める 確定エッジを 黄色く塗る 4.5　クラスカル マウスを クリックするごとに １ステップ進める 確定エッジを 黄色く塗る 2018/12/29

5.まとめ 苦労したこと 工夫したこと OpenGLの処理に合わせたプログラムの分割. 図を回転させる際の視点の設定. 図を見やすくするために, ランダムに定める ノードの間隔を調整した. 2018/12/29