ZDD Graphillionを使う - ryamadaのコンピュータ・数学メモ

超高速グラフ列挙アルゴリズム?〈フカシギの数え方〉が拓く，組合せ問題への新アプローチ?

作者: ERATO 湊離散構造処理系プロジェクト,湊真一
出版社/メーカー: 森北出版
発売日: 2015/04/08
メディア: 単行本（ソフトカバー）
この商品を含むブログ (4件) を見る

が出版され、そこにpythonのgithub(こちらが紹介されているので使ってみる。以前も使ってみようと思ったものの、うまく回せなかったけれど、pythonも少しわかってきたしやり直し
以下は数え上げとGraphillionの動画

教えられるがまま(こちら)に沿ってインストール
- "Mac OS X で Graphillion を使うには、Apple が配布している Xcode の Clang をお使い下さい。"という件についてはYosemiteでは特に何もせずにデフォルトでやったけれど、ひとまず回っている
- まず、コンソールで以下の３行

sudo easy_install networkx
sudo easy_install matplotlib
sudo easy_install graphillion

- そしてpythonを起動し

python

- ひたすらなぞる
  - 格子グラフを作り、描図する

from graphillion import GraphSet # ライブラリのインストール
import graphillion.tutorial as tl # tutorialに帰属する関数を簡易に呼び出せるように簡易名つきにする
universe = tl.grid(8,8) # グラフ全体を作る。(8+1)^2 grid
GraphSet.set_universe(universe) # エッジリスト（重みをつけてもよい）を引数に探索方法と探索開始位置情報を持った「グラフ」を作る。GraphSetオブジェクトはGraphillion処理の基本。まずuniverseを定義し、その他もろもろのグラフ集合を作っていく
tl.draw(universe) # 描図する

- - universeというのはただのエッジリストらしい

>>> universe
[(1, 2), (1, 10), (2, 11), (2, 3), (3, 12), (3, 4), (4, 5), (4, 13), (5, 14), (5, 6), (6, 15), (6, 7), (7, 8), (7, 16), (8, 9), (8, 17), (9, 18), (10, 19), (10, 11), (11, 20), (11, 12), (12, 13), (12, 21), (13, 22), (13, 14), (14, 23), (14, 15), (15, 16), (15, 24), (16, 17), (16, 25), (17, 18), (17, 26), (18, 27), (19, 28), (19, 20), (20, 21), (20, 29), (21, 30), (21, 22), (22, 31), (22, 23), (23, 24), (23, 32), (24, 25), (24, 33), (25, 26), (25, 34), (26, 27), (26, 35), (27, 36), (28, 29), (28, 37), (29, 38), (29, 30), (30, 39), (30, 31), (31, 32), (31, 40), (32, 33), (32, 41), (33, 34), (33, 42), (34, 35), (34, 43), (35, 44), (35, 36), (36, 45), (37, 46), (37, 38), (38, 47), (38, 39), (39, 40), (39, 48), (40, 41), (40, 49), (41, 42), (41, 50), (42, 43), (42, 51), (43, 52), (43, 44), (44, 45), (44, 53), (45, 54), (46, 55), (46, 47), (47, 48), (47, 56), (48, 49), (48, 57), (49, 50), (49, 58), (50, 51), (50, 59), (51, 60), (51, 52), (52, 53), (52, 61), (53, 62), (53, 54), (54, 63), (55, 56), (55, 64), (56, 57), (56, 65), (57, 58), (57, 66), (58, 67), (58, 59), (59, 68), (59, 60), (60, 61), (60, 69), (61, 70), (61, 62), (62, 71), (62, 63), (63, 72), (64, 65), (64, 73), (65, 66), (65, 74), (66, 75), (66, 67), (67, 76), (67, 68), (68, 69), (68, 77), (69, 78), (69, 70), (70, 79), (70, 71), (71, 72), (71, 80), (72, 81), (73, 74), (74, 75), (75, 76), (76, 77), (77, 78), (78, 79), (79, 80), (80, 81)]
>>>

- - 関数がわからなければhelpを使う

>>> help(GraphSet.set_universe)

Help on function set_universe in module graphillion.graphset:

set_universe(universe, traversal='bfs', source=None)
    Registers the new universe.
    
    Examples:
      >>> GraphSet.set_universe([(1, 2, 2.0), (1, 4, -3.0), (2, 3)])
    
    Args:
      universe: A list of edges that represents the new universe.
        An edge may come along with an edge weight, which can be
        positive as well as negative (or 1.0 if not specified).
    
      traversal: Optional.  This argument specifies the order of
        edges to be processed in the internal graphset operations.
        The default is 'bfs', the breadth-first search from
        `source`.  Other options include 'dfs', the depth-first
        search, and 'as-is', the order of `universe` list.
    
      source: Optional.  This argument specifies the starting
        point of the edge traversal.

- - helpを抜けるには

- - と打つ
  - 始点・終点ノードIDを与え、そこを結ぶパスを列挙して、その数を表示する

start = 1
goal = 81
paths = GraphSet.paths(start,goal) # 個々のパスはグラフ。それをリストとして格納
len(paths) # パスグラフの数を表示
|python|<
tl.draw(paths.choice()) # pathsに格納されたパスグラフのうちの一つを選んで描図する
# パスグラフを一つずつ取り出し、それを表示する（すぐに止めれば、はじめのパスグラフが見える）。エッジリストとして表示される
for path in paths:
    path

# Ctrl-C で止めないと何年もかかってしまう
tl.draw(paths.choice())  # パスのひとつを描図する

- - 少し複雑にする。スタートからある点(key)を通ってからゴール(treasure)に着くようなパスを列挙する

key = 64
treasure = 18
# まず始点・経由点を指定し、そのうち、本当のゴールを通らないパスグラフの集合を作る
paths_to_key = GraphSet.paths(start, key).excluding(treasure)  # 宝箱を通らずに鍵にたどり着くパス
# 作った集合paths_to_keyを含み、かつゴールを含むようなパスグラフを選ぶ
treasure_paths = paths.including(paths_to_key).including(treasure)  # 鍵と宝箱を通ってゴールにたどり着くパス
len(treasure_paths)
789438891932744
tl.draw(treasure_paths.choice())  # パスのひとつを表示する
# 制約条件付きのパス数は条件なしのパス数より小さい
treasure_paths < paths

i = 0
data = []
for path in treasure_paths.rand_iter():
	data.append(tl.how_many_turns(path))  # パスが曲がる回数を数えて、その結果を継ぎ足しで格納する。10000パス処理したら終了
	if i == 10000: break
	i += 1

# ヒストグラムにする
tl.hist(data)

鍵をとってから宝にたどり着く場合の曲がる回数

i = 0
for path in treasure_paths.min_iter():
	tl.how_many_turns(path)

	break  # break しないと、複数のパスが昇順で取り出される
universe = tl.grid(8, 8, 0.37)  # 8x8 の格子から 37 % の辺が取り除かれる
GraphSet.set_universe(universe)
tl.draw(universe)
# 発電所の位置
generators = [1, 9, 73, 81]
# ルートノードを指定し、スパニング木の集合としての森グラフを作る。
forests = GraphSet.forests(roots=generators, is_spanning=True)  # forest にはすべての家庭をカバーし、かつループのない電力フローが格納される
len(forests) # 森のパターンの数
tl.draw(forests.choice()) # 森を一つ選んで描図する

too_large_trees = GraphSet()  # 空のグラフセット
for substation in generators:
# "|="はaugmented assignment なのでx +=1がx = x+1であるように、x |= zはx = x | zとなり、|っていうのは集合で言えば重複なしで付け加える処理に相当する
	too_large_trees |= GraphSet.trees(root=substation).larger(23)  # 危険な電力フロー
	
safe_forests = forests.excluding(too_large_trees)  # 危険なケースを取り除いた、安全な電力フロー
len(safe_forests)
tl.draw(safe_forests.choice())

closed_switches = (forests - safe_forests).choice()  # 安全でない電力フローにおけるオン状態(closed)スイッチの集合
tl.draw(closed_switches)

scores = {}  # 新しい設定におけるオン状態スイッチのスコア（デフォルトは 0）
for switch in universe:
	# もし現在の状態がオンならスコアは 1、でなければスコアは -1。switchはclosedする前にオンのエッジで、それについて、closedした後の状態に応じて+1,-1をアサインしている
	scores[switch] = 1 if switch in closed_switches else -1

for forest in safe_forests.max_iter(scores):
	tl.draw(forest)
	break  # break しないと、複数の設定がスコアの高いものから取り出される

networkXと合わせて使う

ntwksg = treasure_paths.choice() # networkXのグラフオブジェクト
nx.draw(ntwksg)
import matplotlib.pyplot as plt
plt.show()
nx.draw_spectral(ntwksg)
plt.show()

graphillionは、universeという全体の中にある部分集合の操作を行うが、それには、pythonの集合演算が用いられる。pythonの集合演算は大きく分けて変更可能なsetと変更不可能(で、そのおかげでハッシュ値付置、辞書化可能）なfrozensetの２種類がある
- pythonのset,frozensetについてはこちらを参考に