ソフトウェア演習Ⅲ〔課題 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符号にしておいてください。
© Copyright 2024 ExpyDoc