Rのigraphパッケージで厚沢部町内の距離計算を自動化する

仕事で旅費の計算に使っている厚沢部町内の距離表、経由地が増えてくるとどこを通るのが最短なのかもわかりにくいし、計算間違いも起きやすいので、自動計算できたらいいな、と思っていたところ、Rで実現できそうなので試してみました。
ダイクストラ法という手法で最短経路問題を解きます。



使うのはigraphパッケージ

下記を実行してigraphパッケージをインストール。
結構時間がかかりました。
10分くらいだったと思います。

install.packages("igraph")　　##igraphパッケージをインストール
library("igraph")　　##igraphパッケージを読み込み
g<-read.csv("assabu.csv")　　##あらかじめ作っておいた距離データをgに付値



距離データのつくり方

距離データは表計算ソフトでこんな感じでつくります。
「地点1」と「地点2」の順番はどうでもよくて、とにかく隣接する地点間の距離が網羅されていればよろしいです。


ネットワークデータの作成

ネットワークというのは点（ノード）が線（エッジ）でつながったもので、特有のデータ形式があるようです。
まずは、先ほどgに付置した行列のデータをigraphで扱えるデータフレーム型式に変換します。
変換するコマンドはgraph.data.frame()です。
オプションのdirected=Fをdirected=Tにすると地点1から地点2に方向を持つようになります。
つまり、地点2から地点1へは行けない一方通行になります。

また、距離をweightという要素に付置します。

net<-graph.data.frame(g,directed=F) 　　##データをネットワークデータに変換してnetに付値
E(net)$weight<-g$距離　　##距離をネットワークデータのweight要素に付値


ネットワークを図化するとこうなります。
地図ではないので、方位なんかは関係ないのです。



距離行列の作成

全てのノードとノードの距離を算出します。
ノードの数×ノードの数の行列ができます。
これをデータフレーム型式にしてspvに付置します。

距離行列を算出するコマンドはshortest.paths()です。

spv<-as.data.frame(shortest.paths(net)) 　　##距離行列をデータフレームにしてspvに付値



距離計算に必要なデータを準備します

最初に出発点、経由点、終着点をベクトル形式でpに付置します。
経由点を格納するのに使うリスト形式のオブジェクトaを作成します。
距離ベクトルを格納するのに使うベクトル形式のオブジェクトbを作成します。

p<-c("新町","富里","鶉町","碧血碑","意養","美和","富栄","赤沼町","滝野","新町")　　##pに出発点、経由点、終着点を付値
a<-list("test")　　##aにダミーのデータを入れてリスト形式のオブジェクトを作成
b<-0　　##ベクトル形式のオブジェクトbを作成

なお、事例としてpに付置した経路の距離計算はめちゃくちゃ面倒です。



for文を使って、経由点のリストと距離ベクトルを作成

いよいよ本番です。
以下のコードを実行。

for(i in 1:(length(p)-1)){　　
sp<-get.shortest.paths(net,from=p[i],to=p[i+1]) ##spに最短距離のノードリストを付値
a[[i]]<-V(net)$name[unlist(sp)] 　##最短距離のノードリストをaに格納
b[i]<-spv[p[i],p[i+1]] 　　##距離行列の行と列を指定して距離を取り出すしてbに格納
}
print(a)
print(b)

これが経由地のリスト。
新町〜富里〜鶉町〜碧血碑〜意養〜美和〜富栄〜赤沼町〜滝野〜新町までの最短経路上にある地点名の一覧です。
（一部だけ表示）

こちらが新町〜富里〜鶉町〜碧血碑〜意養〜美和〜富栄〜赤沼町〜滝野〜新町までのルートの距離の一覧です。

この 記事 は クリエイティブ・コモンズ 表示 4.0 国際 ライセンスの下に提供されています。