縦？横？京都の交差点名ルールをPythonで探るデータ分析旅

:::note info
　この記事は[DeNA 25新卒 Advent Calendar 2024](https://qiita.com/advent-calendar/2024/dena-25-newgrad)の10日目の記事です。他の記事もぜひチェックしてみてください！
:::

# 1. はじめに
　京都市の中心部は、東西（縦）の道と南北（横）の道から成っており、碁盤の目のような構造をしています。
　それに合わせて、交差点名は、地名ではなく、「縦の道の名前」と「横の道の名前」を並べて付けられていることが多いです。例えば、四条通と烏丸通の交差点は「四条烏丸」といった具合です。
 
 <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1694793/e4ab7577-6ec3-56fe-54d4-05a56837dd7f.png" width="70%">
 
　この命名方法は一見体系的に見えますが、「縦の道と横の道の順番がわからない」という問題を抱えています。縦の道が先の場合もあれば、横の道が先の場合もあります。しかし、駅名・待ち合わせ場所・現在地を伝える際などに交差点名が用いられることも少なくないため、その度に「どちらが先だったけな」と迷う羽目になるのです[^1][^10]。
 　この記事は、「どちらが先か」を機械的に判断できるようにしてみよう、という試みになっています。京都の交差点名を攻略してみましょう！

# 2. 概要
　この記事で行なっていることは以下の通りです。
 
:white_check_mark: 京都市営バスのバス停名を全取得（Python & Selenium）
:white_check_mark: 京都市の道名を全取得（Python & Selenium）
:white_check_mark: バス停名のうち、交差点名であるものを抽出（Python & 手作業）
:white_check_mark: 交差点名を縦の道と横の道に分解（手作業）
:white_check_mark: 有向グラフの構築・閉路チェック（Python & NetworkX）
:white_check_mark: 階層構造にプロット（Python・NetworkX）

データ取得から読みたい方 → [3. データの注意点](#3-データの注意点
)
グラフ構築から読みたい方 → [6. グラフの構築とプロット](#6-グラフの構築とプロット)
結論だけ見たい方 → [6.4 階層構造にプロット](#64-階層構造にプロット)

# 3. データの注意点
　この記事の一番の改善点は、「交差点名のデータ」です。交差点名を分析するからには、そのデータが必要になりますが、「京都市の全ての交差点名」がまとまったデータは見つけることができませんでした。
 　そこで、今回は「京都市営バスのバス停名」を用いることにしました。理由は大きく2点あります。
  1. 京都市営バスは、京都市内の主要地域を網羅しており、その運行路線数は74本に及ぶこと
  2. バス停名に交差点名が用いられていることが多いこと

　このデータの問題点は、データが小さくなってしまうことです。どうしても、「交差点名が用いられているバス停の数」は「交差点の数」より少ないです。
　しかし、このデータから得られた結果も十分参考にできそうなものであったため、ここではこのデータを用いることにします。もし良いデータを知っている方がおられたら、教えていただけますと有り難いです[^2][^3]。

# 4. データの取得
　ここでは、交差点のデータを作成するために必要な、バス停名と道名のデータを取得します。
## 4.1 取得元
　京都市営バスのバス停名、京都市の道名を、それぞれ以下のサイトから取得しました。
* [京都市交通局のバス路線一覧 - NAVITIME](https://www.navitime.co.jp/bus/route/busroutelist?cCode=00001064&cName=%E4%BA%AC%E9%83%BD%E5%B8%82%E4%BA%A4%E9%80%9A%E5%B1%80&p=1)
* [京都府京都市の道路名一覧｜マピオン電話帳](https://www.mapion.co.jp/phonebook/M08015/26100/)
:::note warn
　2024年12月16日時点では、どちらのサイトもこのURL以下の場所についてクローリングが許可されていました。データ取得時は対象サイトの利用規約を遵守しましょう。
:::


## 4.2 取得方法
　Python と Selenium を用いてクローリング & スクレイピングしました。
 　バス停名と道名でそれぞれ別のスクリプトを書いたのですが、大枠は同じものになっています。それぞれ50行ほどあるため、折りたたんでおきます。

<details><summary>バス停名を取得する Python スクリプト</summary>


```collect_bus_stops.py
import time

from selenium import webdriver
from selenium.webdriver.common.by import By
import pandas as pd

NAVITIME_KYOTO_BUS_TOP_URL = "https://www.navitime.co.jp/bus/route/busroutelist?cCode=00001064&cName=%E4%BA%AC%E9%83%BD%E5%B8%82%E4%BA%A4%E9%80%9A%E5%B1%80"

options = webdriver.ChromeOptions()
options.add_argument("--headless")
options.add_argument("--disable-blink-features=AutomationControlled")
options.add_argument(
    "user-agent=Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/91.0.4472.124 Safari/537.36"
)


driver = webdriver.Chrome(options=options)
driver.implicitly_wait(30)
driver.set_page_load_timeout(30)

current_url = NAVITIME_KYOTO_BUS_TOP_URL
bus_links = []
while True:
    driver.get(current_url)

    current_bus_links = driver.find_elements(By.XPATH, '//li[@class="link"]/a')
    current_bus_links = list(
        map(lambda link: link.get_attribute("href"), current_bus_links)
    )
    bus_links.extend(current_bus_links)

    next_page_link = driver.find_element(By.XPATH, '//img[@alt="次へ"]').find_element(
        By.XPATH, ".."
    )
    next_page_link = next_page_link.get_attribute("href")
    if next_page_link is None:
        break
    current_url = next_page_link

bus_stops = set()
for bus_link in bus_links:
    driver.get(bus_link)
    print(driver.title)
    current_stop_links = driver.find_elements(By.XPATH, '//dt[@class="node_name"]/a')
    for stop_link in current_stop_links:
        bus_stops.add(stop_link.text)
    time.sleep(10)

driver.quit()

df_bus_stops = pd.DataFrame(bus_stops, columns=["bus_stop"])
df_bus_stops.to_csv("data/bus_stops.csv", index=False)

```

</details>

<details><summary>道名を取得する Python スクリプト</summary>

```collect_streets.py
import time

from selenium import webdriver
from selenium.webdriver.common.by import By
import pandas as pd

MAPION_KYOTO_STREETS_URL = "https://www.mapion.co.jp/phonebook/M08015/26100/"

options = webdriver.ChromeOptions()
options.add_argument("--headless")
options.add_argument("--disable-blink-features=AutomationControlled")
options.add_argument(
    "user-agent=Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/91.0.4472.124 Safari/537.36"
)

driver = webdriver.Chrome(options=options)
driver.implicitly_wait(30)
driver.set_page_load_timeout(30)

current_url = MAPION_KYOTO_STREETS_URL
street_names = set()
while True:
    driver.get(current_url)
    print(current_url)

    current_street_names = driver.find_elements(
        By.XPATH, '//table[@class="list-table"]/tbody/tr/th//a'
    )
    current_street_names = list(
        map(lambda a_tag: a_tag.get_attribute("title"), current_street_names)
    )
    street_names.update(current_street_names)

    next_page_link = driver.find_elements(By.XPATH, '//a[@class="pagination-link"]')[-1]
    if next_page_link.text != "後へ":
        break
    next_page_link = next_page_link.get_attribute("href")
    current_url = next_page_link

    time.sleep(10)

driver.quit()

df_streets = pd.DataFrame(street_names, columns=["street"])
df_streets.to_csv("data/streets.csv", index=False)
```


</details>

## 4.3 取得結果
　データの件数はそれぞれ次の通りでした。完全一致している重複は除去済みです。
 * バス停名：713個
 * 道名：342個

　取得できたデータも貼っておきます。
 
:::note alert
（データ件数 + 1）に等しい行数があるため、折りたたみを解除する際は気をつけてください
:::

<details><summary>バス停名のデータ</summary>

```bus_stops.csv
bus_stop
花園橋(京都府)
横大路車庫前
北白川
桂消防署前
東高縄町
下津林大般若町
真如堂前
峰ケ堂町三丁目
大原野上里北ノ町
西大橋西詰
田中大久保町
桜木町(京都府)
福西竹の里
小畑川公園北口
西賀茂橋東詰
花園駅前(京都府)
高野(京都府)
下岸町
北白川小倉町
福西遺跡公園前
南広町
神泉苑前
上京区総合庁舎前
物集女
松尾橋(京都府)
吉祥院天満宮前
南禅寺・永観堂道
新林公団住宅前
修学院離宮道
藤森神社前
烏丸七条
小松原児童公園前
洛西口駅前
堀川今出川
河原町丸太町
吉祥院長田町
国道大手筋
北白川仕伏町
吉祥院前田町
竹田浄菩提院町
西大路五条
高野橋東詰
御土居
京都産大前
吉祥院嶋高町
河原町五条
嵯峨嵐山駅前
横大路
久世七本松
深草西浦町
下嵯峨(京都府)
山ノ前町
久我御旅町
墨染
桂小橋
九条大宮
京大桂キャンパス前
西ノ京馬代町
銀閣寺道
千本丸太町
槇ノ尾〔京都市営〕
久世橋東詰
唐戸町
九条車庫前
嵐山(京都府)
千本北大路
河原町八条
馬町
谷ヶ辻町
西大路駅前
京都駅八条口アバンティ前
上賀茂石計町
上里(京都府)
生田口
久世殿城町
東寺道
梅津段町
ゴルフ場前(京都府)
七瀬川町
智恵光院中立売
桂徳大寺
祇園(京都府)
伏見警察署前
広沢御所ノ内町
ＪＲ長岡京駅［東口］
大宮松原
樫原塚ノ本町
山越東町
京都市役所前
竹田久保町
高雄病院前
京都リサーチパーク前
太秦小学校前
七条御前通
地下鉄十条駅前
帷子ノ辻
今宮神社前(京都府)
河原町正面
西小路御池
近鉄上鳥羽口駅前
太秦天神川駅前
上桂駅前
修学院駅前
南区総合庁舎前(京都市)
宇多野御屋敷町
樋爪町
元町(京都府)
嵐電宇多野駅前
高雄小学校前
勝山町(京都府)
荒神口
洛北高校正門前
千本旧二条
深草下川原町
大原野小学校前
鳥羽大橋北詰
田中樋ノ口町
鷹峯上ノ町
京阪中書島・伏見港公園
東福寺道
京大正門前
常盤・嵯峨野高校前
西京極小学校前
東寺南門前
青少年科学センター前
下鳥田町
烏丸下立売
妙心寺北門前
牛若
西洞院六条
烏丸札ノ辻
堀川五条
西大路花屋町
大徳寺前
境谷センター前
吉祥院高畑町
深草北蓮池町
七条大宮・京都水族館前
松尾大社前
ふれあいの里(京都府)
府道横大路
住吉(京都府)
志久呂橋
船戸町
十条新町
桂イノベーションパーク前
竹田駅東口
葛野大路八条
西京極駅前
北山駅前
土天井町
上堀川
今出川浄福寺
吉祥院壱ノ段町
平田町(京都府)
水垂町
上鳥羽馬廻
勧進橋
烏丸六条
島原口
北白川校前
石原団地前
東福寺(京都府)
熊野神社前(京都府)
鳴滝松本町
四条京阪前
丸太町京阪前
西大路八条
京大病院前
壬生寺道
太秦北路町
南太秦
国道中山
下桂(京都府)
千本出水
宝ヶ池
西大路七条
四条中学前
国道三ノ宮
野田町(京都府)
車折神社前
河原町今出川
浄土寺(京都府)
一乗寺地蔵本町
御陵町
築山(京都府)
樫原(京都府)
四条河原町北詰〔よるバス〕
平岡八幡前
西賀茂井ノ口町
久世橋通新町
七本松出水
建勲神社前
肥後町
向日回生病院前
中久世一丁目
植物園前(京都府)
東新林町
ＪＲ藤森駅前
原谷
葛野大路高辻
文化庁前・府庁前
五条京阪〔清水五条駅〕
烏丸下長者町
大門町(京都府)
山科団地
西境谷町三丁目
北大路新町
京都外大前
十条竹田街道
下久世
花の舞公園前
丹波橋
千代原口
栂ノ尾
新林中通
柊野グラウンド前
千本今出川
大宮五条
上桂西居町
自衛隊前(京都府)
一条戻橋・晴明神社前
宮前橋西詰
法然院町
出雲路橋
国道東野
ユースホステル前(京都府)
御室
七条河原町
一乗寺青城町
川田道
桂坂小学校前
三栖大黒町
札ノ辻(京都府)
双ケ丘
深泥池
新林池公園
久我の杜
下町(京都市)
洛水高校前
三条京阪前
八条中学前
大宮交通公園前
南工業団地前(京都府)
北園町(京都府)
桂中学前
常盤御池町
西寺前(京都府)
嵐電妙心寺駅前
納所岸ノ下
左京区総合庁舎・京都工芸繊維大学前
伯楽町
中久世
一乗寺下り松町
角倉町
南田町(京都府)
同志社前
紅葉町
東土川橋
四条中新道
上賀茂松本町
等持院道
八丁畷(京都府)
境谷大橋
新葵橋
北野中学前
竹田出橋
岡崎道
ライトハウス前
山ノ内(京都府)
太秦開日町
西大路三条
西大路御池
一乗寺梅ノ木町
峰ケ堂町一丁目
東山二条・岡崎公園口
川島町(京都府)
二条駅前
菱妻神社前
七条壬生川
福王子
大覚寺(京都府)
塩小路橋
棒鼻
伏見インクライン前
御香宮前
西洞院仏光寺
中書島
聖母女学院前
糺ノ森
梅津西浦町
久世橋通大宮
塩小路高倉・京都市立芸術大学前
飛鳥井町
小枝橋
新林センター前
上賀茂橋
東元町(京都府)
北白川別当町
梅小路公園・ＪＲ梅小路京都西駅前
清水道
西賀茂車庫前
樫原鴫谷
桂坂中央
神川小学校前
西大路四条［阪急・嵐電西院駅］
五条大和大路・東山開睛館前
衣笠氷室町
二条駅西口
菱川〔京都市営〕
修学院道
六孫王神社前
高雄(京都府)
京都駅八条口
堀川中立売
西洞院正面
西墨染通
加茂川中学前
左京区総合庁舎前
上高野(京都府)
西桂坂
河原町三条北〔よるバス〕
一乗寺北大丸町
堀川三条
桂大橋
西院巽町
羅城門
東寺東門前
西丹波橋
堀川下立売
三条春日
河原町三条南〔よるバス〕
右京ふれあい文化会館前
府立体育館前［島津アリーナ京都前］
岡崎神社前
今出川大宮
京都明徳高校前
大宮中立売
東天王町
大枝山町西
蚕ノ社
桂滝川町
莚田町
西京極運動公園前
嵐山天龍寺前［嵐電嵐山駅］
嵐山公園
朝露ケ原町
久世橋通油小路
丸太町智恵光院
西小路花屋町
四条堀川
出雲路俵町
堀川上立売
松ヶ崎駅前
岡崎公園　ロームシアター京都・みやこめっせ前
上賀茂菖蒲園町
公会堂前(京都市西京区)
五条西洞院
日新電機前
竹田城南宮道
下鳥羽城ノ越町
桂離宮前
小渕町
下鳥羽
玄琢
千本上立売
桃山中学前
松ヶ崎橋
西京極午塚町
桃陵団地前
東寺町
下久我
神殿町
御経坂
神宮道
岡崎公園　動物園前
久世工業団地前
松室北河原町
洛西バスターミナル
一乗寺高槻町
市立病院前(京都市中京区)
十条油小路
上桂前田町
常徳寺前
北福西町
梅宮大社前
堀川下長者町
久世大薮町
東山安井
直違橋一丁目
木辻南町
下京区総合庁舎前
近衛通
東山七条
上賀茂御薗橋
上宮ノ前町
烏丸御池
伊織町
金閣寺道
天神公園前
三栖公園前
北山橋東詰
城ケ前町
南松ノ木町
国道下鳥羽
樫原小学校前
月輪
吉祥院宮ノ西町
龍谷大学前(京都府)
嵯峨釈迦堂前
西ノ京塚本町
等持院南町
地下鉄九条駅前［大石橋］
十条大宮
平和台町
紫野泉堂町
三ノ宮(京都府)
府立大学前(京都府)
裁判所前(京都府)
神光院前
大将軍
下三栖(京都府)
光華女子学園前
出雲路神楽町
四条葛野大路
西竹の里町
八条油小路
松ノ下町
丸太町御前通
洛西高校前
上樋爪
七条京阪前
三町(京都府)
岩倉操車場前
桂駅東口
地蔵前(京都府)
洛西大橋
松尾大利町
竹の里小学校前
烏丸北大路〔北大路駅前〕
柊野別れ
国道塚原
国道赤池
北野天満宮前
下鴨神社前
藤ノ森(京都市)
安井西口
北ノ口(京都府)
上ノ町(京都市)
一乗寺赤ノ宮町
上七軒
上鳥羽塔ノ森
中央公園南口
大宮田尻町
岩ノ本町
阪急嵐山駅前
嵯峨野秋街道町
稲荷大社前
樫原水築町
上賀茂豊田町
東桂坂
府立医大病院前
二条城前
納所北城堀
南福西町二丁目
堀川鞍馬口
桂川小学校前
樫原秤谷町
上鳥羽村山町
わら天神前
出町柳駅前
川島粟田町
御室仁和寺
立命館西園寺記念館前
葛野大路花屋町
四条烏丸［地下鉄四条駅］
川島六ノ坪町
馬場(京都府)
南福西町三丁目
南福西町［竹林公園前］
梅ヶ畑清水町
西大手筋
千本中立売
藤森神社
博物館三十三間堂前
西板橋
三ノ宮街道
百万遍
九条御前通
京都駅前
河原町三条
西ノ京藤ノ木町
桂高校前
北大路バスターミナル［地下鉄北大路駅］
御薗口町［上賀茂神社前］
市民防災センター前(京都府)
上野橋(京都府)
太秦開町
北野白梅町
立命館大学〔衣笠キャンパス構内〕
烏丸五条［地下鉄五条駅］
羽束師志水町
上終町・瓜生山学園　京都芸術大学前
上桂東ノ口
嵯峨瀬戸川町
庚申前(京都府)
南春日町(京都府)
東寺西門前
堀川御池
十条相深町
警察学校前(京都府)
坊町
烏丸二条
西大路松原
鳴滝本町
馬塚町
芝本(京都府)
吉祥院池田町
堀川丸太町
黒橋(京都府)
葛野大路九条
僧坊町
宇多野病院前
堀川蛸薬師
花園扇野町
九条河原町
七条千本
西洞院松原
西賀茂中学北
四条御前通
免許試験場前(京都府)
月見ケ丘(京都府)
葵橋西詰
上鳥羽小学校前
宮ノ前町
四条高倉
五条壬生川
ＪＲ桂川駅前(京都府)
丸太町七本松
下緑町
佛教大学前
板橋(京都市伏見区)
玄琢下
七条堀川
西ノ京円町［ＪＲ円町駅］
西久宝寺町
広沢池・佛大広沢校前
一乗寺清水町
城南宮(京都市伏見区中島)
長福寺道
河原町十条
西本願寺前
竹田駅西口
五条坂
吉祥院蒔絵町
城南宮道
御所ノ口
九条近鉄前
やまごえ温水プール前
大宮総門口町
北沓掛町六丁目
千本三条・朱雀立命館前
北上久世
西寺町
京都先端科学大学前
西京極
堀川松原
鷹峯源光庵前
上賀茂神社前
上池田町
東山三条［地下鉄東山駅］
有栖川
史跡公園前(京都府)
京大農学部前
立命館大学前
烏丸丸太町［地下鉄丸太町駅］
吉祥院車道町
久我石原町
広芝町(京都府)
山越中町
河原町東寺道
志久呂橋西詰
岩倉大鷺町
最上町(京都府)
高鼻町
下竹殿町
太子道
上賀茂榊田町
五条高倉
松ヶ崎海尻町
落合町
みぶ操車場前
樋爪口
国道東土川
四条西洞院
山越(京都府)
野々宮〔京都市営〕
竹田内畑町
烏丸三条
今熊野
常磐野小学校前
岡崎法勝寺町
川勝寺
堀川寺ノ内
四条大宮
四条河原町
三宝寺(京都府)
北木ノ畑町
錦林車庫前
高木町(京都府)
旭ケ丘(京都市)
南横大路［さすてな京都］
上鳥羽
烏丸一条
油小路丹波橋・アクト京都前
銀閣寺前
鈴虫寺・苔寺道
原谷農協前
妙心寺前
久世橋西詰
知恩院前
西賀茂庄田町
高田町(京都府)
右京の里
一本松(京都府)
桂坂センター前
九条七本松
桂駅西口
烏丸今出川［地下鉄今出川駅］
太秦広隆寺前
久我
船岡山
岡崎公園　美術館・平安神宮前
京阪淀駅
乾隆校前
納所町
西京区役所前
洛北高校前
七条西洞院
山科西野
等持院東町
大枝山町東
国際会館駅前
川端二条
龍安寺前
太秦映画村道
東北園町
堺町御池
富ノ森
吉祥院堂ノ後町
河原町松原
上賀茂小学校前
梅小路公園・京都鉄道博物館前
北大路堀川
中ノ橋五条
中桂
東山仁王門
太秦東口(京都府)
下津林中島
新間ノ町二条
国道沓掛口
四条河原町南〔よるバス〕
高原町(京都府)
吉祥院運動公園前
野々神町
赤池(京都府)
嵯峨中学前
桂御陵坂
北福西町一丁目
奈須野
嵯峨小学校前
下鴨東本町
京橋(京都府)
大宮小野堀町
紫野上野町
内田町
下津林六反田
原谷口(京都府)
植物園北門前
牛ケ瀬(京都府)
下総町
七本松仁和寺街道
千本鞍馬口
城南宮東口
桂坂口
塔ノ下町
泉涌寺道
高橋南(京都府)
新町御池
山ノ内御池
東竹の里町
天蓋公園前
千本十条
パルスプラザ前
柊野
月読橋
八条大宮
梅津石灘町
上桂御正町
猿田彦橋
教育大学前(京都府)
東側町
烏丸松原
釈迦谷口
西大路九条
衣笠校前
一乗寺木ノ本町
大宮大門町
松ヶ崎大黒天
五丁橋
叡電元田中
工業団地前(京都市)
吉祥院西ノ茶屋町

```

</details>

<details><summary>道名のデータ</summary>

```streets.csv
street
寺町通
錦小路通
東鞍馬口通
七本松通
水垂上桂線
神宮道
烏丸通
梅小路通
千本通
下板橋通
揚梅通
諏訪町通
奈良街道
竹の里北通り
西石垣通
下魚棚通
鍵屋町通
久世橋通
間之町通
七条大宮四塚線
六波羅裏門通
両替町通
洛西中央通り
宇多野嵐山山田線
三条通
京都日吉美山線
今出川通
山中越え
鞘町通
黒門通
三年坂
新道通
京都広河原美山線
佐々江京北線
東中筋通
新柳馬場通
新千本通
宮ノ辻神吉線
元大宮通
川端通
下鴨京都停車場線
衣笠宇多野線
黒門通（新シ町通）
安井北門通
市道蹴上高野線
下切通シ
日野薬師線
押小路通
高倉通
神宮通
八条通
五条通
蹴上高野線
国道１６２号線
宮川町通
松屋町通
日暮通
国道１７１号線
中地熊田線
西小路
二条停車場円町線
上立売通
本町通
墨染通
醒ケ井通
新椹木町通
二条停車場嵐山線
御前通
勧修寺日ノ岡線
花園停車場御室線
松原通
今小路通
六条通
石塀小路
仁和寺街道
古門前通
新高倉通
鹿ケ谷通
東大路通
蛸薬師通
西寺町通
天神通
柿町通
吉田東通
中筋通
美福通
賀茂街道
岡崎通
清水坂
中町通
大宮通
毛利橋通
春日上通
伏見港京都停車場線
福西中通り
神護寺線
市道嵐山祇園線
裏門通
西塩小路通
花屋町通
新小栗栖街道
若宮通
渋谷山科停車場線
清水新道（茶わん坂）
伏見柳谷高槻線
丹波橋通
西三本木通
国道３６７号線
上枳穀馬場通（上珠数屋町通）
向島宇治線
切り通し
旧小栗栖街道
四ノ宮四ツ塚線
浄福寺通
椥辻通
上黒田貴船線
北泉通
中山稲荷線
福西本通り
西大路通
清滝道
船岡東通
新東洞院通
宝ケ池通
上長者町通
旧奈良街道
武者小路通
柚原向日線
京都八幡木津自転車道線
新奈良街道
元誓願寺通
桜馬場通
櫛笥通
曼殊院通
三之宮町通
先斗町通
塔ノ段通
花見小路通
二条通
壬生通
東山ドライブウェイ
下長者町通
針小路通
渋谷通
大黒町通
冷泉通
岩倉中通
木津屋橋通
修学院離宮道
丸太町通
後院通
南インター竹田線
雲ケ畑下杉坂線
柳馬場通
新麩屋町通
上板橋通
六軒町通
桝形通
洛南道路
下松屋町通
伏見向日線
名神高速道路
麩屋町通
勧修寺今熊野線
境谷中通り
堺町通
万寿寺通
佐々里井戸線
大津宇治線
向日善峰線
丹波口通
十条通
白川北通
銀閣寺宇多野線
上切通シ
出水通
白川通
五辻通
二之宮町通
市道衣笠宇多野線
一条通
塩小路通
正面通（中珠数屋通）
玄以通
若松通
大和大路通（縄手通）
綾小路通
御霊図子通
新門前通
麻生古屋梅ノ木線
紫明通
大津淀線
正面通
白川南通
宇多野吉祥院線
京都縦貫自動車道（京都丹波道路）
神泉苑通
石薬師通
嵯峨野西梅津線
竹の里本通り
錦市場
嵐山・高雄パークウェイ
今宮通
新烏丸通
新町通
沓掛西大路五条線
佐々江下中線
国道９号線
御池通
中道通
二年坂
上賀茂山端線
北小路通
荒神口通
城南宮北出入口
仏光寺通
嵯峨嵐山停車場線
不明門通
福西東通り
嵐山祇園線
上ノ下立売通（妙心寺通）
釜座通
太秦上桂線
京都環状線
京都京北線
仁王門通
岩倉山端線
天神川通
新京極通
二条停車場東山三条線
上ノ口通
近衛通
新富小路通
智恵光院通
裏寺町通
市道京都環状線
車屋町通
孫橋通
下鴨静原大原線
小川通
新丸太町通
嵐山高架道路
醍醐街道
師団街道
椹木町通
問屋町通
富小路通
鹿ケ谷嵐山線
姉小路通
市道鹿ケ谷嵐山線
西陣杉坂線
北山通
旧京阪国道
新間之町通
六軒通
西中筋通
新十条通
衣棚通
塔下弓削線
新橋通
愛宕弓槻線
中立売通
新林本通り
下鴨東通
梅津東山七条線
大覚寺平岡線
新宮川町通
御幸町通
新堺町通
新車屋町通
国道４７７号線
下立売通
高辻通
清滝鳥居本線
花園停車場大将軍線
維新の道
東海自然歩道
土手町通
西木屋町通
油小路通
古川町通
四条通
阪神高速８号京都線
下枳穀馬場通（下珠数屋町通）
猪熊通
葛野西通
北大路通
一般国道１６２号
中長者町通
周山街道
葭屋町通
六角通
東寺通
日野道
七条通
木屋町通
葛野大路
下鴨大津線
笹屋町通
東一条通
広小路通
西洞院通
哲学の道
国道１号線
岩上通
境谷本通り
下鴨本通
夷川通
草生上野線
神楽岡通
札辻通
五条坂
三栖向納所線
新町淀停車場線
国道２４号線
相国寺東通
鞍馬街道
御蔭通
河原町通
堀川通
団栗通
大手筋通
外環状線
九条通
妙心寺通
東三本木通
竹屋町通
土屋町通
中山向日線
灰方中山線
東洞院通
神山岩倉停車場線
寺之内通
室町通
竹田街道
下ノ森通
久多広河原線
的場通
小塩山大原野線
八坂通
末吉町通
京都守口線

```

</details>

# 5. データの整形
　ここでは、バス停名のデータと道名のデータから、交差点名および交差点を構成する道名のデータ（以下、交差点のデータ）を作成します。
　以下の理由で、交差点のデータを全自動で作成することは難しいと判断したため、途中で手動の工程を挟んでいます。
1. 一つの道が複数の名称を持つ場合があること[^4]
2. 交差点名となる際に道の呼び方が変わる場合があること[^5]
 
## 5.1 交差点名候補の抽出
　まず、「道名を含むバス停名」を機械的に抽出して、交差点名候補としました。道名とバス停名に対し、1回ずつフィルタリング処理を施します。
1. 「〇〇通」の形をした道名を抽出
2. 1. で抽出した道名の「〇〇」の部分が1つ以上含まれているバス停名を抽出

:::note warn
　有名な「京都の碁盤の目」は「〇〇通」の形の道名で構成されています。そのため、「〇〇通」の形でない道名（〇〇線、国道〇〇号など）を除外するために 1. の処理を行ったのですが、交差点名を詳しく見ていると、「〇〇通」の形でない道名が交差点名を構成していることもありました。
　今回のデータでは、1. の処理の有無によってこの後の結果は変わらなかったのですが、用いるデータによっては 1. の有無で結果が変わるかもしれません。
:::

　この工程で、バス停名が 713 件から 214 件に減りました[^6]。

　ソースコードは次の通りです。ここでの出力に列を加えたものが次節の出力になるため、出力の掲載は省略します。

<details><summary>道名を含むバス停名を抽出する Python スクリプト</summary>

```extract_bus_stops_containing_intersection.py
import numpy as np
import pandas as pd


def does_contain_street_name(bus_stop, streets):
    for street_name in streets:
        if street_name[:-1] in bus_stop:
            return True
    return False


df_bus_stops = pd.read_csv("data/bus_stops.csv")["bus_stop"]
df_streets = pd.read_csv("data/streets.csv")["street"]

street_candidates = df_streets[df_streets.str.endswith("通")].values

bus_stops_containing_intersection = df_bus_stops[
    df_bus_stops.apply(
        lambda bus_stop: does_contain_street_name(bus_stop, street_candidates)
    )
]

bus_stops_containing_intersection.to_csv(
    "data/bus_stops_containing_intersection.csv", index=False
)

```

</details>

## 5.2 交差点名を自力で抽出
　5.1 で作成した交差点名候補に対して、手作業で以下のことを行いました
 1. CSV に「縦の道名」「横の道名」「縦横どちらが先かのフラグ」の3列を追加
 2. 各交差点名候補が、交差点名であるかどうかの判定
 3. 交差点名である場合、1. で作成した3つの列を埋める

　出力は以下のようになりました。

 <details><summary>交差点のデータ</summary>

```bus_stops_containing_intersection_annotated.csv
bus_stop,vertical,horizontal,vertical_first
北白川,,,
北白川小倉町,,,
神泉苑前,,,
烏丸七条,烏丸,七条,1
小松原児童公園前,,,
堀川今出川,堀川,今出川,1
河原町丸太町,河原町,丸太町,1
国道大手筋,,,
北白川仕伏町,,,
西大路五条,西大路,五条,1
河原町五条,河原町,五条,1
久世七本松,,,
墨染,,,
九条大宮,大宮,九条,0
千本丸太町,千本,丸太町,1
久世橋東詰,,,
九条車庫前,,,
千本北大路,千本,北大路,1
河原町八条,河原町,八条,1
西大路駅前,,,
京都駅八条口アバンティ前,,,
東寺道,,,
智恵光院中立売,智恵光院,中立売,1
大宮松原,大宮,松原,1
樫原塚ノ本町,,,
七条御前通,御前,七条,0
地下鉄十条駅前,,,
今宮神社前(京都府),,,
河原町正面,河原町,正面,1
西小路御池,西小路,御池,1
太秦天神川駅前,,,
荒神口,,,
千本旧二条,千本,旧二条,1
東寺南門前,,,
烏丸下立売,烏丸,下立売,1
妙心寺北門前,,,
西洞院六条,西洞院,六条,1
烏丸札ノ辻,烏丸,札ノ辻,1
堀川五条,堀川,五条,1
西大路花屋町,西大路,花屋町,1
七条大宮・京都水族館前,大宮,七条,0
十条新町,新町,十条,0
葛野大路八条,葛野大路,八条,1
北山駅前,,,
上堀川,,,
今出川浄福寺,浄福寺,今出川,0
烏丸六条,烏丸,六条,1
北白川校前,,,
鳴滝松本町,,,
四条京阪前,,,
丸太町京阪前,,,
西大路八条,西大路,八条,1
壬生寺道,,,
千本出水,千本,出水,1
西大路七条,西大路,七条,1
四条中学前,,,
河原町今出川,河原町,今出川,1
一乗寺地蔵本町,,,
四条河原町北詰〔よるバス〕,河原町,四条,0
久世橋通新町,新町,久世橋,0
七本松出水,七本松,出水,1
葛野大路高辻,葛野大路,高辻,1
五条京阪〔清水五条駅〕,,,
烏丸下長者町,烏丸,下長者町,1
北大路新町,新町,北大路,0
十条竹田街道,竹田街道,十条,0
丹波橋,,,
千本今出川,千本,今出川,1
大宮五条,大宮,五条,1
一条戻橋・晴明神社前,,,
七条河原町,河原町,七条,0
三栖大黒町,,,
三条京阪前,,,
八条中学前,,,
大宮交通公園前,,,
常盤御池町,,,
嵐電妙心寺駅前,,,
四条中新道,,,
上賀茂松本町,,,
岡崎道,,,
西大路三条,西大路,三条,1
西大路御池,西大路,御池,1
東山二条・岡崎公園口,東大路,二条,1
二条駅前,,,
七条壬生川,壬生川,七条,0
塩小路橋,,,
西洞院仏光寺,西洞院,仏光寺,1
久世橋通大宮,大宮,久世橋,0
塩小路高倉・京都市立芸術大学前,高倉,塩小路,1
北白川別当町,,,
梅小路公園・ＪＲ梅小路京都西駅前,,,
西大路四条［阪急・嵐電西院駅］,西大路,四条,1
五条大和大路・東山開睛館前,大和大路,五条,0
衣笠氷室町,,,
二条駅西口,,,
京都駅八条口,,,
堀川中立売,堀川,中立売,1
西洞院正面,西洞院,正面,1
西墨染通,,,
河原町三条北〔よるバス〕,河原町,三条,1
堀川三条,堀川,三条,1
東寺東門前,,,
西丹波橋,,,
堀川下立売,堀川,下立売,1
三条春日,春日,三条,0
河原町三条南〔よるバス〕,河原町,三条,1
岡崎神社前,,,
今出川大宮,大宮,今出川,0
大宮中立売,大宮,中立売,1
久世橋通油小路,油小路,久世橋,0
丸太町智恵光院,智恵光院,丸太町,0
西小路花屋町,西小路,花屋町,1
四条堀川,堀川,四条,0
堀川上立売,堀川,中立売,1
岡崎公園　ロームシアター京都・みやこめっせ前,,,
五条西洞院,西洞院,五条,0
千本上立売,千本,上立売,1
東寺町,,,
神宮道,,,
岡崎公園　動物園前,,,
松室北河原町,,,
十条油小路,油小路,十条,0
堀川下長者町,堀川,下長者町,1
近衛通,,,
東山七条,東大路,七条,1
烏丸御池,烏丸,御池,1
天神公園前,,,
北山橋東詰,,,
西ノ京塚本町,,,
地下鉄九条駅前［大石橋］,,,
十条大宮,大宮,十条,0
四条葛野大路,葛野大路,四条,0
八条油小路,油小路,八条,0
丸太町御前通,御前,丸太町,0
七条京阪前,,,
烏丸北大路〔北大路駅前〕,烏丸,北大路,1
大宮田尻町,,,
岩ノ本町,,,
二条城前,,,
堀川鞍馬口,堀川,鞍馬口,1
わら天神前,,,
葛野大路花屋町,葛野大路,花屋町,1
四条烏丸［地下鉄四条駅］,烏丸,四条,0
西大手筋,,,
千本中立売,千本,中立売,1
九条御前通,御前,九条,0
河原町三条,河原町,三条,1
北大路バスターミナル［地下鉄北大路駅］,,,
烏丸五条［地下鉄五条駅］,烏丸,五条,1
東寺西門前,,,
堀川御池,堀川,御池,1
十条相深町,,,
烏丸二条,烏丸,二条,1
西大路松原,西大路,松原,1
鳴滝本町,,,
堀川丸太町,堀川,丸太町,1
葛野大路九条,葛野大路,九条,1
堀川蛸薬師,堀川,蛸薬師,1
九条河原町,河原町,九条,0
七条千本,千本,九条,0
西洞院松原,西洞院,松原,1
四条御前通,御前,四条,0
四条高倉,高倉,四条,0
五条壬生川,壬生川,五条,0
丸太町七本松,七本松,丸太町,0
七条堀川,堀川,七条,0
西久宝寺町,,,
河原町十条,河原町,十条,1
五条坂,,,
九条近鉄前,,,
大宮総門口町,,,
千本三条・朱雀立命館前,千本,三条,1
西寺町,,,
堀川松原,堀川,松原,1
東山三条［地下鉄東山駅］,東大路,三条,1
烏丸丸太町［地下鉄丸太町駅］,烏丸,丸太町,1
山越中町,,,
河原町東寺道,河原町,東寺,1
五条高倉,高倉,五条,0
四条西洞院,西洞院,四条,0
烏丸三条,烏丸,三条,1
岡崎法勝寺町,,,
堀川寺ノ内,堀川,寺ノ内,1
四条大宮,大宮,四条,0
四条河原町,河原町,四条,0
烏丸一条,烏丸,一条,1
油小路丹波橋・アクト京都前,油小路,丹波橋,1
妙心寺前,,,
久世橋西詰,,,
九条七本松,七本松,九条,0
烏丸今出川［地下鉄今出川駅］,烏丸,今出川,1
岡崎公園　美術館・平安神宮前,,,
七条西洞院,西洞院,七条,0
川端二条,川端,二条,1
堺町御池,堺町,御池,1
河原町松原,河原町,松原,1
梅小路公園・京都鉄道博物館前,,,
北大路堀川,堀川,北大路,0
中ノ橋五条,,,
東山仁王門,東大路,仁王門,1
新間ノ町二条,新間ノ町,二条,1
四条河原町南〔よるバス〕,河原町,四条,0
下鴨東本町,,,
大宮小野堀町,,,
七本松仁和寺街道,七本松,仁和寺街道,1
千本鞍馬口,千本,鞍馬口,1
新町御池,新町,御池,1
山ノ内御池,,,
千本十条,千本,十条,1
八条大宮,大宮,八条,0
烏丸松原,烏丸,松原,1
西大路九条,西大路,九条,1
一乗寺木ノ本町,,,
大宮大門町,,,
```

</details>

:::note warn
　手作業で行ったため、間違いがある可能性があります。3度見直しましたが、もし間違いに気づかれた場合、ご指摘いただけますと助かります。
:::


# 6. グラフの構築とプロット
　ここまでで、無事に交差点のデータを作成できました。
　ここからは、有向グラフの構築と、図のプロットを行なっていきます。
 
## 6.1 簡単な例
　実際のデータを扱う前に、簡単な例を用いて工程を軽く説明します。

　「四条通」「五条通」「烏丸通」「河原町通」の3つの道が作る、二つの交差点を考えます。交差点名は「四条烏丸」「烏丸五条」「四条河原町」「河原町五条」です。

  <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1694793/8219557e-3aaa-8c80-8926-7c8ab35a60f8.png" width="70%">

　道の間に順位付けを行いたいため、有向グラフを構築します。この例の場合、「四条」「五条」「烏丸」「河原町」の4つのノードと、「四条 → 烏丸」「四条 → 河原町」「烏丸 → 五条」「河原町 → 五条」の4つのエッジから成る有向グラフとなります。

   <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1694793/d7630571-d1e9-eeff-dd64-486953d61b8d.png" width="70%">

　続いて、すべてのエッジに対して、エッジの根本のノードが上に、先（三角形の方）のノードが下に来るように、ノードの位置を調整します。

   <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1694793/01116d3c-741b-2b14-a6a7-392f028ebe8e.png" width="70%">


すると、2つのノードを選んで交差点名を作る際に、「上の方のノードが先、下の方のノードが後」になると判断することができるいうわけです。
　一直線に並べる訳ではないため、トポロジカルソートとはまた違うのですが、トポロジカルソートのようなことをしようとしています。このプロット方法のことを便宜上、「階層構造にプロット」すると表現しています。このようなプロット方法の名前を知っている方がおられたら、コメント欄で教えてください......

## 6.2 有向グラフの構築
　5.2 で作成した交差点のデータから、有向グラフを構築します。
　ソースコードは以下の通りです。ノードの csv, エッジの csv, グラフの png ファイルを出力しています。

```build_directed_graph.py
import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt


# データ読み込み
df_bus_stops_containing_intersection = pd.read_csv(
    "data/bus_stops_containing_intersection_annotated.csv"
)
# 交差点名でない行を削除
df_bus_stops_containing_intersection = df_bus_stops_containing_intersection.dropna()
# 0, 1 で表されているフラグを bool に変換
df_bus_stops_containing_intersection["vertical_first"] = (
    df_bus_stops_containing_intersection["vertical_first"].astype(int).astype(bool)
)

# 有向グラフの構築
nodes, edges = set(), set()
for _, row in df_bus_stops_containing_intersection.iterrows():
    nodes.add(row["vertical"])
    nodes.add(row["horizontal"])
    if row["vertical_first"]:
        edges.add((row["vertical"], row["horizontal"]))
    else:
        edges.add((row["horizontal"], row["vertical"]))

G = nx.DiGraph()
G.add_nodes_from(nodes)
G.add_edges_from(edges)

# csv ファイルの作成
df_nodes = pd.DataFrame(list(nodes), columns=["node"])
df_edges = pd.DataFrame(list(edges), columns=["from", "to"])
# 便宜上、df_node にそのノード（道）が縦の道であるかどうかのフラグを追加
for _, row in df_nodes.iterrows():
    node = row["node"]
    if node in df_bus_stops_containing_intersection["vertical"].values:
        df_nodes.loc[df_nodes["node"] == node, "is_vertical"] = True
    else:
        df_nodes.loc[df_nodes["node"] == node, "is_vertical"] = False

df_nodes.to_csv("data/nodes.csv", index=False)
df_edges.to_csv("data/edges.csv", index=False)


# 画像の生成
plt.figure(figsize=(12, 8))
nx.draw(
    G,
    with_labels=True,
    font_family="Osaka",
    node_size=800,
    node_color="tab:cyan",
    font_size=8,
    pos=nx.nx_pydot.graphviz_layout(G),
)
plt.savefig("fig/directed_graph.png")
```

　出力は次のようになりました。csv は折りたたんでいます。

<details><summary>ノードの csv</summary>

```nodes.csv
node,is_vertical
油小路,True
九条,False
札ノ辻,False
千本,True
大宮,True
松原,False
河原町,True
七条,False
西洞院,True
旧二条,False
寺ノ内,False
堺町,True
塩小路,False
中立売,False
西小路,True
下立売,False
三条,False
久世橋,False
仁王門,False
丸太町,False
仏光寺,False
仁和寺街道,False
御池,False
下長者町,False
六条,False
智恵光院,True
丹波橋,False
新間ノ町,True
春日,True
大和大路,True
壬生川,True
出水,False
東寺,False
正面,False
五条,False
高倉,True
鞍馬口,False
竹田街道,True
御前,True
二条,False
浄福寺,True
堀川,True
新町,True
上立売,False
川端,True
八条,False
花屋町,False
北大路,False
葛野大路,True
七本松,True
高辻,False
西大路,True
今出川,False
東大路,True
蛸薬師,False
十条,False
四条,False
烏丸,True
一条,False
```
</details>

<details><summary>エッジの csv</summary>

```edges.csv
from,to
東大路,三条
四条,御前
西洞院,正面
油小路,丹波橋
河原町,十条
烏丸,二条
堺町,御池
八条,大宮
堀川,今出川
四条,河原町
今出川,浄福寺
五条,大和大路
久世橋,新町
五条,西洞院
堀川,寺ノ内
九条,大宮
四条,葛野大路
西洞院,松原
西大路,松原
河原町,正面
七条,御前
十条,油小路
東大路,二条
大宮,五条
五条,壬生川
葛野大路,花屋町
烏丸,下立売
丸太町,智恵光院
烏丸,下長者町
七条,河原町
七本松,出水
河原町,松原
西大路,八条
大宮,中立売
烏丸,六条
新間ノ町,二条
五条,高倉
河原町,東寺
堀川,下立売
西洞院,六条
川端,二条
千本,丸太町
八条,油小路
西大路,四条
葛野大路,高辻
久世橋,大宮
烏丸,御池
千本,中立売
千本,旧二条
河原町,八条
烏丸,松原
千本,三条
九条,千本
烏丸,北大路
西大路,御池
智恵光院,中立売
西小路,御池
西洞院,仏光寺
河原町,五条
堀川,鞍馬口
西大路,九条
堀川,松原
九条,御前
烏丸,七条
千本,今出川
四条,堀川
丸太町,御前
西大路,七条
河原町,三条
三条,春日
今出川,大宮
烏丸,五条
七条,西洞院
九条,河原町
西大路,五条
堀川,下長者町
千本,上立売
東大路,仁王門
久世橋,油小路
七条,壬生川
河原町,今出川
烏丸,三条
烏丸,札ノ辻
七条,堀川
西大路,花屋町
四条,西洞院
千本,十条
西大路,三条
西小路,花屋町
四条,大宮
堀川,蛸薬師
四条,烏丸
堀川,御池
十条,竹田街道
北大路,新町
河原町,丸太町
烏丸,今出川
大宮,松原
北大路,堀川
葛野大路,八条
七条,大宮
四条,高倉
九条,七本松
千本,鞍馬口
七本松,仁和寺街道
烏丸,丸太町
東大路,七条
千本,北大路
堀川,五条
高倉,塩小路
丸太町,七本松
千本,出水
十条,大宮
烏丸,一条
新町,御池
十条,新町
堀川,丸太町
堀川,中立売
堀川,三条
葛野大路,九条
```

</details>

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1694793/28f31ec1-3331-9805-011d-ac236219b4ef.png)

　ノードの数は 59, エッジの数は 120 でした。
　ノードは道、エッジは交差点に対応しているため、ノードの数に対してエッジが少ないことがわかります。理論上、エッジは最大で $((ノードの数)/2)^2$ あるはずです[^7]。今回のノード数だと、理論上の最大値は $(59/2)^2=870.25$ になります[^8]。
 
:::note warn
　この見積もりは、すべての道が十分長く伸びていて、横の道ならすべての縦の道と、縦の道ならすべての横の道と交わるという仮定に基づいています。
　しかし、実際は、道の長さにかなりばらつきがあります。大通りならこの仮定をしても良いくらい長く伸びていることが多いですが、細い道は途中で途切れていることが多いです。
　そのため、エッジ数の実際の最大値は、ここで求めた最大値の何割かしかないと思われます。
:::

　ノードの次数が大きいほど、そのノードと他のノードとの関係が正確になります。今回のデータでも、大通りのノードは次数が大きく、正確な結果を得ることができていそうです。しかし、大通りでない通りは次数1のノードも多く、結果の精度がある程度低いと思われます。

## 6.3 閉路チェック
　閉路があると、[6.1](#61-簡単な例)で説明したような、すべてのエッジが下を向くような図を作成できなくなります。例えば、6.1 で例に出した4つの道が下図のような交差点を構成していた場合、閉路が生じます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1694793/7df49ad1-1597-e2c6-ea89-875f1b8908ed.png)

　閉路がないことを確かめるために、トポロジカルソートを行いました。
　閉路の存在を確かめる方法は、幾通りもあります。その中でトポロジカルソートを選択した理由は、どの道が先に来やすいかということを見ておきたかったからです。

　トポロジカルソートを行う Python スクリプトは以下の通りです。
```topological_sort.py
import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt

df_nodes = pd.read_csv("data/nodes.csv", index_col=0)
df_edges = pd.read_csv("data/edges.csv")

df_nodes["indegree"] = df_edges["to"].value_counts()
df_nodes["indegree"] = df_nodes["indegree"].fillna(0).astype(int)

sorted_graph = df_nodes[df_nodes["indegree"] == 0].index.tolist()
q = sorted_graph.copy()
while q:
    from_node = q.pop()
    for _, (_, to_node) in df_edges[df_edges["from"] == from_node].iterrows():
        df_nodes.loc[to_node, "indegree"] -= 1
        if df_nodes.loc[to_node, "indegree"] == 0:
            q.append(to_node)
            sorted_graph.append(to_node)

assert len(sorted_graph) == len(df_nodes), "Graph is not a DAG"

print(sorted_graph)
```

　見づらいですが、出力はこのようになりました。
```python
['堺町', '西小路', '久世橋', '新間ノ町', '川端', '西大路', '東大路', '仁王門', '四条', '葛野大路', '烏丸', '七条', '札ノ辻', '一条', '高辻', '九条', '千本', '河原町', '東寺', '八条', '旧二条', '上立売', '十条', '北大路', '堀川', '今出川', '寺ノ内', '下立売', '鞍馬口', '下長者町', '蛸薬師', '丸太町', '三条', '春日', '智恵光院', '御前', '七本松', '出水', '仁和寺街道', '浄福寺', '竹田街道', '二条', '新町', '大宮', '油小路', '丹波橋', '五条', '中立売', '大和大路', '西洞院', '壬生川', '高倉', '塩小路', '正面', '松原', '六条', '仏光寺', '花屋町', '御池']
```

　無事に、閉路がないことを確認できました。閉路があれば、強連結成分分解をして、閉路部分を1つのノードにまとめることで対応するつもりでした。今回はその必要がなく、シンプルに進めることができたためよかったです。

## 6.4 階層構造にプロット
### 6.4.1 結果

　ここまでで、道同士の関係が閉路のない有向グラフ（DAG）であることが確認できました。あとは、見やすくプロットするだけです！
　先に結果をお見せします。今回の結果は、次のようになりました。
 
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1694793/9348139f-47c9-8b9e-80d9-c77f9491b1be.png)


　青っぽいノードが縦の道、緑っぽいノードが横の道になっています。

　前述の通り、この図では、交差点名で先に来るノードほど上の方にプロットされています。そのため、**例えば、西大路通と四条通の交差点に居て、「西大路四条と四条西大路、どっちで呼べばいいんだったっけな......」と思ったときにこの図があれば、「西大路四条だ！」と判断できる**という訳です。（西大路は一番上のノード、四条は上から二番目のノードになっています）。
 
### 6.4.2 考察
　大通りはエッジの数が多いため、結果が正確だと思われます。一方、大通りでない道は、結果の精度に欠けるのではないかと推測していました。この図では、大通りでない道はすべて、下の2段に存在しています。つまり、「大通りと大通りでない道の交差点」についても、この図はある程度正しい結果を反映していそうです。

　今回の結果に足りないのは、以下の2点だと考えています。
 1. ノード数
 2. 大通りでない道同士の交差点の情報

　これらは、データを変えることでしか改善できません。[3.](#3-データの注意点
) のところで書いたように、もっと良いデータで試してみたいです......

### 6.4.3 プロット方法
　プロットの方針は次の通りです。まず、次の計算を行い、下から順番にノードを並べます。
1. 出次数がゼロのノード（葉）を一番下に並べる
2. 1.で選ばれたノードに向かって伸びるエッジを削除する
3. すべてのノードが並べられるまで、1., 2.を繰り返す

　ノードを並べることができたら、エッジを復元します。

　以下が、このプロットを行う Python スクリプトです。実際には手順 2. でエッジを削除はしておらず、出次数を減らしているだけです。

```draw_hierarchical_graph.py
import pandas as pd
import networkx as nx
import matplotlib.pyplot as plt

df_edges = pd.read_csv("data/edges.csv")
df_nodes = pd.read_csv("data/nodes.csv", index_col=0)

# 出次数の計算
df_nodes["outdegree"] = df_nodes.index.map(df_edges["from"].value_counts())
df_nodes["outdegree"] = df_nodes["outdegree"].fillna(0).astype(int)

# ノードの位置（階層と x 座標）を計算
df_nodes["layer"] = None
df_nodes["pos_x"] = None
current_layer = 0
while df_nodes["layer"].isna().any():
    outdegree_after = df_nodes["outdegree"].copy() # 更新後の出次数を保存
    pos_x = 0
    for node_name, row in df_nodes.iterrows():
        if row["outdegree"] == 0 and row["layer"] is None:
            # 出次数が0かつ階層がまだ決まっていない場合
            df_nodes.loc[node_name, "layer"] = current_layer
            df_nodes.loc[node_name, "pos_x"] = pos_x
            outdegree_after.loc[df_edges[df_edges["to"] == node_name]["from"]] -= 1
            # x 座標を計算
            if pos_x >= 0:
                pos_x = -pos_x - 1
            else:
                pos_x = -pos_x

    current_layer += 1
    df_nodes["outdegree"] = outdegree_after

pos = {
    node_name: (row["pos_x"], row["layer"]) for node_name, row in df_nodes.iterrows()
}

# グラフの作成
G = nx.DiGraph()
G.add_nodes_from(df_nodes.index)
G.add_edges_from(df_edges[["from", "to"]].values)

# 図をプロット
plt.figure(figsize=(15, 8))
node_color = []
for node in G._node:
    if df_nodes.loc[node, "is_vertical"]:
        node_color.append("tab:cyan")
    else:
        node_color.append("tab:olive")

nx.draw(
    G,
    pos,
    with_labels=True,
    font_family="Osaka",
    node_size=800,
    node_color=node_color,
    font_size=8,
)
plt.savefig("fig/hierarchical_graph.png")
```

　一部の例外を除き、交差点は「縦の道」と「横の道」から成ります[^9]。つまり、一部の例外のエッジを除くと、交差点の有向グラフは二部グラフになっています。
　二部グラフである性質を活かして、次のような形で道名を並べて可視化したかったため、今回のプロット方法を用いました
```
優先順位が最も高い縦の道の集合
↓
優先順位が最も高い横の道の集合
↓
優先順位が2番目に高い縦の道の集合
↓
優先順位が2番目に高い横の道の集合
↓
：
↓
優先順位が最も低い縦の道の集合
↓
優先順位が最も低い横の道の集合
```

# 7. まとめ
　道名を組み合わせて交差点名を表現する方法は、とても便利ですよね。エンジニアの好みと合っているのではないか、と個人的に思っています。
　しかし、交差点名の道の順番は、判断がつきにくいところです。もちろん、どちらの順番でも大丈夫ではあります。しかし、誰にでもわかる指針を示すことも面白いのではないか、と以前から興味を持っていました。
 
　今回分析してみたことで、指針を示すことができただけでなく、道の順番に対して意外な発見もありました。例えば、
* 四条通が優先順位1位ではないこと
* 主要な道である、堀川通・河原町通・烏丸通がすべて 5 段目以下であること
    * これらは順に、国道1号線、代表的な繁華街、地下鉄の通る道なのですが、交差点の順位だと上位には来ないようです

などです。
　指針として眺めてみたり、面白いポイントを探してみたり、さまざまな使い方をしていただけると嬉しいです。
 
　今回のデータでもある程度指針を示せたとは思うのですが、もう少し大きいデータで試した方が、より具体的で正確な結果を得ることができるはずです。またデータを取り直して試してみたいところです。

[^1]: 基本的に、より主要な道の方が先に来ているとは思います。大通りとそうでない道の交差点は、だいたい大通りの方が先なはずです。しかし、大通り同士や大通りでない道同士だと、どちらが先かの判断はすぐにはできません。
[^10]: 交差点名の法則について調べている記事が、他にもいくつも見つかりました。ご興味のある方は、他の記事も読んでみていただけると面白いかと思います。例として2つリンクを貼っておきます。[京都の交差点名に法則は？（謎解きクルーズ）　繁華な通り先に　地域の実情映し変化 - 日本経済新聞](https://www.nikkei.com/article/DGXLASIH11H09_R10C15A6AA1P00/), [京の地名の不思議　東西と南北の通り、どっちが先？ | NHK](https://www.nhk.or.jp/kyoto/lreport/article/003/16/)
[^2]: 他に思いついたデータは次のものがありました。① 交差点の標識 ② Google Trends。これらを採用できなかった理由はそれぞれ次のとおりです。① ストリートビューを目視で確認する必要があり、手間がかかりすぎたこと ② 2種類の交差点名で人気度にあまり差のない場合が多かったこと。① のデータ自体は良いものだと思うため、収集してみたいのですが......
[^3]: 交差点名は、縦が先と横が先の、両方の名前が用いられていることがあります。例えば、五条通と大宮通の交差点は、標識は「五条大宮」なのに対してバス停名は「大宮五条」となっています。一般的かつ命名方法が一貫しているデータを用いることで、より自然な結果を得たいです。
[^4]: 例えば、「佐井通」は地域によっては「春日通」と呼ばれます。
[^5]: 例えば、「東大路通」は交差点名やバス停名においては「東山」となります。かつて「東山通」という名称であったことに由来しているようです。
[^6]: 道名でフィルタリングしたため、縦の道も横の道も[^3]や[^4]で挙げたようなパターンとなる交差点名が省かれてしまいました。「東大路通」と「安井北門通」の交差点である「東山安井」が除外されてしまったことには気がついたのですが、他にも除外された交差点があるかどうかは確認できていません。
[^7]: 適当な見積もりなので、縦の道の数と横の道の数が等しいと仮定しています。
[^8]: ノード数が奇数のため、エッジの最大値が少数になってしまいました。$29*30=870$ の方が良い見積もりな気がします。
[^9]: 例えば、例外として「三条御池」が存在します。この交差点は三条通と御池通の交差点なのですが、これらの道はどちらも横の道です。交差点付近で三条通が斜め向きに変わるため、横の道同士の交差点が生じています。ここの交差点のバス停名は交差点名ではなく、「太秦天神川」になるため、今回のデータにはこの交差点は含まれていません。