graphillion - 莫大な数の部分グラフを扱う Python

今日の内容
graphillion - 莫大な数の部分
グラフを扱う Python ライブラリ
• graphillion ライブラリの紹介
• graphillion ライブラリでできること
• graphillion の内部データ構造
• ZDD
奈良先端科学技術大学院大学
川原純
• graphillion が使用しているアルゴリズム
• フロンティア法
• 適用事例紹介 (1), (2), (3)
謝辞
本スライドで使用している図の一部と全適用事例は発売予定の書籍
「超高速グラフ列挙アルゴリズム」（仮題）
のドラフト版から引用しています。図の引用は「ZDD書籍から引用」と明示しています。
graphillion ライブラリの作者井上武さん，岩下洋哲さん
書籍の著者湊真一先生，斎藤寿樹先生，安田宜仁さん，井上武さん，
羽室行信先生，前川浩基さん，丸橋弘明さん，堀山貴史先生，その他の著者の皆様，
JST ERATO 湊離散構造処理系プロジェクトメンバーの皆様に感謝いたします。
graphillion とは
2
graphillion とは
http://graphillion.org
NTT研究所井上武氏作
http://graphillion.org
NTT研究所井上武氏作
• 部分グラフ列挙ツール
• グラフに関する様々な最適化問題を解く
• 部分グラフ列挙ツール
• グラフに関する様々な最適化問題を解く
グラフとは
頂点
辺
グラフ
路線図
地図（の隣接関係）
3
知り合い関係
「もの」と、「もの」のつながりを
抽象化して表したもの
4
部分グラフ
部分グラフ列挙
• 与えられたグラフの一部分からなるグラフ
• 与えられた条件を満たす部分グラフをすべて求める
• 例:
s
与えられたグラフ
s から t までの、
同じ頂点を通らない経路は？
部分グラフの例
• 経路（パス）や全域木などは部分グラフ
t
t
s
全域木
s-t 経路（s-t パス）
5
6
部分グラフ列挙
部分グラフ列挙
• 与えられた条件を満たす部分グラフをすべて求める
• 例:
全体グラフ (universe)
• 与えられた条件を満たす部分グラフをすべて求める
• 例:
s
部分グラフ
s から t までの、
同じ頂点を通らない経路は？
列挙して何が嬉しいのか？
後述
全体グラフ (universe)
s
t
t
7
8
graphillion を使ってみよう(1)
graphillion を使ってみよう(2)
• インストール (Mac, Linux)
• グラフの表現
全体グラフ (universe)
• networkx ライブラリと同じ
または、
s=1
2
3
4
5
6
7
8
http://graphillion.org
$ easy_install graphillion
からダウンロード、ビルド
• python インタプリタを起動
$ python
• ライブラリのインポート
頂点: オブジェクト（何でもよい）
本講演では1,2,3,...
t=9
辺: 頂点のタプル
(1, 2) や (2, 3) など
グラフ: 辺のリスト
[(1, 2), (1, 4), (2, 3), (2, 5), (3, 6), (4, 5), (4, 7),
(5, 6), (5, 8), (6, 9), (7, 8), (8, 9)]
• 全体グラフの設定
>>> from graphillion import GraphSet
>>> GraphSet.set_universe( [(1, 2), (1, 4), (2, 3), (2, 5),
(3, 6), (4, 5), (4, 7),(5, 6), (5, 8), (6, 9), (7, 8), (8, 9)] )
9
graphillion を使ってみよう(3)
• s-t 経路を列挙する
graphillion でできること(1)
全体グラフ (universe)
s=1 2 3
4
5
7
8
>>> paths = GraphSet.paths(1, 9)
10
• 数のカウント
6
>>> print paths.len()
12
• 各部分グラフに対する処理
t=9
>>> for p in paths:
...
print p
引数に始点と終点
全体グラフ (universe)
3
2
s=1
4
5
7
8
6
t=9
paths 変数に、部分グラフの集合が格納される
11
12
graphillion でできること(1)
• 数のカウント
>>> print paths.len()
12
• 各部分グラフに対する処理
全体グラフ (universe)
3
2
s=1
4
5
7
8
2),
2),
2),
2),
2),
2),
4),
4),
4),
4),
4),
4),
(2,
(2,
(2,
(2,
(2,
(2,
(2,
(2,
(4,
(4,
(4,
(4,
3),
3),
3),
5),
5),
5),
3),
3),
5),
5),
7),
7),
(3,
(3,
(3,
(4,
(5,
(5,
(2,
(2,
(5,
(5,
(5,
(7,
6),
6),
6),
5),
6),
8),
5),
5),
6),
8),
6),
8),
(4,
(5,
(6,
(4,
(6,
(8,
(3,
(3,
(6,
(8,
(5,
(8,
5),
6),
9)]
7),
9)]
9)]
6),
6),
9)]
9)]
8),
9)]
• 経路の短い順に、各部分グラフを処理
6
t=9
>>> for p in paths:
...
print p
...
[(1,
[(1,
[(1,
[(1,
[(1,
[(1,
[(1,
[(1,
[(1,
[(1,
[(1,
[(1,
(universe)
graphillion でできること(2)s =全体グラフ
1 2 3
(7, 8), (8, 9)]
(4, 5), (6, 9)]
(4, 7), (5, 8), (6, 9), (7, 8)]
5
7
8
6
t=9
>>> for p in paths.min_iter():
...
print p
...
[(1,
[(1,
[(1,
[(1,
[(1,
[(1,
[(1,
[(1,
[(1,
[(1,
[(1,
[(1,
(4, 7), (5, 6), (7, 8), (8, 9)]
(5, 8), (8, 9)]
4
4),
4),
4),
2),
2),
2),
4),
4),
2),
2),
4),
2),
(4,
(4,
(4,
(2,
(2,
(2,
(4,
(2,
(2,
(2,
(2,
(2,
7),
5),
5),
5),
5),
3),
7),
3),
5),
3),
3),
3),
(7,
(5,
(5,
(5,
(5,
(3,
(5,
(2,
(4,
(3,
(2,
(3,
8),
8),
6),
8),
6),
6),
6),
5),
5),
6),
5),
6),
(8,
(8,
(6,
(8,
(6,
(6,
(5,
(3,
(4,
(5,
(3,
(4,
9)]
9)]
9)]
9)]
9)]
9)]
8),
6),
7),
6),
6),
5),
(6,
(4,
(7,
(5,
(4,
(4,
9),
5),
8),
8),
7),
7),
(7,
(6,
(8,
(8,
(5,
(5,
8)]
9)]
9)]
9)]
8), (6, 9), (7, 8)]
6), (7, 8), (8, 9)]
(6, 9), (7, 8)]
13
14
(universe)
graphillion でできること(3)s =全体グラフ
1 2 3
• （一様）ランダムに1つ抽出
>>> p = paths.choice()
>>> print p
4
5
7
8
6
t=9
graphillion でできること(4)
• さらに、頂点3を通らない
経路のみを抽出
>>> paths3 = paths2.excluding(3)
[(1, 2), (2, 3), (3, 6), (4, 5), (4, 7), (5, 6), (7, 8), (8, 9)]
全体グラフ (universe)
3
2
s=1
4
5
7
8
6
t=9
• 頂点5を通る経路のみを抽出
>>> paths2 = paths.including(5)
15
16
1.7
graphillion でできること(5)
• 辺に重みをつけて、重みの和が
最大・最小の部分グラフを求める
3.2
...
全体グラフ (universe)
s=1 2 3
>>> weights = {}
>>> weights[(1, 2)] = 3.2
>>> weights[(1, 4)] = 1.7
# （略）
>>> weights[(8, 9)] = 6.2
>>>
>>> iter = paths3.max_iter(weights)
>>> p1 = iter.next()
>>> p2 = iter.next()
4
5
7
8
graphillion の威力(1)
データ取得: 駅データ.jp
http://ekidata.jp
• JR（Japan Railway）の路線図
6
頂点数: 4534, 辺数: 4646
t=9
6.2
一番長い経路
二番目に長い経路
辺の重みは、辺をキー、重みをバリューとするディクショナリで与える
最北駅（稚内）～最南駅（西大山）の経路
>>> GraphSet.set_universe(jrmap)
>>> weights = read_weights()
>>>
>>> paths = GraphSet.paths(“1111553”, “1193021”)
>>> paths.len()
1112870539692503649611518720
計算時間: 258.16 秒
Intel Xeon E5-1620 3.60GHz
使用メモリ: 12.4 GB
経路は圧縮して保持されている
17
18
ZDD書籍から引用
graphillion の威力(2)
graphillion で扱える部分グラフの種類
• 経路
• JR（Japan Railway）の路線図
頂点数: 4534, 辺数: 4646
• s-t 経路
• ハミルトン経路（すべての頂点を通る）
• サイクル（1周して戻る）
最北駅（稚内）～最南駅（西大山）の経路
最長経路を求める
>>> max_path = paths.max_iter(weights).next()
>>> print len(max_path)
2650
>>> sum = 0.0
>>> for edge in max_path:
...
sum += weights[edge]
...
>>> print sum
10337.3
•木
駅数 ― 1
• 森、全域森
• 木、全域木
• 連結成分
• マッチング
• クリーク（頂点同士がすべて結ばれている頂点集合）
総距離
最短経路も求まるが、ダイクストラ法などの既存アルゴリズムの方が速い
19
ZDD書籍から引用
• その他、様々な制約を課した部分グラフ
20
今日の内容
graphillion で用いられるデータ構造
ゼロサプレス型二分決定グラフ
• graphillion ライブラリの紹介
• Zero-suppressed Binary Decision Diagram (ZDD) [S.Minato 93]
• 集合族（集合の集合）をコンパクトに効率良く記憶
• graphillion ライブラリでできること
• graphillion の内部データ構造
• ZDD
• graphillion が使用しているアルゴリズム
特殊な形をしたグラフ
• フロンティア法
• 適用事例紹介 (1), (2), (3)
{e1, e2, e5}, {e1, e3, e4, e7}, {e1, e5, e8, e12},
{e3, e7, e9}, {e2, e6, e7, e8, e9, e10}, {e4},
{e1, e4, e6, e8}, {e1, e2, e5, e8}, {e1, e9, e10},
{e4, e5, e9}, {e1, e3, e4, e5, e9, e11}, {e6, e7},
{e1, e4, e5}, {e1, e5, e8, e10}, {e2, e5, e11},
{e5, e8, e9}, {e2, e3, e7, e8}, {e10, e11, e12},
…
ZDD
21
22
ZDD の基本
ZDD の基本
root
e1
0
{ { e1 e3 } , { e2 e5 } , { e2 e4 e5 }
{ e3 e4 e5 } , { e3 e5 } ,
{ e5 } }
0
1
e2
e3
{ { e1 e3 } , { e2 e5 } , { e2 e4 e5 }
{ e3 e4 e5 } , { e3 e5 } ,
{ e5 } }
e3
e3
e3
e4
e5
0
1
e2
e4
集合族
e1
0 : 0 終端 (0-terminal)
1 : 1 終端 (1-terminal)
1
ei
ZDD
: ノード
それぞれ
1つずつもつ
e5
e1 ～ e5 いずれかのラベル
e1 , e2,…, e5 の順序
0
1
ZDD
要素は {e1, e2 , e3 , e4, e5} の5種類で固定
（事前に固定する必要あり）
23
24
ZDD の基本
ZDD の基本
root
ノードは0枝と1枝を1つずつもつ
e1
0
{ { e1 e3 } , { e2 e5 } , { e2 e4 e5 }
{ e3 e4 e5 } , { e3 e5 } ,
{ e5 } }
{ { e1 e3 } , { e2 e5 } , { e2 e4 e5 }
{ e3 e4 e5 } , { e3 e5 } ,
{ e5 } }
e3
1 : 1 終端 (1-terminal)
ei
: ノード
それぞれ
1つずつもつ
e3
e3
e4
e5
e5
0
e1 ～ e5 いずれかのラベル
e1 , e2,…, e5 の順序
1
e2
e4
0 : 0 終端 (0-terminal)
e1
0
1
e2
e3
root
ノードは0枝と1枝を1つずつもつ
1つの集合が、
root から 1 までの1本のパスに対応
1
0
ZDD
1
ZDD
0
: 0-terminal
1
: 1-terminal
ei
: node with label
e1
～
e5
25
ZDD の基本
26
ZDD の基本
root
ノードは0枝と1枝を1つずつもつ
e1
0
{ { e1 e3 } , { e2 e5 } , { e2 e4 e5 }
{ e3 e4 e5 } , { e3 e5 } ,
{ e5 } }
{ { e1 e3 } , { e2 e5 } , { e2 e4 e5 }
{ e3 e4 e5 } , { e3 e5 } ,
{ e5 } }
e3
e3
e5
1つの集合が、
root から 1 までの1本のパスに対応
1
ZDD
0
: 0-terminal
1
: 1-terminal
ei
: node with label
e1
～
e3
e4
e5
0
1
e2
e4
1つの集合が、
root から 1 までの1本のパスに対応
e1
0
1
e2
e3
root
ノードは0枝と1枝を1つずつもつ
0
1
ZDD
e5
27
0
: 0-terminal
1
: 1-terminal
ei
: node with label
e1
～
e5
28
ZDD の基本
ZDD の基本
ノード共有ルール
ZDD は2分木を圧縮したものとみなすことができる
{ { e1 e3 } , { e2 e5 } , { e2 e4 e5 },
}
{ e3 e4 e5 } , { e3 e5 } ,
{ e5 }
e1 1
0
e1 = 0 e1 e1 = 1
e2
e2
e2
e2 = 1 e2 = 0
e2 = 1
e2 = 0
e3
e3
e3
e3
e3
e3
1
0
e4
e4
e5
...
...
0
1 1 1 1
1
0
1
ゼロサプレスルール
2種類のルールを
繰り返し適用して圧縮
e5
0
他は 0
...
2つの「等価な」ノードは
共有される
ei
...
1
1
...
...
...
...
1
ZDD
{ e5 } { e3 e5 }
0
0
1
1
1-枝が0-Terminalを指す
ノードは削除される
29
30
今日の内容
ZDDの演算
• ZDD を用いると、集合演算や、要素の検索等、様々な演算が
効率良く行える
• graphillion ライブラリでできること
• graphillion の内部データ構造
和集合を求める
(union)
∪
• graphillion ライブラリの紹介
• ZDD
• graphillion が使用しているアルゴリズム
• フロンティア法
{e1, e2, e5}, {e1, e4},
{e1, e2, e5},
{e1, e3, e4, e7} {e1, e3, e4, e7} {e1, e4}
{e1, e3, e4, e7}
• 適用事例紹介 (1), (2), (3)
s-t 経路を例に説明
要素の抽出
{e1, e2, e5},
{e1, e4}
{e1, e3, e4, e7}
{e1, e4}
{e1, e3, e4, e7}
e4 を含む
集合を取り出す
31
アルゴリズムは省略
32
s-t 経路は辺の集合で表現できる
s-t 経路は辺の集合で表現できる
s
e1
e4
e3
e2
s
e1
e4
e3
e2
s
t
e4
e1
s
e3
e2
e3
s
{e1, e3 ,e5}
e5
e4
{e1, e4}
t
e1
e4
s
t
e1
e3
{e2, e5}
e2
e5
e1
e4
e3
e2
e4
e2
t
s
e4
e3
e2
e5
辺集合の集合で表す
e5
e1
s
e3
s
t
{e1, e3 ,e5}
e5
e4
{e1, e4}
e5
e1
{e2, e3 ,e4}
t
全ての s-t 経路を列挙して、
t
e3
e2
e5
e5
e1
s
t
t
{e2, e5}
e2
e5
e1
e4
e3
e2
t
{e2, e3 ,e4}
e5
33
s-t 経路は辺の集合で表現できる
s
e1
e4
e2
s-t 経路は辺の集合で表現できる
全ての s-t 経路を列挙して、
t
e3
34
s
辺集合の集合で表す
e5
e1
e4
e3
e2
s
s
e4
e3
e5
e1
s
t
{e1, e3 ,e5}
e4
e3
{e1, e4}
e5
e1
e2
t
e5
e1
e4
e3
e2
e1
e4
e3
{e2, e5}
e2
e2
t
s
e4
e3
e2
35
辺集合の集合で表す
これをZDDで表現する
e5
t
s
e5
e1
s
t
{e1, e3 ,e5}
e4
e3
{e1, e4}
e5
e1
{e2, e3 ,e4}
e5
全ての s-t 経路を列挙して、
t
全 s-t 経路の集合 = {{e1, e4}, {e2, e5},{e1, e3 ,e5},{e2, e3 ,e4}}
s
t
e4
e3
e2
全 s-t 経路の集合 = {{e1, e4}, {e2, e5},{e1, e3 ,e5},{e2, e3 ,e4}}
s
e1
{e2, e5}
e2
e5
e1
e4
e3
e2
t
t
{e2, e3 ,e4}
e5
36
経路列挙（ZDD構築）アルゴリズム [Knuth 08]
経路列挙（ZDD構築）アルゴリズム [Knuth 08]
e1
s
e4
t
e3
e2
e5
1. 辺に順番を付ける
（例えば、s から幅優先）
e1 = 0 e1 e1 = 1
e2
e2
e2 = 1 e2 = 0
e2 = 1
e2 = 0
e3
e3
e3
e3
1
0
（もっと良い方法もあり）
2. ZDDを構築
s-t path
e
s 1
辺 e1, e2,… の順に処理
各辺変数 ei に対し、
ei = 0 or 1 を決めていく
e2
e1
s
t
e3
e2
e5
e4
1. 辺に順番を付ける
（例えば、s から幅優先）
e5
（もっと良い方法もあり）
2. ZDDを構築
1
e4
e3
辺 e1, e2,… の順に処理
t
各辺変数 ei に対し、
ei = 0 or 1 を決めていく
e5
ei = 1 である辺が s-t 経路になっているか？
e1 = 0 e1 e1 = 1
e2
e2
e2 = 1 e2 = 0
e2 = 1
e2 = 0
e3
e3
e3
e3
1
0
e5
s-t経路でない
s
e1
0
e4
e3
e2
s-t path +
余分な辺
s
t
経路列挙（ZDD構築）アルゴリズム [Knuth 08]
t
e3
e2
e5
1. 辺に順番を付ける
（例えば、s から幅優先）
e1 = 0 e1 e1 = 1
e2
e2
e2 = 1 e2 = 0
e2 = 1
e2 = 0
e3
e3
e3
e3
1
0
（もっと良い方法もあり）
2. ZDDを構築
e1
e4
e3
e2
e5
s
e4
0
e5
a
e1
e2
e5
t
e3
e6
b e
4
c
e4
e5
1
1
1 1 他は0
辺 e1, e2,… の順に処理
各辺変数 ei に対し、
ei = 0 or 1 を決めていく
…
39
t
38
経路列挙（ZDD構築）アルゴリズム [Knuth 08]
e1
e4
ei = 1 である辺が s-t 経路になっているか？
37
s
e4
40
経路列挙（ZDD構築）アルゴリズム [Knuth 08]
s
a
e1
経路列挙（ZDD構築）アルゴリズム [Knuth 08]
e5
t
e3
e2
処理済み辺
未処理辺
e6
b e
4
f
c
f
d
d
a
s
b
t
f
c
s
b
h
g
d
d
a
s
t
f
c
s
h
g
フロンティア
部分経路の反対側の端点を記憶しておき、
フロンティア上ですべて一致するなら、
2つは同じ状態とみなす。
…
41
42
6
6
e1
e3
s
e2 e e4 e e5
8
6
6
6
e7
2
4
3
3
2
4
3
3
4
3
3
経路の数え上げ
12
ZDDの形式で保存
• ZDDが構築できれば、経路の全列挙は簡単
• top から 1-終端までたどればよい
• 構築したZDDはコンパクトなので、そのまま保持可能
• ZDD演算を行うことで、経路の条件付き検索が可能
{e1, e2, e5},
{e1, e4}
{e1, e3, e4, e7}
{e1, e4}
{e1,e3, e4, e7}
e4 を通る
経路のみを
取り出す
2
1
1
2
1
1
2
1
1
1
1
1
1
2
1
1
1
1
43
2
1
2
1
1
1
1
1
1
e11
2 1
2
1
1
e9
e10
e12 t
1
1
重み付き和の最大値・最小値も
同様の方法で行える
44
一様ランダムサンプリング
確率
6
13
13
0 a 1
6
b
b
3
7
13
d
2
6
7
b
b
b
b
3
3
6
7
4
3
c
c
c
1
{d}, {c}, {c, d},
{b}, {b, d}, {b, c, d},
{a}, {a, d}, {a, c, d},
{a, b}, {a, b, c}, {a, b, d},
{a, b, c, d}
1
確率
0 a 1
c
d
0
確率
7
13
4
c
1
13
6
3
c
a
一様ランダムサンプリング
d
d
0
1
2
b
6
確率
3
6
3
3
c
{d}, {c}, {c, d},
{b}, {b, d}, {b, c, d},
{a}, {a, d}, {a, c, d},
{a, b}, {a, b, c}, {a, b, d},
{a, b, c, d}
45
一様ランダムサンプリング
graphillion で扱える部分グラフの種類
（再掲）
• s-t 経路
• ハミルトン経路（すべての頂点を通る）
• サイクル（1周して戻る）
13
0 a 1
6
b
b
7
c
c
c
d
d
0
•木
4
3
1
46
• 経路
{b, d}
3
c
1
2
• 森、全域森
• 木、全域木
• 連結成分
{d}, {c}, {c, d},
{b}, {b, d}, {b, c, d},
{a}, {a, d}, {a, c, d},
{a, b}, {a, b, c}, {a, b, d},
{a, b, c, d}
フロンティア法は、Knuth のアルゴリズム（s-t 経路）を、
様々な部分グラフに適用できるように拡張したもの
• マッチング
• クリーク（頂点同士がすべて結ばれている頂点集合）
• その他、様々な制約を課した部分グラフ
47
48
適用事例1: パズルソルバー
適用事例1-1: ナンバーリンクソルバー 1/4
• ナンバーリンク
• グラフの問題として定式化
s1-t1 経路
s2-t2 経路
...
sp-tp 経路
（複数終端対経路）
を同時に求める問題
同じ数字同士を、線を交差させずに結ぶ
R. Yoshinaka, T. Saitoh, J. Kawahara, K. Tsuruma, H. Iwashita, S. Minato.
Finding all solutions and instances of numberlink and slitherlink by ZDDs.
Algorithms, 5, 176–213, 2012.
49
50
ZDD書籍から引用
ZDD書籍から引用
適用事例1-1: ナンバーリンクソルバー 2/4
適用事例1-1: ナンバーリンクソルバー 3/4
• graphillion には、直接、複数終端対
経路を求めるメソッドはない
• 条件をつけた部分グラフを求める
メソッドを使う
• 次数の条件
• 終端（si, ti）の次数は1
• それ以外の次数は0 または 2
>>>
>>>
>>>
>>>
>>>
>>>
...
>>>
...
universe = [...]
GraphSet.set_universe(universe)
point_pairs = [[2, 6], [1, 11], [3, 22]]
points = sum(point_pairs, [])
[2, 6, 1, 11, 3, 22]
deg_cons = dict([(v, 1) for v in
set(range(1, 37)) if v in points])
deg_cons.update(dict([(v, (0, 2)) for v in
set(range(1, 37)) if v not in points]))
{1: 1, 2: 1, 3: 1, 4: (0, 2), 5: (0, 2), 6: 1,...
51
ZDD書籍から引用
52
ZDD書籍から引用
適用事例1-1: ナンバーリンクソルバー 4/4
適用事例1-2: スリザーリンクソルバー 1/4
[[2, 6], [1, 11], [3, 22]]
s2
s1
s3
書かれている数字の
本数の辺を使う
• スリザーリンク
>>> solutions = GraphSet.graphs(
...
vertex_groups=point_pairs,
...
degree_constraints=deg_cons,
...
no_loop=True)
>>>
>>> print solutions.len()
1
t1
t2
サイクルを1個作る
t3
得られた解
{1: 1, 2: 1, 3: 1, 4: (0, 2), 5: (0, 2), 6: 1,...
53
54
ZDD書籍から引用
ZDD書籍から引用
適用事例1-2: スリザーリンクソルバー 2/4
適用事例1-2: スリザーリンクソルバー 3/4
• 初めに、マスの数字は無視して、サイクルをすべ
て求める
• 次に、ある1つのマスに着目
そのマスの制約を満たしている部分グラフのみを抽出
>>> universe = [...]
>>> GraphSet.set_universe(universe)
>>>
>>> cycles = GraphSet.cycles()
>>>
>>>
>>>
>>>
e1
e2
e3
e4
=
=
=
=
(15,
(15,
(16,
(23,
16)
23)
24)
24)
15 e1 16
e2 e3
23
24
e4
>>> from itertools import
combinations
>>> g_set = list(combinations([e1,
e2, e3, e4], 2))
>>> in_gs = GraphSet(g_set)
>>> cycles = cycles.including(in_gs)
55
56
ZDD書籍から引用
適用事例2: 配電網のスイッチ構成 1/10
適用事例1-2: スリザーリンクソルバー 4/4
• 次に、ある1つのマスに着目
そのマスの制約を満たしている部分グラフのみを抽出
>>>
e2,
>>>
>>>
g_set2 = list(combinations([e1,
e3, e4], 3))
ex_gs = GraphSet(g_set2)
cycles = cycles.excluding(ex_gs)
配電網
すべての家は
ちょうど1つの変電所に
つながっている必要がある
15 e1 16
e2 e3
23
24
e4
サイクルが生じてはいけない
変電所を根とする根付き全域森
これをすべてのマスについて行う。
得られた部分グラフが解
2
0
引用： http://www.jst.go.jp/pr/announce/20120223/index.html
2
0
0
2
得られた解
0
2
57
ZDD書籍から引用
T. Inoue et al., “Distribution Loss Minimization with Guaranteed Error Bound,”
IEEE Transactions on Smart Grid, Vol. 5, Issue 1, 2014, pp. 102-111.
適用事例2: 配電網のスイッチ構成 2/10
適用事例2: 配電網のスイッチ構成 3/10
• 根付き全域森を列挙する
• 電気制約
58
• 1つの変電所が給電可能な最大家庭数に制限がある
>>> universe = [...]
>>> GraphSet.set_universe(universe)
>>> forests = GraphSet.forests(roots=[1, 9, 73, 81],
is_spanning=True)
>>> print forests.len()
54060425088
制限数 5
...
59
制限数オーバー
60
適用事例2: 配電網のスイッチ構成 5/10
適用事例2: 配電網のスイッチ構成 4/10
• 電気制約を満たす根付き全域森を求める
• 電気制約を満たす根付き全域森を求める
制限数 6
制限数 6
...
...
まずは、電気制約を満たさない大きな木を求める
根付き全域森の集合から、電気制約に違反する
木を含む根付き全域森を削除
>>> safe_forests = forests.excluding(too_large_trees)
>>> all_trees = GraphSet.trees()
>>> too_large_trees = all_trees.larger(6)
...
...
61
62
適用事例2: 配電網のスイッチ構成 6/10
適用事例2: 配電網のスイッチ構成 7/10
• 与えられた構成（根付き全域森）が、制約を満たす
かどうか調べる
• 与えられた構成から、スイッチON/OFFをいくつか
変化させて、制約を満たす構成に変化させる
>>> unsafe_forest = [...]
>>> unsafe_forest in safe_forests
False
2回
5回
...
4回
与えられた構成
変化数最小の構成を求めるには？
63
safe_forests （制約を満たす）
64
適用事例2: 配電網のスイッチ構成 8/10
適用事例2: 配電網のスイッチ構成 9/10
• 最適化問題として定式化
• 与えられた構成（根付き全域森）が、制約を満たす
かどうか調べる
スイッチを変化させるごとにペナルティーが発生
ペナルティーを最小化する構成を求める
graphillion では、採用した辺にしか重みをつけることはできない
-1
+1 -1
+1 -1 +1 -1
+1
+1
+1 +1
-1
+1 +1
-1
-1
-1
-1
与えられた構成
（元グラフ）
元グラフにない辺を採用すると
ペナルティー +1 点（採用しないと 0点）
元グラフにある辺を採用すると
65 0点）
ペナルティー -1 点（採用しないと
>>>
>>>
>>>
>>>
...
...
>>>
...
...
...
unsafe_forest = [...]
weights = {}
for switch in universe:
weights[switch] = 1 if switch in unsafe_forest else -1
for f in safe_forests.min_iter(weights):
print f
on_switches = [e for e in f if e not in unsafe_forest]
off_switches = [e for e in unsafe_forest if e not in f]
66
適用事例2: 配電網のスイッチ構成 10/10
事例3: 避難所割り当て 1/2
• blocking set (hitting set)
• グラフと避難所が与えられたとき、避難所ごとにグ
ラフを分割
切断によって、構成（根付き全域森）が
なくなるような辺の集合
>>> failures = safe_forests.blocking()
>>> minimal_failures = failures.minimal()
極小のものだけを求めることができる
67
68
事例3: 避難所割り当て 2/2
その他の適用事例
• 割当をすべて列挙する
• 選挙区割りの列挙
• 多面体の展開図の列挙
• 住宅フロアプランの列挙
• ...
6
1, 6, 10 は同じ連結成分に
含まれてはいけない
1
10
>>>
>>>
>>>
>>>
>>>
universe = [...]
GraphSet.set_universe(universe)
assignments = GraphSet.graphs([[1], [6], [10]])
maximal_assignments = assignments.maximal()
同じ連結成分内で辺が張れる場合は
必ず張る
69
まとめ
• graphillion の紹介
• 内部データ構造とアルゴリズム
• ZDD
• フロンティア法
• 適用事例の紹介
• パズルソルバー（ナンバーリンク、スリザーリンク）
• 配電網のスイッチ構成
• 避難所割り当て
71
70

Download Report