ソフトウェア演習Ⅲ〔課題 5:トポロジカル・ソーティング〕青野雅樹

ソフトウェア演習Ⅲ〔課題 5:トポロジカル・ソーティング〕青野雅樹
以下の問題に対する解答を、Java 言語でのプログラムを作成し、プログラムと実行結果
（kadai5.txt）、ならびに自分で作成した DAG データ【CSV ファイル形式（後述例参照）】
（myDAG.csv）をつけて Moodle にアップロードせよ。締め切りは 11 月 11 日（火）ま
でとする。
巡回のない有向グラフ（DAG: Directed Acyclic Graph）G=(V,E)が与えられたとき、グ
ラフ G に対するクラスを作成し、トポロジカル・ソーティングを行うプログラムを作成せ
よ。入力データは以下に述べる 2 種類を使うこと。
(1) http://www.kde.cs.tut.ac.jp/~aono/data/DAG 以下に幾つかの DAG データを
CSV フォーマット（UTF-8 符号）で置いている。各自適当な１つのデータを選択し、
これを読み込み、トポロジカル・ソーティングを行うこと。
(2) さらに、各自で 10 ノード以上、10 エッジ以上の DAG を後述のファイル形式で作成
し、そのデータファイルでも実行すること。
【コメントとヒント】
右図に DAG の例（ただし、「腕時計」のような孤立ノードのサイクルは無害なので許し
ている）を示しています。これはあるサラリーマンが朝起きて身支度をする手順をしたもの
と仮定しています。ノード間の有向グラフの関係は、どちらを先に身に着けるかを表してい
ます。DAG で与えられるグラフには、このような順序（半順序）が埋め込まれていますが、
自由度があることもわかるかと思います。トポロジカル・ソーティングでは、これにある適
当な順序を与えるアルゴリズムを作ることになります。
実装例の考え方を紹介します。DAG の場合、必ずノード（頂点）集合 V の中に、（その
ノードからは有向エッジが出ない）終端ノード（terminal node with no outgoing edge）
が存在します。まず、このようなノードを見つけます。図では「くつ」や「上着」などが終
端ノードの例です。次に終端ノードへのエッジを削除します。この操作を反復します。見つ
かった終端ノードは、たとえ
ば「スタック」にプッシュして
いきます。すべてノード集合
を処理し終わったら「スタッ
ク」をポップしていきます。こ
の結果、V のノードをある順
序で出力できます。
一般に、トポロジカル・ソー
ティングの解はユニークでは
ありませんが、DAG（半順序集合）からノードを適当な順序集合として出力する手段とし
てよく使用されます。
他の実装例としては、資料で紹介したグラフに対する DFS(Depth First Search：深さ優
先探索)を利用することでも求められます。その場合は、DFS にもうひとつ、たとえば
ArrayList<Integer>型のパラメータを追加し、そこに「深さ優先探索」で終了ノード（終了
時刻の早い順に）を先頭に挿入してゆき、全部処理が終わったところで、この ArrayList の
先頭要素から書き出せば、トポロジカル・ソートが完成します。なお、先頭に追加する場合、
ArrayList<Integer> list;のような変数なら、list.add(0, vertexId);のようにすれば先頭に追
加できます。
また、CSVファイル形式は、左下図に示すようで、以下のようになっています。
最初の行は（ノード数）,（エッジ数）を表し、そのあと、（エッジ数）だけ、（開始ノー
ド名）,（終了ノード名）のペアが各行にひとつ現れます。たとえば、「靴下, くつ」の意
味は、「靴下」を先に身に着け、そのあとで「くつ」を身に着ける、という意味です。右
下図はトポロジカル・ソーティングの実行例です。（この例はDFSで実装したものです）
CSVファイル例
トポロジカル・ソーティング実行例
なお、DAGファイルを置いてあるhttp://kde.cs.tut.ac.jp/~aono/data/DAGには、CSV
データのほかに、graphviz（http://www.graphviz.org/）と呼ばれるソフトウェアで可
視化した結果を前ページのような有向グラフで表現した画像ファイル(.jpg)を置いています
ので、デバッグに利用してください。
ちなみに、ここで述べた例ではノード名のStringを、日本語（たとえば「ベルト」）で
使用していますが、課題の２つのデータのうち、自分で作成するデータで日本語を利用す
る場合は、UTF-8符号にしておいてください。

Download Report