大阪Metroに受けて立つ！Graphillionで見つけた最長の驚異のルート！

2024年6月27日 08:32

はじめに

　大阪Metroの公式Youtubeで最長一筆書きのルートが紹介されていました。「挑戦者求む!」らしいので、受けて立つ!

条件確認

以下の条件で大阪Metroで最長の経路を求めてみたいと思います。

大阪メトロ内の地下鉄、ニュートラムのみで完結する[1]
同じ駅を二度通らない
心斎橋駅と四ツ橋駅は同一とする
梅田駅と東梅田駅、西梅田駅は別駅とし、距離は0kmとする。

　駅間距離はWikipediaや石本隆一著「大阪の地下鉄」市ヶ谷ハジメら著「都市鉄道完全ガイド関西私鉄・地下鉄」を参考にしています。ここで、値が一致しないときは、ジョルダンやYahoo乗換案内に一致するものを取ることにしました。[2]
　手打ちでデータ入力したので、打ち間違いが頻発して大変でした,,,,,
　今思えば、Wikipediaのライブラリを使って、データを習得してもよかったのかもしれない。

　データを入力しましたし、最長の一筆書き経路を見つけましょう。でも、一筆書きの経路はめちゃくちゃ多そうだし、計算ミスしそうだし無理!　,めんどい!　やーめたー

そんなあなたでも、簡単に、高速に最長経路を見つけることができます。

そうGraphGraphillionならね

Graphillionを使ったコードを実装する

　Graphillionは昔ネットで有名になった「数え上げお姉さん問題」を作った人たちが作ったPythonライブラリです。数え上げお姉さん問題だけでなく、さまざまなグラフの問題を解くことができます。
　もちろん、最長一筆書き問題もね。

　ということで、データを手打ちし、Graphillionで求めてみましょう。参考にした記事はこちら。

#Google Colaboratoryで行う時に必要なもの最低でもgraphillionだけあれば下のコードは動く
!pip install graphillion                 #graphillionインストール
!apt-get -y install fonts-ipafont-gothic #日本語フォントのインストール
!pip install japanize_matplotlib         #日本語化のためのライブラリ

import pandas as pd
import matplotlib.pyplot as plt
import japanize_matplotlib
import numpy as np
import networkx as nx
from graphillion import GraphSet, tutorial
import itertools
from graphillion import GraphSet as gs

# 与えられたリスト　距離は100m単位で与えられている
#乗換駅と終着駅以外は省略をしている
universe = [
    ('江坂', '梅田', 64, '御堂筋線'),
    ('梅田', '東梅田', 0, '御堂筋線'),
    ('梅田', '西梅田', 0, '御堂筋線'),
    ('梅田', '本町', 22, '御堂筋線'),
    ('本町', '心斎橋', 9, '御堂筋線'),
    ('心斎橋', 'なんば', 12, '御堂筋線'),
    ('なんば', '大国町', 12, '御堂筋線'),
    ('大国町', '動物園前', 12, '御堂筋線'),
    ('動物園前', '天王寺', 10, '御堂筋線'),
    ('天王寺', '長居', 44, '御堂筋線'),
    ('長居', 'なかもず', 62, '御堂筋線'),
    ('天王寺', '八尾南', 105, '谷町線'),
    ('天王寺', '谷町九丁目', 21, '谷町線'),
    ('谷町九丁目', '谷町六丁目', 9, '谷町線'),
    ('谷町四丁目', '谷町六丁目', 10, '谷町線'),
    ('谷町四丁目', '南森町', 23, '谷町線'),
    ('東梅田', '南森町', 12, '谷町線'),
    ('東梅田', '天神橋筋六丁目', 18, '谷町線'),
    ('天神橋筋六丁目', '太子橋今市', 55, '谷町線'),
    ('太子橋今市', '大日', 30, '谷町線'),
    ('西梅田', '本町', 19, '四つ橋線'),
    ('阿波座', '大国町', 227, '四つ橋線ニュートラム中央線'),
    ('阿波座', '本町', 11, '中央線'),
    ('本町', '堺筋本町', 7, '中央線'),
    ('堺筋本町', '谷町四丁目', 10, '中央線'),
    ('谷町四丁目', '森ノ宮', 13, '中央線'),
    ('森ノ宮', '緑橋', 12, '中央線'),
    ('緑橋', '長田', 43, '中央線'),
    ('天神橋筋六丁目', '南森町', 13, '堺筋線'),
    ('南森町', '堺筋本町', 17, '堺筋線'),
    ('堺筋本町', '長堀橋', 9, '堺筋線'),
    ('長堀橋', '日本橋', 8, '堺筋線'),
    ('日本橋', '動物園前', 17, '堺筋線'),
    ('動物園前', '天下茶屋', 15, '堺筋線'),
    ('野田阪神', '阿波座', 19, '千日前線'),
    ('阿波座', '西長堀', 9, '千日前線'),
    ('西長堀', 'なんば', 20, '千日前線'),
    ('なんば', '日本橋', 7, '千日前線'),
    ('日本橋', '谷町九丁目', 10, '千日前線'),
    ('谷町九丁目', '今里', 26, '千日前線'),
    ('今里', '南巽', 39, '千日前線'),
    ('大正', '西長堀', 17, '長堀鶴見緑地線'),
    ('西長堀', '心斎橋', 11, '長堀鶴見緑地線'),
    ('心斎橋', '長堀橋', 7, '長堀鶴見緑地線'),
    ('長堀橋', '谷町六丁目', 11, '長堀鶴見緑地線'),
    ('谷町六丁目', '森ノ宮', 21, '長堀鶴見緑地線'),
    ('森ノ宮', '蒲生四丁目', 35, '長堀鶴見緑地線'),
    ('蒲生四丁目', '門真南', 48, '長堀鶴見緑地線'),
    ('今里', '緑橋', 13, '今里筋線'),
    ('緑橋', '蒲生四丁目', 21, '今里筋線'),
    ('蒲生四丁目', '太子橋今市', 48, '今里筋線'),
    ('太子橋今市', '井高野', 37, '今里筋線')
]

# リストをpandasのデータフレームに変換
df = pd.DataFrame(universe, columns=['from', 'to', 'dist', 'line'])

univ = []#つながっている駅同士の情報を入れる
weights = {} # 駅間距離

for i, v in df.iterrows():
    edge = (v['from'], v['to'])
    univ.append(edge)
    weights[edge] = v['dist']

gs.set_universe(univ)

#頂点の集合を作成
from_elements = [item[0] for item in universe]
to_elements = [item[1] for item in universe]

# 重複を削除して一つのリストにまとめる
unique_elements = list(set(from_elements + to_elements))

# ソートして見やすくする
unique_elements.sort()

combinations = list(itertools.combinations(unique_elements, 2))
ans = 0
max_pa = []


# 結果の表示　グラフ上の異なる2点を取り出し最長経路を算出し、その中で最大の経路を記憶する
for combination in combinations:

    paths=gs.paths(combination[0],combination[1])
    max_path = next(paths.max_iter(weights))
    distance = 0
    for edge in max_path:
        distance += weights[edge]
    if ans < distance:
        ans = distance
        max_pa = max_path
        #print(combination)
print(ans)
print(max_pa)

このコードの出力結果は、以下の様になりました。

794
[('今里', '緑橋'), ('南森町', '堺筋本町'), ('堺筋本町', '谷町四丁目'), 
('大国町', '動物園前'), ('天王寺', '谷町九丁目'), ('天王寺', '長居'), 
('天神橋筋六丁目', '太子橋今市'), ('心斎橋', 'なんば'), ('日本橋', '動物園前'), 
('本町', '心斎橋'), ('東梅田', '南森町'), ('東梅田', '天神橋筋六丁目'), 
('梅田', '本町'), ('森ノ宮', '緑橋'), ('森ノ宮', '蒲生四丁目'), ('江坂', '梅田'), 
('蒲生四丁目', '太子橋今市'), ('西長堀', 'なんば'), ('谷町九丁目', '今里'), 
('谷町四丁目', '谷町六丁目'), ('長堀橋', '日本橋'), ('長堀橋', '谷町六丁目'), 
('長居', 'なかもず'), ('阿波座', '大国町'), ('阿波座', '西長堀')]

ということで、最長一筆書きは79.4km　でした。
動画で紹介されていたのは78.9kmなので大阪メトロ公式より0.5km長いです。
ジョルダンで測ってみると4時間ほどで到着いたします。

わかりにくいので、経路を路線図に色付けすると下のようになります。

経路の表示は以下の記事を参考にしました。(この記事では駅間距離が駅の緯度経度から出されていることに注意)

おまけ　いまざとライナーの導入

　動画ではいまざとライナーが消されているので、いまざとライナーがあった場合の、最長片道ルートを考えたいと思います。なお、この条件では、地下鉄で発行される切符では乗れず、追加料金がかかりますので、実際には一日乗車券前提です。

universeの部分に

('今里', '天王寺', 61, '今里ライナー'),
　('今里', '長居', 95, '今里ライナー')

を追加すればよいです。(距離はgoogle mapで無理やり出した)
結果は91kmです。

910
[('今里', '長居'), ('堺筋本町', '谷町四丁目'), ('堺筋本町', '長堀橋'), ('大国町', '動物園前'), 
('天王寺', '八尾南'), ('天王寺', '長居'), ('天神橋筋六丁目', '太子橋今市'), ('心斎橋', 'なんば'),
 ('日本橋', '動物園前'), ('本町', '心斎橋'), ('東梅田', '南森町'), ('東梅田', '天神橋筋六丁目'), 
('梅田', '本町'), ('森ノ宮', '蒲生四丁目'), ('江坂', '梅田'), ('蒲生四丁目', '太子橋今市'), 
('西長堀', 'なんば'), ('谷町九丁目', '今里'), ('谷町九丁目', '谷町六丁目'), 
('谷町六丁目', '森ノ宮'), ('谷町四丁目', '南森町'), ('長堀橋', '日本橋'), ('阿波座', '大国町'), 
('阿波座', '西長堀')]

主な違い
(江坂、なかもず)から、(江坂、八尾南)になっています。
いまざとライナーを今里-長居間で使っています。

終わりに

　データの打ち間違いの可能性が否定できないので、実際はもっと長い経路があるかもしれません。もし、見つけた方がいらっしゃった場合は、コメントなり、TwitterのDMなりしてください。

かなりどうでもいい脚注

[1]中津以北とか阿波座以西は地上区間だけど、目をつぶってほしい..
[2]西梅田だけは例外でジョルダンとか無視して、1.9kmとしたよ。
あと、ほんと値が文献によって細かく違ってて大変だった。(公式がcsvデータとかで公開してほしい)

大回り乗車の正当性について

大阪Metro旅客営業規則に第28条に

第28条普通券は、旅客が乗車経路の連続した区間を片道１回乗車する場合に発売する。

大阪メトロ旅客営業規則より

とあります。
大回り乗車を禁止するときは近鉄などのように、明示してあります。これ