数理解析研究所講究録
第 1744 巻 2011 年 35-41

35

ZDD によるパスの列挙
川原 純 \dag er ,\d ag er\dag er

斎藤 寿樹 \dag er ,\d ag er

鈴木 拡 \d ag er

湊 真一 \d ag er ,\dag er

吉仲 亮 \dag er ,\d ag er

科学技術振興機構 ERATO 湊離散構造処理系プロジェクト\d ag er
北海道大学大学院情報科学研究科
多く，多くの経路問題で解の数を求める問題は #P-

概要

完全であり，あるいは，解の存在問題は NP 完全で与えられたグラフ中のパスを列挙する問題は古典あって，満足のいく高速な列挙アルゴリズムの実現的な問題である．これまで，解を列挙するアルゴリは難しい．
ズムや解の数を数えるアルゴリズムがいくつか提案

グラフ中の経路を辺の集合と同一視することで，経されているが，一般に解の数は極めて多く，解の数路の集合を辺の集合族とみなせる．集合族を圧縮してを求める問題は#P-完全であるため，満足のいく高 表現するデータ構造として，ZDD (Zero-suppressed

速な列挙アルゴリズムの実現は難しい．
近年 Knuth は，ZDD (Zero-suppressed BinaryDecision Diagram) を用いた任意のグラフのある 2

Binary Decision Diagram) が提案されている [4].
ZDD は膨大な集合族を効率よく圧縮できるのみならず，集合データに対する多様な演算もまた効率よ

点間を端点とするパスを列挙するアルゴリズムを提く実行可能であるという特長があり，VLSI 設計や案した．ZDD とは集合族を圧縮して表現できるデー

データマイニングニューラルネットワーク上の計タ構造である．グラフの経路を辺の集合と同一視す算等々に，幅広く応用されている．

ることによって，経路の集合は ZDD で表現すること

最近 Knuth[3] は，ZDD 構造を用いて任意のグラができる．提案されたアルゴリズムは，出力結果がフの任意の 2 点間を端点とするパスを列挙する高速パス集合の ZDD による圧縮表現であり，従来手法アルゴリズムを提案した．本発表では，まず Knuthに比べ高速に動作する．本発表では，まず Knuth ののアルゴリズムを紹介し，次にKnuth のアルゴリズアルゴリズムを紹介し，次に Knuth のアルゴリズム ムを基にしたアルゴリズムを提案する．このアルゴを基にした筆者らによる多項式回の ZDD の基本演リズムは多項式回のZDD の基本演算でパスの列挙算でパスの列挙を行うアルゴリズムを提案する．こを行う．これらの手法と既存手法との比較実験を行
れらの手法と既存手法との比較実験を行い，ZDD にい，ZDD によるパスの列挙手法の利を論ずる．
よるパスの列挙手法の利を論ずる．

12

序

与えられたグラフ中の特定 2 頂点間のパスやハミルトン閉路など，特定の性質を満たす経路の列挙問
題は古典的な問題である．これまで，解の数を数える
アルゴリズム [1,7] や解を列挙するアルゴリズム [6]がいくつか提案されている力 一般に解の数は極めて$\nwarrow$

Zero-SuppressedDecision Diagram

BinaryZDD[4] は，有限集合の部分集合の集合を，出次数が 2 である非循環有向グラフによって表現する．語の混乱を避けるため，以降，全体集合の要素をアイテムと呼び，全体集合の部分集合を (アイテムの) 組

36合せと呼ぶ．ある ZDD の表現する組合せ集合をデータと呼ぶ．ZDD ではアイテム間に全順序を仮定し，それぞれの組合せは順序に従ってリストとして表現される．ZDD には根と呼ばれる特殊ノードが 1 つあり，ある組合せがデータに含まれるか否かは，根.

からノードを順に辿ることで決定する．各ノードは実線は HI 枝を，点線は LO 枝を表すアイテムでラベルづけされており，そのアイテムが当該組合せに含まれるか否かに応じて，ノードから集合 {a, b, c, ac, bc} を表す ZDD
図 1:の二本の出力枝の一方を決定的に選択する．アイテ
ムが含まれることを意味する出力枝を HI 枝と呼び，他方を LO 枝と呼ぶことにする．アイテム間の全順 味する．換言すれば，データに含まれる組合せの全序に従って，上流ノードのアイテムラベルは常に下 てのアイテムは，ひとつずつ順番に ZDD のノード$|$

流ノードのアイテムラベルよりも真に小さい．ZDDとは出力枝を持たないただ 2 っの底ノードをによって「確認」されなければならない．

持ち，T に到達することは当該組合せがデータに含もしくはそれ以上に重要な ZDD の特長に，．演算処$T$データを大幅に圧縮表現するという特長に加え，$\perp$まれることを意味し， ，悗療 達は含まれないこと の容易性効率性がある [5]. 集合に新しい組み合を意味する．データの圧縮表現である ZDD は，次 わせを加える，組合せのうち特定のアイテムを含む/含まないもののみを抜き出す，各アイテムに重みなる 2 つの簡約化規則を持つ:を仮定して最大重みを与える組合せを求めること，ラベル，HI 枝，LO 枝の全てが同じであるよう 等々が容易に可能である．ここで，ZDD の表す集な異なるニノードは存在しないものとする (ノー 合 $F$ を多項式で表すと便宜だろう．例えば図 1 ではドの一意性),$F=a+$ ac $+b+$ bc $+c$ となる．この例を用いて，$\Phi$$\bullet$$\bullet$

HI 枝が ，鮖悗好痢璽匹詫曚防集修靴覆 (Zerosuppress 規則).

$|\ovalbox{\tt\smallREJECT}$$1$

ノードの一意性，Zero-suppress 規則を満たさない
データ構造にあっても，組合せがデータに入っているかどうかは上述のノード間の遷移規則によって決定できる．このようなものを非既約な ZDD と呼ぶ．
単に ZDD と言えば上記簡約化規則を満たす既約なものを意味する．Zero-suppress 規則によって陽に表に，和，積，商，剰余をとる演算を紹介する．
$\bullet$

足算$+$: 集合$F$に組合せ abc を追加すると

きは $Farrow F+$ abc と命令する．結果は $F=$$a+$ abc $+$$\bullet$

ac $+b+$ bc $+c$ となる

掛算 : 集合 $F$ 中の全ての組合せにアイテムを追加するときは $Farrow F\cross d$ と命令する．結$d$$\cross$

果は $F=$ ad $+$ abcd $+$ acd $+$ bcd $+$ bd $+$ cd となる．

現されなくなったノードの扱いについては注意が必要である．たとえば図 1 の ZDD に表現されるデータには，組合せ abc は含まれない．なぜなら，a でラベルづけされた根ノードから HI 枝に辿ったあとのノードのラベルは$b$$b$

ではなく$c$であり，ここにはでラベルづけされたノードが Zero-suppress 規則を適用されたと見ることができる．これは，組合せにが含まれるならば ．痢璽匹謀 達すべきこと，$b$

そのような組合せはデータ中に存在しないことを意$\bullet$

割算 /:$F$の全ての組合せのうち，特定のアイテム (の組合せ) を含むものについて，それを$Farrow F/a$ の結果は取り除いた結果を与える．

.

$F=$ bcd $+$ cd $+d$ である．

剰余算 %:$F$の全ての組合せのうち特定のアイテム (の組合せ) を含まないもののみを与え$Farrow F$ %る．

$c$の結果は $F=d$ となる．

37
これらの演算は 2 つの異なる集合 $F,$ を表す ZDD間でも同様に実行可能である．ZDD ではこれらの演算をある種の因数分解と対応したままで実行するため，式を展開して行うよりも高速に演算できる．上記の基本演算以外にもさらに多様な演算が実装・提$G$供されている．

1 つからなる集合とする．また，辺に順序が与えられており，各辺で次の操作が行われる． の各パス
$P$ に辺マッチング $P$ について，を追加したパス$\mathcal{P}$$e$

マッチング $P’$ およびグを$e$に格納する． の全要素の処理の終了後，の全要素を に移動させる．すべての辺への$\mathcal{P}_{new}$$\mathcal{P}new$を追加しないパスマッチン$\mathcal{P}$$\mathcal{P}$

処理が終了したとき， から へのパスのみで構成さ
$t$

$s$

3

ZDD によるパスの列挙アルゴ
リズムれるパスマッチングが出力対象である．しかし，単純にこれを実行すると，パスマッチングの数は非常に多いため，膨大な計算時間および領域が必要となる．

SIMPATH では，すべてのパスマッチングを管理せ
グラフ $G=(V, E)$ において，$i\in\{1,2,$に対し $\{v_{i}, v_{i+1}\}$$1\}$$(v_{1}, v_{2}, \ldots, v\iota)$

ら,$\in E$$\ldots,$$l-$

ず，今後行う操作が同じであるパスマッチングを同であるとき，頂点の列 一視し，管理すべきパスマッチングの数を減らして

ただし $i\neq i$ で $v_{i}\neq v_{j}$ , を$v_{1}$

か$E’\subset E$ を現在までに操作した辺の集いる．ここで，へのパスという．また，パス合とし，$\{\{v_{i},v_{i+1}\}|i\in\{1,\ldots,l-1\}\}$
をパ対し，辺の集合とき，任意の$(v_{1}, v_{2}, \ldots, v_{l})$$v_{l}$に$P,$ $P’\subset E’$をパスマッチングとする．この$P”\subset E\backslash E’$$P\cup P’’$ がに対し，$s$から$t$スと同一視する．互いに素なパスの集合をパスマッ へのパスであるとき，またそのときに限り，$P’\cup P’’$チングという．
$P$ と $P’$ を同値なが から へのパスであるならば，本論文では，以下の問題を考える．
パスマッチングという．SIMPATH では，mate と呼入力 : グラフ $G=(V, E)$ , 2 頂点 とばれる配列を用いて，同値であることが明らかなパ
出力 : から へのすべてのパスを格納した ZDD.
スマッチングを 1 つにまとめて取り扱う．配列 mate
本論文では次のような ZDD でグラフ上のパスを は要素数 $|V|$で配列の添字は頂点に対応する．mate格納する．グラフ の各辺 $e\in E$ は ZDD における の各要素の値はパスマッチング $P$ の状態によって，アイテムであり，各 から へのパス $P$ は ZDD 上の 以下のような値を取る．
$P$ に含まれる辺根からまでのあるパスに対応し，$P$ に$P$ に含まれない辺はは HI 枝を通り，を端点とするパスが存在LO 枝を通る．
本節では，この ZDD を構築する 2 つのアルゴリ matep $[i]=$頂点 の接続辺が使われていない
ズムについて述べる．1 つ目は近年，Knuth により
頂点 は $P$ のあるパスの中点提案されたアルゴリズムで [3], このアルゴリズムを実装した SIMPATH と呼ばれるプログラムが公開さ mate が同一なら，2 つのパスマッチングは同値で$s$

$s$

$s$

$t$

$t$

$t$

$G$

$G$

$s$

$t$

$T$

$\{$

れている．2 つ目は本論文で提案するアルゴリズム

$i$

$i,$

$i$

$i$

$0$

$i$

$j$ある．

で，SIMPATH のアルゴリズムを元にした，ZDD でSIMPATH のアルゴリズムは非既約な ZDD を先に行える多項式回の基本演算のみを用いたアルゴリズ構築し，後から非既約な ZDD の簡約化を行い，解とムである．

なる ZDD を出力する (非既約な ZDD の簡約化につ

3.1

Simpath のアルゴリズム

SIMPATH のアルゴリズムの主なアイディアはパスマッチングの集合$\mathcal{P}$を管理することである．具体的には，まず，初期化として$\mathcal{P}$を空のパスマッチング

いては文献 [3] を参照). SIMPATH の作成する ZDDのノードは，mate, LO 枝，HI 枝をもつ．ノード $N$の LO 枝(HI 枝) が指すノードを $LO(N)(HI(N))$と表記する．SIMPATH の非既約な ZDD 構築部分のアウトラインは以下の通りである．

38
1.

$\mathcal{P};=\{N_{0}\},$$/*N_{0}$$\mathcal{P}_{new}:=\emptyset$

は初期ノード (空のパスマッチング)$*/$

2. For each 辺 $e\in E$ do
For each ノード
3.
do$N$ にとする．
を加えたノードを4.
$N$ にとする．
を加えないノードを
5.
For $X=HI,$ $LO$ do
6.
$s-b,$ $c-d$ がパスをなす 2 つが孤立し，がのいずれかの要素 $N’$ と 図 2: 頂点
7.
If$P’$との同値なパスマッチング「同値」 then $Nx:=N’$に加える．
8.
else $Nx$ をの処理が終ったとき， の次数が 1 である．(i) は，の mate が 1 つの s-t パスを表す
If
9.
mate $[u]=v$ (mate $[v]=u$ ), または mate $[u]=0$ ,then $X(N);=T$または mate $[v]=0$ のとき mate は無効であると判の mate が無効
10.
else if
定する．(ii) は，mate $[v]=v$ または mate $[v]=0$ とthen $X(N):=\perp$$N\in \mathcal{P}$$N_{HI}$$e$$N_{LO}$$e$$N_{X}$$a$$\mathcal{P}_{new}$

.

$e$

$P$

$\mathcal{P}new$$v$$N_{X}$$N_{X}$

11.
12.

なっていない場合，mate は無効であると判定する．

else $X(N)$ $:=N_{X}$ .
End ForEnd For

13.
14.
15. End For$\mathcal{P}$$:=\mathcal{P}new,$$\mathcal{P}new$

7. ではノードの同値性判定を行う．多くの同値なパスマッチングを同一視するために，フロンティアだけ mate を抜き出し，同値判定に用いる．フロンを空にする．

ティアとは少なくとも 1 つの処理済の辺 $(\in E’)$ およの両方とび少なくとも 1 っの未処理の辺$(\in E\backslash E’)$接続している頂点の集合である (図 2). 例えば，図 2追加して新しいパスマッチングを生成する．実際には， の 2 つのパスマッチングは mate 全体の値は異なる

4. では $N$ の表すパスマッチングに辺 $e=\{u, v\}$ をはパスマッチングそのものではなく，mate を保持していることに注意せよ．具体的には辺 を追加した$N$$e$

とき，mate を次のように更新する．mate $[u]=w$ か
つ mate $[v]=x$ のとき，mate $[x]=w$ , mate $[w]=x$とする．このとき，$v\neq x$ ならば mate $[v]=0,$ $u\neq w$
ならば mate $[u]=0$ とする．

が，フロンティア上の mate の値が同一であるので，同値である．このように，処理済のどの辺をどのように使っているかは関係なく，フロンティア上の頂点の mate の値が等しい 2 つのパスマッチングは同値であるため，フロンティア上の頂点の mate のみを管理すればよい．これにより，非既約な ZDD のノード数を削減し，計算時間および領域を大幅に短

9. では mate が 1 つの s-t パスを表すかどうか判定する．具体的には mate $[s]=t$ かつ mate $[t]=s$ か 縮することができる．
つ，それ以外の mate が mate $[i]=0$ or であるな
$[i]$

$i$

らば，mate が表すパスマッチングは 1 つの s-t パス
3.2 Bottom-up Mate-ZDD 法である．このとき，HI 枝の指す先を T に設定する．
本節では，Bottom-up MATE-ZDD 法 (もしくは，9. 10. 11. の $X(N):=N’$ は $N$ の HI 枝 (LO 枝)

MATE-ZDD 法) というアルゴリズムを提案する．こ10. では，mate が「無効」 であるか判定を行う． のアルゴリズムのベースとなるアイディアは SIMmate が無効であるとは，以下の (i), (ii) のいずれか PATH のアルゴリズムと同様である．決定的な違いが成り立つことと定義する．(i) 頂点の次数が 3 以上 は，SIMPATH l は mate を管理し (非既約な)ZDD をになる等，mate がパスマッチングになっていない． 構築するが，MATE-ZDD 法は ZDD で行える基本演の指すノードを $N’$ に設定するという意味である．

(ii) 頂点 $v(v\neq s$ かつ $v\neq t)$ に接続するすべての辺算 (足算，掛算，割算，剰余算) のみを用いて，ZDD39を更新していくアルゴリズムである．

MATE-ZDD 法は，パスマッチングを保持する
ZDD $F$ と，さらにフロンティア上の mate 配列の代わりとなる補助変数を管理する．具体的には， 表 1: JapanMap $(JM)$ と JapanMap2 $(JM^{2})$ 上のパス
$mate[i]=j(i\neq 0)$ に対し，MATE-ZDD 法では補助変数$t_{i,j}$が対応し，変数$t_{i,j}$のノードの HI 枝はの列挙 (単位: 秒).

$i$と $i$ を両端点とするパスを持つパスマッチングに対応する．

4

実験結果

MATE-ZDD 法のアルゴリズムの流れは以下のとお
MATE-ZDD アルゴリズムの実装を行い，りである．まず，$F$ の初期値を $F=t_{1,1}\ldots t_{n,n}$ (頂点 Knuth [3] による SIMPATH プログラムと比較を 1, . . . , とする) とする．決められた順番に辺を処を行った．また，Read と Tarjan による Backtrack
理していき，mate とほぼ同様の更新を ZDD の演算を のアルゴリズム [6](宇野毅明氏による実装であ$n$用いて行う．アルゴリズムが処理済みの辺を $E’\subset E$とし，パスマッチング集合$\mathcal{P}$を $\mathcal{P}:=\{P|P\subset E’\}$$V’$ をフロンティアとする．アルゴリズムのとする．

途中で $F$ は以下の形となる．
$F= \sum_{P\in’P}F_{P}$

動可能な) 場合に頂点間に辺を張ることによって生成したグラフである．沖縄は除くので頂点数は 46である．JapanMap2 は JapanMap の頂点と辺をそ,れぞれ二重化したグラフである．これらのグラフに

ただし，対し，各プログラムを用いて，始点を北海道，終点を鹿児島としたパスの列挙を行ったのが表 1 である．表中の Simp. は SIMPATH による計算時間を，.
$F_{P}= \prod_{mato_{P}[i]=j}t_{i,j}\prod_{\{i,j\in V’,i\leq jk,\ell\}\in P}e_{k,l}$

各$F_{P}$CYPATH [8] プログラム) とも比較を行った．
JapanMap は都道府県を頂点とし，都道府県が地図上で隣接している (歩行，車，鉄道のいずれかで移るは 1 つのパスマッチング $P$ に対応する．変$e$数の積で 1 つのパスマッチング $P$ を表現し，変数$t$の積でパスマッチング $P$ の mate を表現する．
辺 $\{u, v\}$ を追加するときの更新式は以下の通りである．各 $w,$ $x\in V’$ に対し，M.-ZDD は MATE-ZDD による計算時間を意味する．計算環境は CPU が AMD Quad-Core Opteron

8393 SE $(3.09GH_{Z})$ , メモリが $512GB$ である．
ZDD のノード数は，変数の順序に大きく依存する．今回の$MATE-ZDD$ プログラムが出力する実験のための実装では，ノード数が小さくなるよ$F=F+(F/t_{u,w}/t_{v,x})\cross e_{u,v}\cross t_{x,w}$とする．また，頂点$v$がフロンティアから抜けるとうにヒューリスティックに変数順序を決定している．表 1 の「ノード数」の項目は，この変数順序の元で $MATE-ZDD$ プログラムが出力した (既$v\neq s,$ならば の次数は 1 であってはならな
き，い．そのため，フロンティアの各頂点 $w\neq v$ に対し， 約な) ZDD のノード数を意味する．JapanMap2
上のパス列挙において，生成された ZDD のノー$F=F$ %
$t$

$v$

$t_{v,w}$を行う．また，頂点ド数は 17,036,796 個であり，一方，パスの数は$v$が孤立しているかどうかに関心はないので$F=F/t_{v,v}+F$ %552,990, 153,767,713,569,683,921,601,890,579,271,385,088個である．ZDD によって膨大な数のパス集合をコ$t_{v,v}$ンパクトに表現できていることが分かる．

ランダムグラフについても，各プログラムを用いとする．そして，最終的に構築した ZDDF に対し， てパスの列挙を行った (表 2). 頂点数 を指定し，を含んだ項 $F=F/t_{s,t}$ が求める ZDD である．
$n$$t_{s,t}$40

表 2: ランダムグラフ上のパスの列挙，辺の生成確率 05(単位: 秒)

表 4: 完全グラフ上のパスの列挙 (単位: 秒)した物によって管理されるため，探索において，その表 3: 格子グラフ上のパスの列挙 (単位: 秒)辺の生成確率を $p=0.5$ とし，グラフを 100 個生成して列挙時間の平均を求めた．
$n=15,16,17$ の場

合に，3 つのプログラムの計算時間の差が明確に表れた．

木の登り降り等，その更新に時間がかかること，などが考えられる．一方で，MATE-ZDD 法はアルゴリズムが単純で，メンテナンス性に優れる．例えば，2 つの離れた辺の間に共起性や排他性のような関係がある場合にこれを実現することが容易である．常に正しく ZDD を構築しているので，ある辺を追加するか否かを決めるときに，共起すべき辺が構築中のパスに含まれるかどうかに応じた挙動を取ることが容易に実装できる．これは SIMPATH にあっては頂mate の概念を拡張することなしには実現できず，条件が複雑化したときの実装が難しくなる可能性があ

点完全グラフについても，各プログラムを用いてパスの列挙を行った．結果を表 3,4 に示す．

る．もっとも，条件を無視して ZDD でパスを列挙$n\cross n$5の格子グラフ (グリッドグラフ) 及び$n$した上で，条件を満たすものを ZDD 演算で取り出すこともできるので，一概に計算速度について論じることは難しい．今後の研究課題としたい．

議論
本研究では Knuth の ZDD によるパス列挙プ

また，グラフにおける頂点の探索順序あるいは辺に対応する ZDD の変数順序が，計算時間や構築さログラム SIMPATH と，それを基に独自に提案したれる ZDD のサイズに影響することがわかっている．

Bottom-up MATE-ZDD 法を比較検討した．圧縮した表現でパスを列挙するため，両手法とも，既存の列挙手法 (CYPATH [8]) に比して著しく高速に動作する．さらに，これらのプログラムはわずかな変更

現在は開始地点から幅優先で決めているが，これが最適ではない例が存在することがわかっている．グ
ラフの特徴に応じたより良い頂点の探索順序の決定手法も今後の課題である．

で，ハミルトン閉路の列挙等への応用が可能である．
これら ZDD に基づくプログラムの比較においては

MATE-ZDD 法が SIMPATH に比して一桁遅いが，この理由として (1) SIMPATH は非既約な ZDD を構築し，最後にまとめて簡約化を行うのに対し，MATEZDD は計算途中の構築物が常に既約な ZDD であるように維持していること，(2) SIMPATH で 1 つのmate に相当するものが，複数の 変数を木状に配置
$t$

参考文献
[1] E. T. Bax. Algorithms to Count Paths and Cycles. information Processing Letters, 52, pp.
249-252, 1994.

[2] M. B. avanbarg, C. Scawthorn, J. iyono, andY. Ono. Minimal Path Sets Seismic Reliability
$J$

$K$

41
Evaluation of Lifeline Networks with Link andNode Failures. In Proc. Lifeline Earthquake Engineereng in a Multihazard Environment.
[3] D. Knuth. The Art of Computer Programming,Volume 4, Fascicle 1.

[4] S. Minato. Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems. In $DAC$,
pp. 272-277, 1993.
[5] S. Minato. Fast Factorization Method for Implicit Cube Set Representation. IEEE Trans.
on Computer-Aided Design of Integrated Circuits and Systems, VOL. 15, No. 4, pp. 377-384,
1996.
[6] R. C. Read and R. E. Tarjan. Bounds on Backtrack Algorithms for Listing Cycles, Paths, andSpanning Trees. Networks, 5, pp. 237-252, 1975.
[7] K. Sekine and H. Imai. Counting the Number ofPaths in a Graph via BDDs. IEICE TRANS.
FUNDAMENTALS, VOL. ESO-A(4), pp. 682688, 1997.
[8] T. Uno. CYPATH; $st$ path, cycle, chordless $st$ path, chordless cycle enumeration.
http: //research. nii. ac. $jp/\sim uno/code/cypath$ . html.