小方 登
ここで提示するのはソースコードおよび使用法など最小限の情報であり,原理や応用の説明は授業・ゼミ等で行っています。以下に掲げるソースコードのファイル拡張子は,ブラウザで見やすいよう".txt"になっていますが,C++処理系に適するよう".cpp"などに改め,コンソール・アプリケーションとして作成してください。
ネットワークの例としては,地表上の道路網や,人々の間の知己関係などがあります。前者は網の目として物理的実体をもつもの,後者はもたないものの例です。この両者に共通し,ネットワークの本質を構成するのは,《関係》であるといえます。ネットワークを点と点を結ぶ線,すなわち《関係》のセットとしてとらえたものをグラフといい,その性質について研究するのがグラフ理論です。グラフををコンピュータ上に整数で表現することにより,コンピュータを利用したネットワークの分析・処理が可能となります。以下の例では,ネットワークを行列として表現しています。
仮想的なネットワーク | ネットワークの行列表現 |
上に示した例では,点と点の間に線がある場合,対応する行列要素に1が,ない場合に0が入ります。このような行列を,連結性行列と呼んでいます。
連結性行列は,点と点の間の直接の結合しか示しませんが,連結性行列を2乗することにより,2つの線を経る間接的な結合を明らかにすることができます。次のプログラムでは,2つの行列の積を計算します。
C++ソースコード‥‥mm.txt
使い方‥‥Windowsのコマンドプロンプトから
C:\>mm c01.txt c01.txt
ここで,"c01.txt"は処理対象のファイルであり,連結性行列を表すテキストファイル。「メモ帳」などのテキストエディタで編集する。1行目が行・列数で,2行目以下が行列の内容。
結果は,処理対象のファイルと同じ形式で画面(標準出力)に出される。結果をファイルに保存し,さらに次の処理の入力としたい場合には,出力をファイルにリダイレクトする。
C:\>mm c01.txt c01.txt > c02.txt
結果をさらに掛け算することで,3乗以上を求めることができる。
C:\>mm c02.txt c01.txt > c03.txt
連結性行列から,2地点間の Shimbel 距離(トポロジー的な距離)を求めます。Shimbel 距離とは,ネットワーク上の任意の2点間を結ぶために最少でいくつの線を経なければならないかをいい,トポロジー的な距離ということができます。
C++ソースコード‥‥shimbel.txt
使い方‥‥Windowsのコマンドプロンプトから
C:\>shimbel c01.txt
結果は,画面に表示されます。
以上の例では,点と点の間の線の有無だけを問題にしていましたが,距離や費用など線(あるいは関係)の性質についての情報を含むグラフを有値グラフといいます。次の図では,点と点を結ぶ線の距離を行列で表現しています。直接的な結合がない組み合わせでは,行列要素に無限大が入りますが,コンピュータでは無限大を表現できないので,代わりに「十分大きな数」を入れています。
有値グラフを表す行列から,間接的な距離を求めます。
距離の情報のあるネットワーク | ネットワーク(距離の情報を含む)の行列表現 |
1本の線で直接結ばれている点間の距離についてだけ表現している上の行列から,複数の線を経る経路の距離を算出する手順をプログラム化したものです。
C++ソースコード‥‥vm.txt
使い方‥‥Windowsのコマンドプロンプトから
C:\>vm vg01.txt vg01.txt
ここで,"vg01.txt"は処理対象のファイルであり,有値グラフの行列を表すテキストファイル。1行目が行・列数で,2行目以下が行列の内容。「無限大」は,ここでは "9999" で表している。
結果は,処理対象のファイルと同じ形式で画面(標準出力)に出される。この例では,2本の線を経る経路の距離を出力する。結果をファイルに保存し,さらに次の処理の入力としたい場合には,出力をファイルにリダイレクトする。
C:\>vm vg01.txt vg01.txt > vg02.txt
結果をさらに演算することで,3ステップ以上の距離を求めることができる。
C:\>vm vg02.txt vg01.txt > vg03.txt
上に実装した手順を応用し,有値グラフを表す行列から,2地点間の経路の距離を表す行列を求めます。
C++ソースコード‥‥dist.txt
使い方‥‥Windowsのコマンドプロンプトから
C:\>dist vg01.txt
結果は,画面に表示されます。
有値グラフを表す行列の,ある地点から他の点への最短距離を求めます。
C++ソースコード‥‥dijk.txt
使い方‥‥Windowsのコマンドプロンプトから,ファイル名と始点を指定してください。
C:\>dijk vg01.txt 1
結果は,画面に表示されます。
有値グラフを表す行列から,2地点間の経路の最短距離を表す行列を求めます。
C++ソースコード‥‥fw.txt
使い方‥‥Windowsのコマンドプロンプトから
C:\>fw vg01.txt
結果は,画面に表示されます。
【参考文献】