networkxで最長片道切符のルートを算出しようとするが…

今回は、networkxというライブラリを使って最長片道切符を出そうとしたという記事です。以前使用したGraphillionでは、容量が大きすぎて計算が不能となるケースがありました。そこで、今回はnetworkxというライブラリを使って計算を実行してみました。コードは以下のようになります。

file1 = "honshu_networkx.txt"

Graph = nx.Graph()

def station_pick(lines):
    station_list = []
    for line in lines:
        dat = line.split(",")
        for i in range(2):
            station = dat[i]
            if station not in station_list:
                station_list.append(station)
    return station_list

def count_distance(path, edges):
    distance = 0
    f1_2 = open(file1, "r")
    lines = f1_2.readlines()
    f1_2.close()
    for i in range(len(path)-1):
        word1 = path[i] + "," + path[i+1]
        word2 = path[i+1] + "," + path[i]
        for line in lines:
            if word1 in line or word2 in line:
                dat = line.split(",")
                distance += float(dat[2])
    return distance

f1 = open(file1,"r")
lines = f1.readlines()
station_list = station_pick(lines)
f1.close()
edge1 = []
edge2 = []
for line in lines:
    dat = line.split(",")
    data1 = (dat[0], dat[1])
    data2 = (dat[0], dat[1], float(dat[2]))
    edge1.append(data1)
    edge2.append(data2)

Graph.add_nodes_from(station_list)
Graph.add_weighted_edges_from(edge2)
longest_distance = 0
for path in nx.all_simple_paths(Graph, source='新青森', target='門司'):
    all_distance = count_distance(path, edge2)
    if longest_distance < all_distance:
        print(path)
        print(all_distance)
        longest_distance = all_distance
    else:
        continue

データセットについては自作をしました。なぜ、これを用いたかというとGraphillionの作者の方が大きなデータセットの場合にnetworkxの使用を薦めていたからからと思ったのですが、ちょっとミスリードだった気がしてきました。

github.com

結果として、networkxの使用はあまり向かない気がします。理由としては最初に経路をを算出してから徐々に最長の経路を算出していきますが、例えば、大阪から門司の最長経路を出す際に、既に鳥取から門司までの最長経路が出ているにも関わらずもう一度再計算しようとする印象を受けました。計算に無駄が多いため、結局約2日掛けても終わりませんでした。