『スルッとKANSAI』の最長片道経路を求める 【その１】

　『スルッとKANSAI』エリア内の最長片道経路を求める。
　『スルッとKANSAI』はほぼ全ての関西私鉄が有効エリアに含まれているため、この経路は実質的に"関西私鉄網の最長片道経路"といっても良いかもしれない。
 
 　概要については以前noteに投稿したが、こちらではスクリプトなどより技術的情報についても記述する。

## 1. スルッとKANSAIの最長片道経路

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3325469/671c7871-d06a-addd-24e3-02a6f6e682b6.png)
　『スルッとKANSAI』は近畿圏を中心とした鉄道・バス事業者で構成するスルッとKANSAI協議会が展開していた磁気式共通乗車カードシステムで、2018年まで２府７県で約1,500kmの鉄道路線への乗車が可能だった。
　また、2016年まで*は『スルッとKANSAI 3dayチケット』や『スルッとKANSAI 2dayチケット』等、スルッとKANSAIエリア内のフリーきっぷ(周遊券)が発売されており、１枚のきっぷで関西の多くの私鉄を乗り回すことができた。(*2016年以後もエリア限定版や訪日外国人向けは販売中。)
　現在、磁気カード式の『スルッとKANSAI』は利用終了となっているが、非接触式ICカード『PiTaPa』がスルッとKANSAIエリアにおいて利用可能となっている。


![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3325469/ec2d8d5a-cf7d-8444-2f11-19519d0b2a07.png)

　このスルッとKANSAIエリアの中で、「最も長い一筆書きのルート(最長片道経路)はどこか？」については、以前から気になっていた。
 
　今回、プログラミングにより最長片道切符経路の導出を試みた先人である、JNOT様やPsyduck様のサイトを参考にpythonを用いて"スルッとKANSAIエリアの最長片道経路"を求めてみた。（なお、今回のスルッとKANSAI最長片道経路探索は、正確にはスルッとKANSAIではない近鉄の愛知県/三重県区間や近鉄田原本線なども含めて行うこととする。）

**（参考にした先人達のWebページ↓）**
[JNOT様 - GoogleでJR最長片道切符を計算する方法(初期設定、ロジック実装編)](https://note.com/jnot/n/nd2c9469e4fd8)

[Psyduck様 - Graphillionを使って最長片道切符のルートを算出する - 駆け出しエンジニアの作業ノート](https://psyduck-take-it-easy.hatenablog.com/entry/2018/06/17/222824)

[葛西隆也様 - 最長片道きっぷ - 問題の分析](https://www.swa785.net/lop/lop_def.html#whatslop)

## 2. スルッとKANSAIの最長片道経路 算出の流れ
　「スルッとKANSAIの最長片道経路」について、今回は２パターンの最長片道経路を算出する。
 
 　全体の流れは以下の通り。

**１.** 探索するエリアの全駅間のデータセットを作成する
**２.** 全駅間のデータセットを「必要な駅間」のみのデータセットに加工する
**３.** スルッとKANSAI最長片道経路の有力候補の見当をつけ、経路距離を算出
**４.** ３.で求めた有力候補が最長経路であることを証明する
↑↑↑
ここまでで１パターン目の「スルッとKANSAI最長片道経路」を特定。
**５.** 駅名が違う乗換え駅を同一駅扱いするよう改め、最長片道経路を再算出
↑↑↑
これにより２パターン目「スルッとKANSAI"真の"最長片道経路」を算出。

## 3. 駅間データセットの作成
　スルッとKANSAIの最長片道経路は、Graphillionを使用するコード（スクリプト）をpythonで動かして算出する。

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3325469/3f7c9d18-1e11-8878-394e-552df431846f.png)

　前準備として、最長片道経路特定用のコードで使用する「必要な駅間のデータセット(以下、「必要駅間データセット」)」について、スルッとKANSAIエリアのデータセットを作成する。

### 3-1. スルッとKANSAIエリア 全駅間データセットの作成

　「必要駅間データセット」の作成の前に、まずスルッとKANSAIエリアの「全駅間データセット」を用意する。
 
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3325469/153604b8-28d4-e36f-b10b-17e80a160793.png)

wikipediaの駅一覧表（https://ja.wikipedia.org/wiki/%E8%BF%91%E9%89%84%E5%B1%B1%E7%94%B0%E7%B7%9A）

　「全駅間データセット」は、スルッとKANSAIエリア内の鉄道路線の"全駅間"とその"駅間距離"を一つにまとめたデータセットだが、インターネット上には残念ながら使えそうなデータがないため、Wikipedia等から情報を持ってきてまとめる必要がある。
　ほとんどの鉄道路線のWikipedia個別ページには、「駅一覧表」など、駅間距離がまとめられた"表"が掲載されているので、この表を有効活用するのが良い。（国土数値情報等にこのデータがあれば助かるのだが…）

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3325469/56fa69fb-8019-b8bd-ea76-c74d7b1fc7e7.png)


### 3-2. スルッとKANSAIエリア 必要駅間の考え方
　3-1で用意した「スルッとKANSAIエリアの全駅間データセット」を「スルッとKANSAIエリアの必要駅間データセット」に加工する。

　最長片道経路探索対象エリア内の駅について、以下の３タイプの駅を考える。
　　**①分岐駅　
　　②分岐駅の隣駅　
　　③盲腸線の終端駅**
　この時、最長片道経路の算出において必要な駅間距離は「①〜①間」「①〜②間」「②〜②間」「①or②〜③間」のみ。これら４種類の駅間データのみに「全駅間データセット」を加工したものが「必要駅間データセット」だ。
　※「盲腸線」とは、起点もしくは終点のどちらかが他の路線に接続していない行き止まりの路線のこと。路線網の中であたかも盲腸（虫垂）のように見えることからこのように俗称。（詳しくは次回【その２】にて。）

　「必要駅間データセット」については分かりにくいので補足すると、

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3325469/93a781ea-d40d-dc9b-54aa-c52a983e140b.png)
fig.1 阪急電鉄の路線図

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3325469/a0a8db35-8959-5eab-73b5-e8ad23d5c501.png)
fig2. 阪急電鉄の必要駅間

　fig.1の阪急電鉄の全線路線図において、最長片道経路を求めたい場合に考慮しなければいけない「必要駅間」は、fig.2に載っている駅だけにまで絞り込める、ということ。
　（この時、
　　　①は 桂/淡路/十三/石橋/塚口/西宮北口/夙川
　　　②は 西京極/上桂/洛西口/上新庄/下新庄/柴島/崇禅寺…等
　　　③は 河原町/嵐山/北千里/天神橋筋六丁目/梅田/箕面/伊丹…等
　　となる。）

### 3-3.スルッとKANSAIエリア 必要駅間データセットの作成

[Graphillionで使う路線データを自動生成するツールを作った - 駆け出しエンジニアの作業ノート](https://psyduck-take-it-easy.hatenablog.com/entry/2019/12/15/201555)

　「全駅間データセット」を「必要駅間データセット」に加工するコードは上記リンクのPsyduck様のスクリプトを少し改良して使用する。
 
 　上記リンクに記載されたスクリプトでは、地点(必要駅間)毎の距離を計算して印字(新しいCSVに記録)するループにおいて、end側の駅のみで「全駅間データセット」への当該駅の出現回数を確認しているが、このまま回すと
  
![図N.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3325469/98db632f-5dbf-7418-f1b4-be5275368d09.png)

  「全駅間データセット」が上記のようなデータセットになっていた際に、近鉄名古屋駅がstart駅とならずに飛ばされてしまう結果が出てくる。
  
　そこで、地点(必要駅間)毎の距離を計算して印字(新しいCSVに記録)するループ中に、「（endが空の場合、距離を計算しdistanceに加算した後、）"現在処理中の行が処理された次に処理される行"のline_data[0]がstart_listに含まれていないかを確認し、含まれている場合はひとつ前の条件分岐でendに設定しなかった駅名をendに設定し印字を実行する」というif文を追加する改良を行った。
  
　コードは下記の通り。
```python
# 改良版
# ファイルを読み取りモードで開く
with open(file1, "r") as f:
    lines = f.readlines()
    station_dict = {}
    for line in lines:
        line_data = line.split(",")
        for i in range(0, 2):
            if line_data[i] not in station_dict:
                station_dict[line_data[i]] = 1
            else:
                station_dict[line_data[i]] = station_dict[line_data[i]] + 1

    start_list = []
    for line in lines:
        line_data = line.split(",")
        if station_dict[line_data[0]] > 2:
            if (line_data[1] not in start_list) and (station_dict[line_data[1]] == 2):
                start_list.append(line_data[1])
        elif station_dict[line_data[1]] > 2:
            if (line_data[0] not in start_list) and (station_dict[line_data[0]] == 2):
                start_list.append(line_data[0])

    start = ""
    end = ""
    distance = 0
    stop_station_list = ['くいな橋','中崎町','宝塚']  # 分岐駅では無いが、路線名が途中で変わる駅(神戸・金沢等)や、強制的に分割したい駅をリスト形式で入れる

# 新しいCSVファイルに書き込む
with open(file2, "w") as f2:
    for i, line in enumerate(lines):
        line_data = line.split(",")
        if start == "":
            start = line_data[0]
        if (station_dict[line_data[1]] != 2) or (line_data[1] in stop_station_list) or (
                line_data[1] in start_list):
            end = line_data[1]
        if end == "":
            distance += float(line_data[2])
            distance = round(distance, 1)
        else:
            distance += round(float(line_data[2]), 2)
            distance = round(distance, 1)
            next_line_data = lines[i+1].split(",") if i+1 < len(lines) else None
            if next_line_data and next_line_data[0] in start_list:
                end = line_data[1]  # ここが改良箇所
            write_list = [start, end, str(distance)]
            write_line = ",".join(write_list)
            f2.write(write_line)
            f2.write("\n")
            start = ""
            end = ""
            distance = 0

# 結果を表示する
with open(file2, "r") as result_file:
    result_lines = result_file.readlines()
    print("")   # 1行空白を設ける
    for line in result_lines:
        print(line.strip())
 ```

　なお、上述のコードで「必要駅間データセット」を作成する際は２地点間の距離を二重に登録することがないように強制的な分割駅を定める必要がある。
 
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3325469/0bbd5dfa-8103-a0d5-f088-e76e4bff470b.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3325469/22797f37-95dc-ea37-8a5f-695d3ce686f8.png)

　スルッとKANSAIエリアにおいては、「くいな橋(京都~竹田のため)」と「中崎町(天神橋筋六丁目~南森町)」を分割駅として設定する。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3325469/e45dc2af-cb57-f9d2-8e79-bcd281d22b97.png)

　また、この後最長片道経路を求めるコードを動かす際、必要駅間データセットに他のどの路線とも接続しない"孤立線"が含まれている場合、エラーが出る。
　この対策として、近鉄田原本線や比叡山坂本ケーブルなどの孤立線の端駅を別の路線と接続するように駅名を修正する。（厳密に駅名が一致する場合のみ乗換可能としたい場合は、孤立線の駅間データを削除する。）

 さらに、上記二つの修正以外にも、データセットをチェックし、下記の修正を加えた。
 
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;修正箇所集　↓
![図3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3325469/7fbc9464-7f5d-a253-a96e-790bfae0e4b6.png)


![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3325469/2983d702-d112-29ec-dbe0-7c303cc00371.png)

　ここまでの作業で「スルッとKANSAIエリアの必要駅間データセット」が完成した。

## 4. 最長片道経路の算出(次回に続く)
　次回以降の記事で「スルッとKANSAIエリアの最長片道経路」を"２種類"算出する。