最適なラーメンハシゴルート

[やること]
駅とラーメンのお店をネットワークで表現して、一番満足度の高いラーメンハシゴルートを計算します。
知識グラフを扱う練習が目的です。

[結果1]
青ノードが駅、赤ノードがラーメンのお店です。実際にあるお店です。
赤ノードの大きさが、ラーメンのお店の個人的なスコアです
エッジの数字はラーメンの値段、電車賃などを表します

[結果2]
以下のプログラムで、以下の設定で、スコアが一番高いルートを探索しました
設定：東京駅スタート、ラーメン2店舗ハシゴが上限
結果：['TOKYO', 'Rokurinsha', 'SHINJUKU', 'Konjiki']、1980円

[プログラム]

import networkx as nx
import matplotlib.pyplot as plt
import itertools

class Noodle():

    def __init__(self):
        #ネットワーク読み込み
        self.G = nx.read_edgelist('nodelist.txt', nodetype=str)
        nx.set_node_attributes(self.G, name='score', values=200)
        #スコア
        self.G.nodes["Rokurinsha"]["score"]=850
        self.G.nodes["Konjiki"]["score"]=900
        self.G.nodes["Ozeki"]["score"]=800
        self.G.nodes["TOKYO"]["score"]=0
        self.G.nodes["SHINJUKU"]["score"]=0
        self.G.nodes["SHIBUYA"]["score"]=0
        #コスト
        self.edge_labels={}
        self.edge_labels[("SHINJUKU","TOKYO")]=200
        self.edge_labels[("TOKYO","SHINJUKU")]=200
        self.edge_labels[("SHIBUYA","TOKYO")]=200
        self.edge_labels[("TOKYO","SHIBUYA")]=200
        self.edge_labels[("SHIBUYA","SHINJUKU")]=160
        self.edge_labels[("SHINJUKU","SHIBUYA")]=160
        self.edge_labels[("TOKYO","Rokurinsha")]=830
        self.edge_labels[("TOKYO","Hyottoko")]=670
        self.edge_labels[("TOKYO","Oboroduki")]=850
        self.edge_labels[("TOKYO","Hachigo")]=850
        self.edge_labels[("SHINJUKU","Gonokami")]=800
        self.edge_labels[("SHINJUKU","Funji")]=700
        self.edge_labels[("SHINJUKU","Konjiki")]=950
        self.edge_labels[("SHINJUKU","Sho")]=700
        self.edge_labels[("SHINJUKU","Hayashida")]=800
        self.edge_labels[("SHIBUYA","Kiraku")]=700
        self.edge_labels[("SHIBUYA","Hayashi")]=800
        self.edge_labels[("SHIBUYA","Ozeki")]=830

    #ネットワークをプロットする
    def plot(self):
        #色、サイズなど
        pos = nx.spring_layout(self.G, k=0.8)
        nx.draw_networkx_edges(self.G, pos, edge_color='y')
        c = ['blue' if n.isupper() else 'red' for n in self.G.nodes()]
        score_size = [1000 if n.isupper() else self.G.nodes[n]["score"] for n in self.G.nodes()]
        nx.draw_networkx_nodes(self.G, pos, node_color=c, alpha=0.5, node_size=score_size)
        nx.draw_networkx_edge_labels(self.G, pos, edge_labels=self.edge_labels, font_size=24)
        nx.draw_networkx_labels(self.G, pos, font_size=24)
        plt.figure(figsize=(10, 8))
        plt.axis('off')
        plt.show()

    #ルートのコスト計算
    def costscore_cal(self,route):
        score = 0
        cost = 0
        for a in range(len(route) - 1):
            if route[a] == route[a + 1]:
                continue
            else:
                if not (route[a].isupper()) and route[a + 1].isupper():
                    continue
                else:
                    cost = cost + self.edge_labels[(route[a], route[a + 1])]
                    score = score + self.G.nodes[route[a + 1]]["score"]
        return score, cost

    #店の一番近い駅
    def store2station(self,storename):
        station = {'Rokurinsha': 'TOKYO', 'Hyottoko': 'TOKYO', 'Oboroduki': 'TOKYO', 'Hachigo': 'TOKYO',
                   'Gonokami': 'SHINJUKU', 'Funji': 'SHINJUKU', 'Konjiki': 'SHINJUKU', 'Sho': 'SHINJUKU',
                   'Hayashida': 'SHINJUKU',
                   'Kiraku': 'SHIBUYA', 'Hayashi': 'SHIBUYA', 'Ozeki': 'SHIBUYA'}
        return station[storename]

    #全ルート生成
    def allroutes(self, noodle_count):
        noodle_shop = ('Rokurinsha', 'Hyottoko', 'Oboroduki', 'Hachigo',
                       'Gonokami', 'Funji', 'Konjiki', 'Sho', 'Hayashida',
                       'Kiraku', 'Hayashi', 'Ozeki')
        all_routes = ()
        for a in range(noodle_count):
            all_routes = all_routes + tuple(itertools.permutations(noodle_shop, a + 1))

        return all_routes

    #一番スコアが高いルート探索
    def allroutes_costscore_cal(self,allroutes, start_station):
        result_route = []
        for noodle_route in allroutes:
            list_kari = []
            for a in noodle_route:
                list_kari.append(start_station)
                list_kari.append(self.store2station(a))
                list_kari.append(a)
                list_kari.append(self.store2station(a))
            result_route.append(list_kari)

        result_score = []
        result_cost = []

        for a in result_route:
            score, cost = self.costscore_cal(a)
            result_score.append(score)
            result_cost.append(cost)

        result_route=result_route[result_score.index(max(result_score))]
        result_cost=result_cost[result_score.index(max(result_score))]

        return list(dict.fromkeys(result_route)),result_cost

if __name__=='__main__':

    n=Noodle()
    #2店舗はしごが限界
    allroutes=n.allroutes(2)
    #東京駅スタート
    result_route,cost=n.allroutes_costscore_cal(allroutes,"TOKYO")
    #結果：['TOKYO', 'Rokurinsha', 'SHINJUKU', 'Konjiki']
    print(result_route)
    #結果：1980円
    print(str(cost)+"円")
    n.plot()

[参考文献]
[1]Pythonでネットワークを分析・可視化しよう！必要手順まとめ
https://www.sejuku.net/blog/91371

[2]【Python】NetworkX 2.0の基礎的な使い方まとめ
https://qiita.com/kzm4269/items/081ff2fdb8a6b0a6112f