2 HI LO ZDD 2 ZDD 2 HI LO 2 ( ) HI (Zero-suppress ) Zero-suppress ZDD ZDD Zero-suppress 1 ZDD abc a HI b c b Zero-suppress b ZDD ZDD 5) ZDD F 1 F = a

Transcription

1 ZDD 1, 2 1, 2 1, 2 2 2, 1 #P- Knuth ZDD (Zero-suppressed Binary Decision Diagram) 2 ZDD ZDD ZDD Knuth Knuth ZDD ZDD Path Enumeration Algorithms Using ZDD and Their Performance Evaluations Toshiki Saitoh, 1, 2 Jun Kawahara, 1, 2 Ryo Yoshinaka, 1, 2 Hiromu Suzuki 2 and Shin-ichi Minato 2, 1 The listing of all paths in a given graph is a classical problem. Although there are known algorithms for the problem, the number of the solutions tends to be huge and the counting problem is #P-hard. Recently, Knuth has proposed an algorithm for enumerating paths by using the ZDD (zero-suppressed binary decision diagram). The ZDD is a condensed representation of a family of sets. By identifying a path in a graph as a set of edges, the sets of paths can be represented by ZDD. His algorithm outputs a ZDD representing a set of paths. In this paper, we first introduce Knuth s 1. algorithm, and propose an algorithm where ZDD operations implemented polynomial many times by extending Knuth s algorithm. We experiment with these algorithms and a known enumeration algorithm, and discuss the advantage of the algorithms using ZDD from the experimental result. 2 1),7) 6) #P- NP ZDD (Zero-suppressed Binary Decision Diagram) 4) ZDD VLSI Knuth 3) ZDD 2 Knuth Knuth ZDD ZDD 2. Zero-Suppressed Binary Decision Diagram ZDD 4) 2 ZDD ZDD ZDD 1 1 ERATO 2 1 c 2011 Information Processing Society of Japan

2 2 HI LO ZDD 2 ZDD 2 HI LO 2 ( ) HI (Zero-suppress ) Zero-suppress ZDD ZDD Zero-suppress 1 ZDD abc a HI b c b Zero-suppress b ZDD ZDD 5) ZDD F 1 F = a + ac + b + bc + c + F abc F F + abc F = a + abc + ac + b + bc + c F d F F d c 1 b a c 実線は HI 枝を, 点線は LO 枝を表す {a, b, c, ac, bc} ZDD F = ad + abcd + acd + bcd + bd + cd / F F F/a F = d + bcd + cd % F F F % c F = d 2 F, G ZDD ZDD 3. ZDD G = (V, E) i {1, 2,..., l 1} {v i, v i+1 } E (v 1, v 2,..., v l ) i j v i v j v 1 v l (v 1, v 2,..., v l ) {{v i, v i+1 } i {1,..., l 1}} G = (V, E) 2 s t s t ZDD. ZDD G G e E ZDD s t P ZDD P HI P LO ZDD 1 Knuth 3) Simpath 2 c 2011 Information Processing Society of Japan

3 2 Simpath ZDD 3.1 Simpath Simpath P P 1 P P P e P e Pnew P Pnew P s t Simpath E E P, P E P E \E P P s t P P s t P P Simpath mate mate V mate P j P i j mate[i] = i i 0 i P mate Simpath ZDD ZDD ZDD ZDD ZDD 3) Simpath ZDD mate LO HI N LO HI LO(N) HI(N) Simpath ZDD (1) 1. P := {N 0}, Pnew := /* N 0 */ 2. For each e E do 3. For each N P do 4. N e N HI 5. N e N LO 6. For X = HI, LO do 7. If N X Pnew N then N X := N 8. Else N X Pnew 9. If N X mate 1 s-t then X(N) := 10. Else If N X mate then X(N) := 11. Else X(N) := N X 12. End For 13. End For 14. P := Pnew, Pnew 15. End For 4. N e = {u, v} N mate mate mate[u] = w mate[v] = x mate[x] = w mate[w] = x v x mate[v] = 0 u w mate[u] = 0 9. mate 1 s-t mate[s] = t mate[t] = s mate[i] mate[i] = 0 or i mate 1 s-t HI X(N) := N N HI LO N 10. mate mate (i), (ii) (i) mate (ii) v (v s v t) v 1 (i) mate[u] = v (mate[v] = u) mate[u] = 0 mate[v] = 0 mate (ii) mate[v] = v mate[v] = 0 mate 3 c 2011 Information Processing Society of Japan

4 s 処理済の辺 E a c b P P s e d 未処理の辺 処理済の辺 E a c b e d 未処理の辺 2 a e s b, c d 2 P P 7. mate ( E ) ( E \ E ) ( 2) 2 mate mate mate mate ZDD 3.2 Bottom-up Mate-ZDD Bottom-up Mate-ZDD Mate-ZDD Simpath Simpath mate ( )ZDD Mate-ZDD ZDD ZDD Mate-ZDD ZDD F mate mate[i] = j (j 0) Mate- ZDD t i,j t i,j HI i j Mate-ZDD F F = t 1,1... t n,n ( 1,..., n ) mate ZDD E E P P := {P P E } V F F = F P, P P F P = i,j V, mate[i]=j, i j t i,j e k,l P F P 1 P e 1 P t P mate e k,l. {u, v} w, x V F = F + (F/t u,w/t v,x) e u,v t x,w v v 1 w v F = F % t v,w v F = F/t v,v ZDD F t s,t F = F/t s,t ZDD 4. Mate-ZDD Knuth 3) Simpath Read Tarjan Backtrack 6) ( CyPath 8) ) JapanMap ( ) 46 JapanMap 2 JapanMap 1 CPU AMD Quad-Core Opteron 8393 SE 3.09GHz 512GB JapanMap 2 552,990,153,767,713,569,683,921,601,890,579,271,385,088 Simpath Mate-ZDD 17,036,796 ZDD 2 4 c 2011 Information Processing Society of Japan

5 CyPath Simpath Mate-ZDD ZDD JM > 1000 < 0.01 < JM 2 > JapanMap (JM) JapanMap 2 (JM 2 ) n CyPath Simpath Mate-ZDD ZDD n CyPath Simpath Mate-ZDD ZDD 8 > > > > > n CyPath Simpath Mate-ZDD ZDD n p = n = 15, 16, 17 3 n n n 3, 4 5. Knuth ZDD Simpath Bottom-up Mate-ZDD (CyPath 8) ) ZDD Mate-ZDD Simpath (1) Simpath ZDD Mate-ZDD ZDD (2) Simpath 1 mate t Mate-ZDD 2 ZDD Simpath mate ZDD ZDD ZDD ZDD 1) E.T.Bax. Algorithms to Count Paths and Cycles. Information Processing Letters, 52, pp , ) M.B.Javanbarg, C.Scawthorn, J.Kiyono, and Y.Ono. Minimal Path Sets Seismic Reliability Evaluation of Lifeline Networks with Link and Node Failures. In Proc. Lifeline Earthquake Engineering 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 , ) 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 , ) R.C.Read and R.E.Tarjan. Bounds on Backtrack Algorithms for Listing Cycles, 5 c 2011 Information Processing Society of Japan

6 Paths, and Spanning Trees. Networks, 5, pp , ) K.Sekine and H.Imai. Counting the Number of Paths in a Graph via BDDs. IEICE TRANS. FUNDAMENTALS, VOL. E80-A(4), pp , ) T.Uno. CyPath. 6 c 2011 Information Processing Society of Japan