鉄道とグラフ理論 (3)

技術研究所のまつけんです。

前回 (part 2) の続きです。前回は実際に、仙台近郊と福岡近郊の路線図を入力し、経路を生成してみました。今回は東京近郊です。例によって、路線図を隣接行列に変換します:


路線図から、この巨大な行列にどうやって変換したかというと・・・・手作業です。根性です。エンジニアと言えども時には根性で乗り切らなければならない場面もあるのです (笑)。そうは言ってもソフトウェアエンジニア魂がありますので、幾つかテクニックを駆使して手間を軽減しています。例えば、出来上がった隣接行列は必ず線対称になることがわかっているので、片方だけを入力すれば、もう一方は自動で補完できます。これは、以前に紹介したMATLAB/Octaveで簡単にできます。例えば、以下:

のようにすることで、Aという8×8行列を定義して、それを線対称にすることが出来ます。また、線対称になったことを確認するには

の結果がゼロになっていることを確認します。ちなみに、Python + NumPyでも同じことが出来ます:

さて、このようにして出来た隣接行列のCSVファイル:

を入力できるように、ソフトウェアを改造します。また、探索結果が膨大な数になることがわかっているので、最大乗り換え回数 max_transfers を設定できるようにします。改造後のプログラムは以下の通りです:

さて、それでは実行してみましょう (g++でビルドできます)。乗り換え回数を5、10、および、15に制限して実行した結果です:

もの凄い経路の数です。しかも、ここでいう「乗り換え回数」というのは現実世界のそれとは異なります。例えば、品川から山手線で日暮里まで行くだけでも、神田と秋葉原で乗り換えたという扱いになってしまいます。残念ながら、これでは実用に耐えませんね。この問題を解決するには、鉄道の路線情報などを組み込む必要がありますが、そこまでやると、「ちょっとした趣味」の範囲を逸脱してしまいますので、ひとまず、このくらいにしておきたいと思います。

それはそれとして、もう一つ問題があります。プログラムについては、簡単なテストを行っていますが、データ (路線図を隣接行列に変換したもの) については、まだ、テスト (確認作業) をしていません。根性で打ち込んだものの、行列と路線図を目視で確認するのは大変ですし、確認作業中にミスが発生しそうです。そこで、これについてもソフトウェアエンジニア魂を発揮してみたいと思います。

隣接行列を再び路線図の形に戻せれば、確認作業がやりやすいはずです。路線図を隣接行列に変換した時点で位置情報が失われてしまっていますから、位置情報を与えてやる必要があります。日本の駅の緯度と経度をダウンロードできるサイト[1]を見つけたのでそれを使いましょう。ダウンロードしたCSVファイルは全国版なので、JR東日本管内の緯度と経度だけを取り出します:

先に作成したCSV読み込みルーチンをそのまま使いたいので、ファイル全体を転置します。これについては、Excelなどで「行と列を入れ替えて張り付け」れば出来ます。転置したファイルをjr_east_T.csvとして保存します (なお、隣接行列の駅名に合わせて、茅ケ崎→茅ヶ崎、御茶ノ水→お茶ノ水に置換しました)。先のプログラムを改造して、隣接行列とjr_east_T.csvを読み込んで、路線図のSVGファイルを出力するプログラムを作成しました:

SVGファイルについては、[2]を参照していただければと思います。以下:

のように実行した結果が、こちらです:

生成されたSVGをPDFに変換したものが、こちらになります。早速、元の路線図と比べてみたのですが、思った通り、少なくとも間違いが3か所ありました。やはり、確認作業は大切ですね。なお、今回のように、データを作成したときとは別の方法で確認を行うと、ミスの発見が容易になりますね。

如何でしたでしょうか? 今回作成した座標データから図を生成するプログラムは何かと使えるかと思います (線の色や太さは「stroke=\”grey\” stroke-width=\”1\”」の部分を、文字サイズは「font-size=\”8\”」の部分で変更できます)。次回は、これを少し改良して、より見やすい図を生成できないか、検討したいと思います。それでは、また次回。


[1] 駅・路線、緯度経度データ等のダウンロード https://opendata-web.site/dl/
[2] https://ja.wikipedia.org/wiki/Scalable_Vector_Graphics

  • このエントリーをはてなブックマークに追加