Graphillionで最長片道切符のルート探索(1) 稚内→中小国の最長ルートを求める

Windows版のPythonにGraphillionを入れられなくて四苦八苦しているのが嫌なので、Ubuntuの入った先代のノートPCを引っ張り出して本題である最長片道切符の話を始めることに。
基本的には以下の記事を参考にしていった。合わせて読んでいただきたい。

Home · takemaru/graphillion Wiki · GitHub

SWA氏流にいえば、片道切符のルートとしては、タイプL, タイプO, タイプPの3種類が考えられる。Grphillionでは、タイプLについてはGraphSet.pathsというメソッドによって、たとえば始点と終点を指定した経路については全パターンを数え上げることができる。タイプOは、GraphSet.cyclesを使用すれば同様にことが済む。厄介なのはタイプPで、これは個別の扱いが必要になってきそう。

まずは始めの一歩として、「稚内→中小国の最長ルート」を求めてみる。このルートは現在の最長片道切符における道内ルートと一致するはずである。厳密に言えば、始点は稚内だと決めつけることは出来ないのであるが、それはまた追って。

Graphillionでグラフを扱うには、まずuniverseを設定する。これは考えるべきグラフ全体の空間を教えてやる作業で、要は路線図をインプットするということ。
今回は北海道の路線図ということで、以下の様な(SWA氏のedges.csv風)ファイルを用意した。

1, 3, 125.6, 津軽海峡, 中小国→五稜郭
2, 3, 3.4, 函館, 函館→五稜郭
3, 4, 23.6, 函館, 五稜郭→大沼
4, 5, 22.5, 函館, 大沼→森
4, 32, 33.5, 函館支, 大沼→東森
32, 5, 1.8, 函館支, 東森→森
5, 6, 62.7, 函館, 森→長万部
...

カンマ区切りで、路線の始点(のコード)、終点(のコード)、営業キロの順になっている。グラフの「重み付き辺」を列挙する形式である。それ以降はすべてコメントとなる。
なお、函館本線の大沼→森間は経路が2つあるが、Graphillionでは全く同一の始点・終点をもつ辺が複数あるとエラーが発生するため、わざと支線上の東森で辺を分割してある。

これを読み込み、universeを設定する。スクリプトは以下の通り。

from graphillion import GraphSet as gs

filename = 'edges_hokkaido.txt'

f = open(filename, 'r')
lines = f.readlines()
f.close()

univ = [] # 路線図全体のリスト

for line in lines:
    dat = line.split(',')
    dat[2] = float(dat[2])
    edge = tuple(dat[0:3]) # tupleにしなければ辺として扱えない
    univ.append(edge)

gs.set_universe(univ) # universeを設定

実は、始点と終点のコードについては整数である必要はなく、この場合も文字列としてそのまま扱っている。駅名をそのまま入れてしまったほうが、目で見て分かりやすいかもしれない。プログラム上の扱いは面倒だが。

ここまでいったら、いよいよGraphillionの本領発揮。「稚内から中小国までの経路をすべて数え上げ、営業キロの長い順に表示する」には、以下のようなスクリプトを使う。

start = 30 # 稚内
end = 1 # 中小国
paths = gs.paths(start, goal)
len(paths) # 経路の総数を表示

for path in paths.max_iter():
    path # 最長経路を表示
    break # break しないと、複数のパスが降順で取り出される

以上。ねぇ簡単でしょ？　実行も一瞬で済む。
これで、「あの」最長経路が表示される。ただし、辺の順序はたどる順ではないので一見読みづらいかも。また、2番めに長い経路や最短経路も、最後の3行付近をいじれば同じく一瞬で分かる。

タイプPの取り扱いとか、始点を稚内以外にする話はまた今度。