2015-11-20

GraphillionのZDDデータ把持

Graphillion ZDD pickle

PythonのGraphillionモジュールではユニバースと呼ぶ全体グラフを定めた上で、サブフラフの集合をZDDデータ構造として持つ
その持ち方をしているのがGraphSetクラス
それが実際にどういう持ち方をしているのかを確認したい
実際GraphSetクラスのオブジェクトをテキストファイル保管するにあたって、pythonのデータオブジェクトのserialization機能を使って
- ユニバース　と
- 個々のZDD化したサブグラフ集合　と
をテキスト保存することができる
このテキスト化しているところがZDD構造のようなのでそれを探ることとする
ちなみに、ユニバースは個々のエッジ・頂点の「名称」を決めており、ZDDはエッジ・頂点を数値化したIDとして管理しているらしく、ユニバースを決め、GraphSetオブジェクトを作ったあとで、ユニバースを作り変えると、ZDD構造は変わらずに、エッジ・頂点の名称が入れ替わるらしい
まず、コンソール表示して、それをテキスト書き出ししてみる

from graphillion import GraphSet
from pickle

universe = [(1,2),(2,3),(3,4)]
GraphSet.set_universe(universe)
h1 = []
h2 = [(1,2)]
g0 = GraphSet([])
g0.dumps()
g1 = GraphSet([h1])
g1.dumps()
g2 = GraphSet([h2])
g2.dumps()
g3 = GraphSet([h1,h2])
g3.dumps()
g4 = GraphSet({})
g4.dumps()

ファイルに書き出すには

f = open('/home/ryamada/Desktop/hoge.txt','wb')
g4.dump(f)
f.close()
funiv = open('/home/ryamada/Desktop/univ.txt','wb')
pickle.dump(GraphSet.universe(),funiv)
funiv.close()

このテキストファイルから読み込むにはuniv.txtを読み込んでuniverse指定し、hoge.txtを読み込んで、GraphSetオブジェクトを作りなおせばよい

funiv = open('/home/ryamada/Desktop/univ.txt')
GraphSet.set_universe(pickle.load(funiv))
funiv.close()
fp = open('/home/ryamada/Desktop/hoge.txt')
gr = GraphSet.load(fp)
fp.close()

univ.tstとhoge.txtの中身は以下のような、改行の多いファイル

(lp0
(I1
I2
tp1
a(I2
I3
tp2
a(I3
I4
tp3
a.

コンソール表示にはGraphSetクラスのdumps()関数を使えばよくて、以下のようテキスト書き出し内容を表示させられる

>>> universe = [(1,2),(2,3),(3,4)]
>>> GraphSet.set_universe(universe)
>>> h1 = []
>>> h2 = [(1,2)]
>>> g0 = GraphSet([])
>>> g0.dumps()
'B\n.\n'
>>> g1 = GraphSet([h1])
>>> g1.dumps()
'T\n.\n'
>>> g2 = GraphSet([h2])
>>> g2.dumps()
'0 1 B T\n.\n'
>>> g3 = GraphSet([h1,h2])
>>> g3.dumps()
'1 1 T T\n.\n'
>>> g4 = GraphSet({})
>>> g4.dumps()
'5 3 T T\n9 2 5 5\n13 1 9 9\n.\n'

- コンソールで改行させて表示させるには

print(g4.dumps())

ユニバースの出力はI1,I2がintegerの1とかいう意味で、それ以外はカッコやカンマに相当する単純なもののようだ
ZDDのほうがぱっとはわからないので、検討することにする
- ZDDのdump表示の最終行は、"."
- それ以外の行は、基本的には、４つの成分からなる(例外は、T１字の行、B１字の行)
- ４成分は、左から、ノードID、ノードラベル(ユニバースをエッジのリストと見たときの、エッジの番地)、このノードには二つの識別可能なエッジがあるが、その左行エッジ(破線)の行先のノードIDが３番目、右行エッジ(実線)の行先のノードIDが４番目
- T,Bはそれぞれ「存在有り」「存在なし」に相当する
- これを確かめるには、graphillionソース内の、zdd.cファイルのメンバー関数dumpを読めばよい
- ノードIDは整数で、0始まり。いろいろな・ばらばらとした値が付くが、これは、ZDD作成操作の途中でノードを発生させては消去するなどした結果、欠番IDが生じるため(と思われる)
- 実際、ファイルに書きだした後で、このノードIDを適当に入れ替え、それをloadしてもZDD的には適切なものが再作成される