Pythonからgraphvizを使うには

graphvizというものがあります。ネットワーク構成を独自言語で記述した上でツールにかけると画像を生成してくれます。ネットワーク構成の画像を描くなら、GUIベースのお絵かきソフトを使えば、おそらく隅々まで自分好みの画像ができると思いますが、拘れば拘るほど、いくらでも時間が喰われていくことでしょう。それに対してgraphvizはネットワーク構成の論理的な構造を記述しておいて、画像を自動生成するので、気に入らない点も出てくるかもしれませんが、圧倒的に手間暇が削減できます。これはLaTeXの発想にも通じるところがあると思います。

 

graphvizを単独で使うのではなく、Pythonから利用しようとしたら、どうしたら良いのでしょうか。調べてみるとGraphvizとPyGraphvizがあるようです。Pythonからgraphvizを利用する事例を検索すると、双方とも情報が見つかります。

 

それぞれを試しに使ってみましたが、各々特徴があって、どちらかが良いとか悪いとか判断するのは難しそうです。どうしたものかと思っていたら「Python から Graphviz を使う - networkx & PyGraphviz、pydot など」という記事を見つけました。そこには次のような記述がありました。

pyGraphviz というのもあるのを知る。ロスアラモス研究所 で開発されていて、グラフ操作のための networkx と、グラフ描画のための pyGraphviz という感じのようだ。 

 

PyGraphvizとロスアラモス研究所との関係は不明ですが、PyGraphvizのサイトには「PyGraphviz provides a similar programming interface to NetworkX (https://networkx.org).」と書かれていることは確かです。

 

そもそもPythonからgraphvizを利用したいと考えたのは、NetworkXを使用してグラフ構造を出力したからなのです。そうであれば、これはもうPyGraphvizを利用するしかないのではないかという気になってきました。 

ネットワーク問題を解くためのPythonライブラリは何が良い？

国鉄時代からありますが、日本国内を一筆書きで乗り継ぐ片道切符を考えるという問題があります。『最長片道切符の旅』が有名ですが、これが端緒ではありません。問題を考えるだけなら、時刻表と暇な時間があれば十分ですが、現実に旅行してみようとすると資金面でも現実の時間も必要ですし、体力も必要です。

 

この問題を解くために時刻表とにらめっこするのも一興ですが、コンピュータを使って解いてみるのも楽しそうです。これはネットワーク問題ということになると思いますが、アルゴリズムを最初から自分で実装するよりも、何か既存のライブラリを使う方が、不必要に苦労せずにすむでしょう。いろいろなライブラリがあるとは思いますが、Pythonで利用できるものを考えてみようかと思います。

 

Pythonでネットワーク問題を解くためのライブラリも、いろいろあると思います。何を使っても良いのですが、有名なところでは「NetworkX」があります。また『Python計算機科学新教本』では「3章制約充足問題」や「4章グラフ問題」が参考になりそうです。他にもライブラリはいろいろありそうですが、各ライブラリを比較検討するのが目的ではないので、横道に逸れないように注意して、NetworkXを使ってみようかとも考えています。

 

いきなり日本全国の鉄道路線網を扱おうとすると大変なので、最初に北海道、四国、九州のどこかを使って、具体的な実装を試してみようかと思います。それがうまくいったら、日本全国に広げようかと思います。

 

ただし、国鉄時代とは違い、現在のJR四国は、日本国内の一筆書きの片道切符では対象から外れています。なぜなら、国鉄時代には、四国と本州の間には連絡船が東西に2航路存在していましたが、現在は岡山から四国にわたることしかできません。一筆書きのルールは同じ路線を複数回使用できないため、いったん四国に入ってしまうと出ることが出来ないのです。

 

またJR北海道が路線廃止をすすめていますし、在来線だけでは北海道と本州を移動できなくなっています。このあたりは一筆書きのルールを定義するやり方でなんとかなるでしょう。

Wizardryで冒険を始める前にマップを用意する

Windows10上でPC98エミュレータ「T98-NEXT」を使い、「Wizardry COLLECTION」のWizardry #1をプレイしてみようかと思っています。過去にPC-9801vm2でプレイした際には、ダンジョンのマップを方眼紙に記録していました。今回もそれでも構わないのですが、このゲームに没頭できるだけの時間を確保することは出来ないと思いますし、記録を紙ベースで残すと保管する手間が大変なので、別の方法を考えます。

 

今は何かの記録を残していく場合、TiddlyWikiを使うようにしています。ですからWizardryの冒険に先立ち、TW5のファイルをひとつ作成しました。Wizardryの情報も、PC98エミュレータの情報も、いろいろな情報を記録していくつもりです。そうなるとダンジョンのマップもTW5に記録していこうと思います。

 

マップは20x20なので、TW5のテーブル機能を使えば表現できそうです。しかし単なる壁と扉の区別が必要ですし、場合によっては注意事項をメモしたりする事があるかもしれません。そのような要望を満たすのは、TW5のテーブル機能では難しそうでした。そこで次善の策として編み出した方法を使うと、なんとかマップを表現できそうです。ただし手作業で書き下すのは大変なので、Pythonで雛形を生成させるようにしました。これでマップの問題は解決です。

 

#!/usr/bin/python3

print("|tc-table-no-border|k")

print("|", end="||")
for j in range(20):
    print(" %d " % j, end="||")
print("")

print("|", end="|+|")
for j in range(20):
    print(" ----- ", end="|+|")
print("")

for i in reversed(range(20)):
    print("|",i, end="|||")
    for j in range(20):
        print(" [[%d,%d|WxLyP%02d%02d]] " % (j, i, j, i), end="|||")
    print(i,"|")

    print("|", end="|+|")
    for j in range(20):
        print(" ----- ", end="|+|")
    print("")

print("|", end="||")
for j in range(20):
    print(" %d " % j, end="||")
print("")
#[EOF]

vscodeとPythonと『Python計算機科学新教本』

オライリーから『Python計算機科学新教本』という書籍が出版されています。大雑把に言ってしまうとアルゴリズムについて書かれた本ですが、Pythonを使って説明しているのが今風です。同じ著者から他の言語で説明している書籍がO'Reillyから出ていますが、和訳は無いようです。

 

この本の「3章 制約充足問題」や「4章 グラフ問題」を勉強してみようと思っています。書籍の中でソースコードも提示されていますし、ダウンロードサービスもあるようですから、Pythonが動く環境さえあれば、勉強するための最低限の環境は整います。それでも構わないのですが、最近はやりのVisual Studio Codeを使ってみようかと思います。

vscodeとWSLを連携させることが出来るようですし、Pythonを扱うための機能も揃っているようです。Web上には多くの記事がありますが、「Visual Studio Codeで快適Pythonライフ」を参考にしてみました。Pythonをコーディングするだけなら、WSL上でviを使うのが手っ取り早いのですが、vscodeならデバッガを利用できるようなので、そこに魅力を感じています。

BeautifulSoupでHTMLファイルから情報を取り出す

HTMLファイルの中でTABLEを使っている箇所から情報を取り出そうと思って調べていると「BeautifulSoup」というものを見つけました。これが全体として何が出来るのかは分かっていませんが、HTMLのTABLEで組まれている箇所から情報を抜き出すことは出来ました。最終的にはCSVにして情報を蓄積していこうと考えていますが、そのあたりをどのようにするかは考えているところです。

 

Webを検索すればBeautifulSoupを使った事例が見つかります。汎用的にしていくにはロジックが複雑になると思いますが、情報を抜き出すところだけなら、簡単でした。

#!/usr/bin/python3

import sys

f = open(sys.argv[1], "r", encoding="shift_jis")
data = f.read()
f.close()

import csv
from bs4 import BeautifulSoup

soup = BeautifulSoup(data, "html.parser")
for tab in soup.find_all("table"):
    with open("monex.csv", "w") as file:
        writer = csv.writer(file)
        for row in tab.find_all("tr"):
            csvRow = []
            for cell in row.findAll(["td", "th"]):
                s = cell.get_text().strip()
                if len(s) != 0:
                    csvRow.append(s)
            writer.writerow(csvRow)
# [EOF]

HTMLから特定の情報を抜き出すにはXSLTも使えそうです。XSLTは勉強中なので、どのようにしたら良いのか分かりませんが、きっと簡潔にできるのでしょう。またはsed、awkなどで文字列を解釈するロジックを書くことも出来るのかもしれません。それほど長々としてスクリプトにはならないと思いますが、BeautilfulSoupやXSLTほど簡潔にはならない気がします。

FreeBSDのpackageでPython3が重複する

自宅では中古のノートPCにFreeBSD/amd64を入れて使用しています。以前にFreeBSD/i386を使っていた頃は、アプリケーションを自前でコンパイルしていましたが、今はコンパイル済みのバイナリを入れるだけになりました。以前もそうでしたが、依存関係にあるアプリケーションは勝手にインストールしてくれるので、それが有り難かったり、困ったものだったりして、単純に嬉しいとは言い難いところです。

最近Python3が異なるマイナーバージョンで入ったことに、ふとしたことで気付きました。

> pkg info -a | grep '^python'
python27-2.7.18                Interpreted object-oriented programming language
python36-3.6.10                Interpreted object-oriented programming language
python37-3.7.7_1               Interpreted object-oriented programming language

Python3を明示的に入れた覚えはないので、何かのアプリケーションの依存関係にあって、インストールされたのだと思います。それは良いのですが、アプリケーションが期待するPython3のマイナーバージョンが決め打ちになっていたのではないかと思います。それで複数のマイナーバージョンが入ってしまったのではないかと思います。

このような現象は他にもあって、LLVMについても複数バージョンが入っているのに気付いたりします。今の時代は昔と違ってディスク容量に余裕があるので、複数バージョンが入っていても気にしなくても良いのかもしれません。

しかしながら、Python2とPython3が入っているのは許容できなくもありませんが、Python36とPython37が入っているのは、なんとかならないかと思います。

PythonにNetworkXをインストール

最長片道切符のグラフ問題を扱うために、PythonにNetworkXを導入してみました。導入するのは簡単ですが、pipを利用します。Python 3.4以降には標準で入っているという情報がありますが、FreeBSDのパッケージで入れたpython 3.6には入っていないようでした。

tpe530c> python3.6 -m pip list
/usr/local/bin/python3.6: No module named pip
tpe530c> uname -a
FreeBSD tpe530c 12.0-RELEASE-p8 FreeBSD 12.0-RELEASE-p8 GENERIC  amd64
tpe530c> python3.6 -V
Python 3.6.9
furusawa@tpe530c> python3.6
Python 3.6.9 (default, Jul 11 2019, 01:10:39)
[GCC 4.2.1 Compatible FreeBSD Clang 6.0.1 (tags/RELEASE_601/final 335540)] on freebsd12
Type "help", "copyright", "credits" or "license" for more information.
>>>

pipを導入するのは簡単ですが、パーミッションの都合によりrootで操作する必要があります。

# curl -kL https://bootstrap.pypa.io/get-pip.py | python3.6
tpe530c> python3.6 -m pip list
Package    Version
---------- -------
decorator  4.4.0 
networkx   2.3   
pip        19.2.1
setuptools 41.0.1
wheel      0.33.4

グラフ構造を扱うためにNetworkXが必須かというと、そういうわけでもないと思います。しかし重み付きグラフの情報を記したファイルを読み込んでくれるヘルパー関数があるので、自前で似たようなプログラムを書くより楽ではないかと思います。

NetworkXを極めるよりも、最長片道切符のグラフ問題を解くために必要なプログラムを書けるようにするため、NetworkXの使い方を学んでいきたいと思います。