隣接行列プログラム

隣接行列を使ったグラフ探索のプログラムを作りたいのですが。。
手も足もでません。どなたか助けていただけないでしょうか？？




まずstate.txt
1
2 3

0

といったフォーマットに従った状態空間が記述された
テキストファイルを読み込んで、隣接行列を動的に作成し、
さらにその状態空間をfwrite()を用いてバイナリ形式のファイルにする。

実行時のコマンドラインは次の書式に従う。
> ./MakeGraph テキストファイル(読み込み元）　状態空間(書き込み元）　状態数 [Enter]




もうひとつは、上で作成した状態空間ファイル（バイナリ形式）をmalloc(),fread()を用いて
メモリ上に復元し、経路探索を行う。
ただし、オプション指定で縦型探索と横型探索を切り替えられるようにすること。

実行時のコマンドラインは次の書式に従う。
> ./Search [-bd] 状態空間ファイル　 状態数 　開始状態 　終了状態 [Enter]





ちなみに、
使用例
> ./MakeGraph state.txt state.bin 4 [Enter]
> ./Search -d state.bin 4 1 0 [Enter]
> ./Search -b state.bin 4 3 3 [Enter]
> ./Search -bd state.bin 4 2 0 [Enter]


結果例
1-0 : d : 0 <- 3 <- 1
3-3 : b : 3 <- 1 <- 0 <- 3
2-0 : b : Not Found...
2-0 : d : Not Found...



これらを作るうえでのヒントのようなものもあるのですが、さっぱりで。。

状態空間をファイルから取り込むため、隣接行列で表現した状態空間のサイズは可変、
（たとえば、状態数５ならば、２５個）である。したがって、メモリは動的に確保する必要がある。
また探索時に容易に扱えるようにするため、隣接行列は２次元配列であることが望ましい。
しかし、２次元の動的確保は難易度が高いので、１次元配列の動的確保を応用することで考える。
１次元配列を状態数２個確保し、２点の座標を指定することで、要求する要素へ
アクセスできるマクロCoordinates(x, y, size)を用意する。
このマクロを利用すれば、１次元配列で確保したデータを２次元として扱うことができる。

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

MakeGraph.cとSearch.cは次にあります。
ここにはのせきれなかったので。。

お手数おかけします。

http://mugen.cc.osaka-kyoiku.ac.jp/pg/












あとstate.txt のフォーマットは次のようになっています。

これはデータ構造などででてくる有向グラフを隣接行列で示した場合、
スタート地点の状態０から状態１に（０→１）
状態１から状態２と、ゴールの状態３に（１→２、１→３）
ゴールの状態３からスタート地点の状態０に（３→０）

となっていた場合に、状態０～３までのリンク先をあらわしたものです。
単に、机上において、隣接行列で表現すると
　　０　１　２　３

０　０　１　０　０

１　０　０　１　１

２　０　０　０　０

３　１　０　０　０

となります。（線がはいっていないのでややこしいかもしれませんが。。）

これと同じ意味で、


1 （状態０のリンク先で、１の直後に￥ｎ）
2 3 （状態１のリンク先で、２と３の間に空白、さらに３の後ろに￥ｎ）
　　（状態２のリンク先はなにもないので、まっしろ）
0 （状態３のリンク先）


となっています。こういう説明で伝わっているかわかりませんが、
よろしくおねがいします！！

No.1 回答者： Tacosan 回答日時： 2008/01/23 15:24

なんというか, state.txt のファイルフォーマットから考え直すべきだと思う.

scanf や fgetc などを駆使するか, fgets + strtok (など) で 1行ずつ処理するか, それくらいかなぁ.

この回答への補足

ファイルのフォーマットはもう与えられていて、、
その正直なところfgetsなどの応用がうまく出来なくて困っています。

補足日時：2008/01/24 00:40