ネットワーク分析 ― C++言語による地理情報処理の事例（その２）

小方　登

ここで提示するのはソースコードおよび使用法など最小限の情報であり，原理や応用の説明は授業・ゼミ等で行っています。以下に掲げるソースコードのファイル拡張子は，ブラウザで見やすいよう".txt"になっていますが，C++処理系に適するよう".cpp"などに改め，コンソール・アプリケーションとして作成してください。

グラフ理論に基づくネットワーク分析

ネットワークの例としては，地表上の道路網や，人々の間の知己関係などがあります。前者は網の目として物理的実体をもつもの，後者はもたないものの例です。この両者に共通し，ネットワークの本質を構成するのは，《関係》であるといえます。ネットワークを点と点を結ぶ線，すなわち《関係》のセットとしてとらえたものをグラフといい，その性質について研究するのがグラフ理論です。グラフををコンピュータ上に整数で表現することにより，コンピュータを利用したネットワークの分析・処理が可能となります。以下の例では，ネットワークを行列として表現しています。

仮想的なネットワーク ネットワークの行列表現

上に示した例では，点と点の間に線がある場合，対応する行列要素に１が，ない場合に０が入ります。このような行列を，連結性行列と呼んでいます。

(1) 行列の乗算

連結性行列は，点と点の間の直接の結合しか示しませんが，連結性行列を２乗することにより，２つの線を経る間接的な結合を明らかにすることができます。次のプログラムでは，２つの行列の積を計算します。

C++ソースコード‥‥mm.txt

使い方‥‥Windowsのコマンドプロンプトから

C:\>mm c01.txt c01.txt

ここで，"c01.txt"は処理対象のファイルであり，連結性行列を表すテキストファイル。「メモ帳」などのテキストエディタで編集する。１行目が行・列数で，２行目以下が行列の内容。

結果は，処理対象のファイルと同じ形式で画面（標準出力）に出される。結果をファイルに保存し，さらに次の処理の入力としたい場合には，出力をファイルにリダイレクトする。

C:\>mm c01.txt c01.txt > c02.txt

結果をさらに掛け算することで，３乗以上を求めることができる。

C:\>mm c02.txt c01.txt > c03.txt

(2) Shimbel 距離

連結性行列から，２地点間の Shimbel 距離（トポロジー的な距離）を求めます。Shimbel 距離とは，ネットワーク上の任意の２点間を結ぶために最少でいくつの線を経なければならないかをいい，トポロジー的な距離ということができます。

C++ソースコード‥‥shimbel.txt

使い方‥‥Windowsのコマンドプロンプトから

C:\>shimbel c01.txt

結果は，画面に表示されます。

有値グラフ

以上の例では，点と点の間の線の有無だけを問題にしていましたが，距離や費用など線（あるいは関係）の性質についての情報を含むグラフを有値グラフといいます。次の図では，点と点を結ぶ線の距離を行列で表現しています。直接的な結合がない組み合わせでは，行列要素に無限大が入りますが，コンピュータでは無限大を表現できないので，代わりに「十分大きな数」を入れています。

有値グラフを表す行列から，間接的な距離を求めます。

距離の情報のあるネットワーク ネットワーク（距離の情報を含む）の行列表現

(3) 有値グラフの計算

１本の線で直接結ばれている点間の距離についてだけ表現している上の行列から，複数の線を経る経路の距離を算出する手順をプログラム化したものです。

C++ソースコード‥‥vm.txt

使い方‥‥Windowsのコマンドプロンプトから

C:\>vm vg01.txt vg01.txt

ここで，"vg01.txt"は処理対象のファイルであり，有値グラフの行列を表すテキストファイル。１行目が行・列数で，２行目以下が行列の内容。「無限大」は，ここでは "9999" で表している。

結果は，処理対象のファイルと同じ形式で画面（標準出力）に出される。この例では，２本の線を経る経路の距離を出力する。結果をファイルに保存し，さらに次の処理の入力としたい場合には，出力をファイルにリダイレクトする。

C:\>vm vg01.txt vg01.txt > vg02.txt

結果をさらに演算することで，３ステップ以上の距離を求めることができる。

C:\>vm vg02.txt vg01.txt > vg03.txt

(4) 距離行列の計算

上に実装した手順を応用し，有値グラフを表す行列から，２地点間の経路の距離を表す行列を求めます。

C++ソースコード‥‥dist.txt

使い方‥‥Windowsのコマンドプロンプトから

C:\>dist vg01.txt

結果は，画面に表示されます。

(5) ダイクストラ法 Dijkstra’s algorithm による最短距離の計算

有値グラフを表す行列の，ある地点から他の点への最短距離を求めます。

C++ソースコード‥‥dijk.txt

使い方‥‥Windowsのコマンドプロンプトから，ファイル名と始点を指定してください。

C:\>dijk vg01.txt 1

結果は，画面に表示されます。

(6) フロイド=ワーシャル法 Floyd-Warshall algorithm による距離行列の計算

有値グラフを表す行列から，２地点間の経路の最短距離を表す行列を求めます。

C++ソースコード‥‥fw.txt

使い方‥‥Windowsのコマンドプロンプトから

C:\>fw vg01.txt

結果は，画面に表示されます。

【参考文献】