ソフトウェア演習Ⅲ〔課題 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 符号)で置いている。各自適当な1つのデータを選択し、
これを読み込み、トポロジカル・ソーティングを行うこと。
(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を、日本語(たとえば「ベルト」)で
使用していますが、課題の2つのデータのうち、自分で作成するデータで日本語を利用す
る場合は、UTF-8符号にしておいてください。