本州のJR２駅間での最長片道切符をGraphillionを使って求める

目的

近くにある２つの駅をできる限り遠回りして行ったらどのくらいの距離になるのかが疑問になったので，それを調べます．このような最長切符を求める試みがいくつか見つかったのでそれらを参考にさせていただきました．ルートを探す際のルールは一筆書きで，JRの在来線のみです．
複雑なグラフから一筆書きの経路を探索するという問題は非常に複雑(以下のフカシギの数え方参照)なのでこれを効率的に探索できるGraphillion( https://github.com/takemaru/graphillion )を使いました．

実際に

Graphillionは経路を探索する対象になるグラフの各辺に重み付けをできるので，距離を重みとして用います．

下準備

実際のJR路線の各駅と駅間距離が必要ですが，これらがまとまったデータを入手できなかったので自分で地道につくりました．
まず時刻表などに乗ってる普通の路線図から、盲腸路線ではない乗り換えできる路線と、分岐駅のみを抜粋した簡単な路線図を書き起こし，次に２つの分岐駅からなる区間とその区間距離を書き出していきます．
そのような区間は約200個以上にもなり，駅間距離を求めるのに人力は辛いのでyahoo乗り換えをスクレイピングさせていただきました．yahoo乗り換えではルートに私鉄が使われてしまっていたり，同じ名称の別の駅が指定されたりもしたのでいくつかは手作業で修正します．
最終的には以下のようなデータをつくりました．

edges.csv

...
近江塩津,綾部,125.2,北陸線・小浜線・舞鶴線
小出,新前橋,124.9,上越線
小出,宮内,30.4,上越線
...

4列目の路線名は確認用として経路探索には使いませんでしたが，少し工夫すれば最終結果にも表示させることができそうです．

路線元データを読み込む

from graphillion import GraphSet as gs
import csv
import copy

edges_path = './edges.csv'


univ = []
with open(edges_path) as f:
	reader = csv.reader(f)
	for row in reader:
		#csvから１行ずつ読み込み，重み付け辺としてunivに追加
		edge = (row[0], row[1], float(row[2]))
		univ.append(edge)

gs.set_universe(univ)

2つの駅名とその間の距離を持つタプル(edge)から成るリスト(univ)でユニバースを定義します．

経路探索を行う

start = '大阪'
goal = '天王寺'
paths = gs.paths(start, goal)#全経路を探索
print('経路総数:',len(paths))   #経路の総数を表示


longest_path_result = []
for path in paths.max_iter():
    longest_path_result = path #最長経路
    break

実際に全経路を探索して，その後に最長経路を取得します．ただ，ここで得られる最長経路の結果として表示されるものは順番がバラバラでとても分かりづらいので後で整えてから出力します．
全経路の総数は大阪から天王寺の場合13121083304749989通りになったのですが，正しいのでしょうか？

スコア(合計駅間距離)を求めるために

def get_score(route ,universal):
	for k in universal:
		if (route[0] == k[0]) and (route[1] == k[1]):
			return(k[2])
			break

ここからはテキトーに作ったのですが，駅間距離を最終結果で表示するために用意しておきます．

結果表示

p = []
score = 0.0

longest_path = copy.copy(longest_path_result)
#pに始発駅をまず追加
for k in longest_path:
	if k[0] == start:
		p.append(k)
		score += get_score(k, univ)
		longest_path.remove(k)
	elif k[1] == start:
		p.append((k[1], k[0]))
		score += get_score(k, univ)
		longest_path.remove(k)

#順番につながっていくように探し出してつなげていく
while len(p) < len(longest_path_result):
	for k in longest_path:
		if k[0] == p[-1][1]:
			p.append(k)
			score += get_score(k, univ)
			longest_path.remove(k)
		elif k[1] == p[-1][1]:
			p.append((k[1], k[0]))
			score += get_score(k, univ)
			longest_path.remove(k)


print(p)
print('合計距離:', score, 'km')

outText = start
for l in p:
	outText += '--' + l[1]

print(outText)

大阪から天王寺で求めたときの結果

経路総数: 13121083304749989
合計距離: 5928.8km
大阪--京橋--尼崎--谷川--加古川--姫路--相生--東岡山--岡山--津山--新見--総社--倉敷--福山--塩町--広島--岩国--櫛ケ浜--新山口--居能--小野田--厚狭--下関--長門市--益田--宍道--備後落合--備中神代--伯耆大山--鳥取--福知山--綾部--近江塩津--山科--京都--新大阪--放出--木津--柘植--草津--米原--岐阜--多治見--塩尻--辰野--岡谷--甲府--八王子--立川--拝島--高麗川--高崎--大宮--小山--永盛--郡山--会津若松--小出--宮内--吉田--東三条--新津--新潟--新発田--坂町--余目--秋田--大曲--横手--北上--一ノ関--前谷地--高城町--仙台--塩釜--小牛田--新庄--羽前千歳--米沢--福島--岩沼--いわき--水戸--友部--我孫子--新松戸--南浦和--赤羽--武蔵浦和--西国分寺--新宿--池袋--田端--日暮里--上野--秋葉原--錦糸町--西船橋--千葉--佐倉--成田--成東--大網--木更津--蘇我--南船橋--市川塩浜--東京--神田--御茶ノ水--代々木--品川--川崎--尻手--武蔵小杉--鶴見--東神奈川--橋本--茅ヶ崎--国府津--御殿場--沼津--富士--豊橋--金山--名古屋--亀山--和歌山--高田--奈良--王寺--久宝寺--天王寺

簡単に結果をまとめると，大阪から下関の間を南北にちょこちょこ動きながら往復し，中央線経由で関東に出た後そのまま東北地方を東西にちょこちょこ動きながら往復してまた関東に戻り，房総半島を一周したりしてから東海道を西に進み，最後に紀伊半島を一周してから天王寺に至る．そんなルートです．

さいごに

元データがほとんど手作業だったのでそこでのミスがありそうですが，思っていたより高速で簡単に求めることができました．いつか実際にこの経路で乗車してみてはいかがでしょうか．

参考