GoogleでJR最長片道切符を計算する方法(初期設定、ロジック実装編)

2019年8月29日 22:32

JR最長片道切符はgoogleアカウントを持っていれば無料で計算することができます。その方法がネット上にあまり記載されていないので、記載します。この情報は2020年6月時点でのやり方です。ライブラリやgoogleのポリシー、バージョンが変わってその通りできない場合もありますのでご注意ください。

以下のような人を対象にしています。

・最長片道切符を自力で計算しようとして、SWAさんのページを一通り読んでExcelなどで計算してみようと試みたがLee処理で挫折した
・Excelで計算しようとしたが数式の上限を超えてしまい計算できない
・excelがないので無料ソフトでなんとか最長片道切符を求めたい
・ExcelVBAを触った程度のプログラム知識がある
・pythonを使って最長片道切符を解きたいがインストールするのが超面倒

Google Colaboratory初期設定方法

①googlecolaboratoryにアクセスします。ログインして入ります。
このサービスはブラウザ上でpythonを動かすことができます。

②左上のファイルからPython3の新しいノートブックを選択します。

新しいノートブックが開きます。エラーが出る場合は「OK」をクリックします。

③最長片道切符を求めるためのライブラリ「Graphillion」をインストールします。以下を入力し左にある▶を押してインストールします。

pip install graphillion

インストールが完了すると「Successfully」と表示されます。
下の画像はgraphillion-1.3がインストールされました。

これでpyhon環境が整いました。次に最長片道切符の計算ソースを入力します。

最長片道切符の計算ロジックを実装する

①左上の　+コードをクリックして新しい行を追加します。

②以下のソースを記載します。

from graphillion import GraphSet as gs
import gc
import pandas as pd
import time
import itertools

time_sta=time.perf_counter()

#路線データJR.csvを読み込む[s_sta,e_sta,kiro2]
df_list = pd.read_csv('/content/JR.csv', sep=',')

#JRE.csvの駅名一覧を並べたもの[start_set,end_set]
df_list2=pd.read_csv('/content/order_set.csv', sep=',')

univ = []
weights = {}
AAA = []
BBB = []

#JRE.csvを読み込む
for i, v in df_list.iterrows():
   edge = (v['s_sta'], v['e_sta'])
   univ.append(edge)
   weights[edge] = v['kiro2']

#データをグラフにセット
gs.set_universe(univ)

for i, v in df_list2.iterrows():
   sta_s=(v['start_set'])
   sta_e=(v['end_set'])
   AAA.append(sta_s)
   BBB.append(sta_e)

#計算してキロを返す
def root_calc(start,end):
 #↓これでs-eの経路が列挙される
 paths = gs.paths(start, end)
 max_path = next(paths.max_iter(weights))
 distance = 0
 for edge in max_path:
   distance += weights[edge]
 #2020/6/12追記 メモリがすぐ足らなくなる問題を修正
 del paths
 gs.collect()
 return distance

#ルート詳細を表示する際にこちらを使用
#def root_print(path, search, end):
#   another = ""
#   for i in path:
#       if search in i:
#           root_list = list(i)
#           print(root_list)
#           path.remove(i)
#           root_list.remove(search)
#           another = root_list[0]
#           break
#       else:
#           another = search
#           continue
#   if another != "":
#       root_print(path, another, end)


#メイン処理
i_dst=0.0
j=1
for A in AAA:
 for B in BBB:
   start=A
   end = B
   if(start != end ):
     i=root_calc(start,end)
     time_end=time.perf_counter()
     tim=time_end - time_sta
     print("処理"+str(j)+"回目,"+start+","+end+",距離,"+str(i)+","+str(tim))
     j=j+1
 BBB.pop(0)

ソースは以下の３つのサイトから拝借させていただき微修正しました。
また、上記ソースには途中ルートを表示する仕組みは実装していません。
ソース記載の意味が知りたい方は個々のページを参照してください。また、途中ルートが知りたい方も参照してみてください。

https://psyduck-take-it-easy.hatenablog.com/entry/2018/06/17/222824

http://halpha656.hatenablog.com/entry/2014/08/28/120040

https://tech.mobilefactory.jp/entry/2018/12/20/180000

閑話　Graphillionとは

今回JR最長片道切符を計算するにあたり、pythonライブラリGraphillionを使用します。このライブラリはノードとエッジで構成されたグラフ、鉄道でいうと駅(ノード)と路線(エッジ)を定義すると、任意の２駅間に対して最長経路、最短経路を求めることができます。このライブラリがすごいのは最長経路をmax_iterと書くだけで求めてくれることです。また、それを高速で処理してくれます。
Graphillionの詳細はこちらをご覧ください。

https://github.com/takemaru/graphillion/wiki

あとはデータを作って実行するだけです。

データ設定、計算方法に続く

GoogleでJR最長片道切符を計算する方法(初期設定、ロジック実装編)

Google Colaboratory初期設定方法

最長片道切符の計算ロジックを実装する

閑話 Graphillionとは

いいなと思ったら応援しよう！

閑話　Graphillionとは