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 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
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 9. 10. 11. 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
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
CyPath Simpath Mate-ZDD ZDD JM > 1000 < 0.01 < 0.01 850 5.1 10 10 JM 2 > 1000 24.01 248.62 1.7 10 7 5.5 10 43 1 JapanMap (JM) JapanMap 2 (JM 2 ) n CyPath Simpath Mate-ZDD ZDD 15 3.33 0.29 2.87 1.5 10 5 3.7 10 6 16 25.20 0.96 14.84 6.2 10 5 2.9 10 7 17 147.62 2.99 64.45 2.2 10 6 1.6 10 8 2 0.5 n CyPath Simpath Mate-ZDD ZDD 8 > 1000 0.03 0.44 31487 7.8 10 11 9 > 1000 0.15 1.92 110215 3.2 10 15 10 > 1000 0.63 6.00 377202 4.1 10 19 11 > 1000 1.88 23.75 1.2 10 6 1.5 10 24 12 > 1000 6.25 148.11 4.2 10 6 1.8 10 29 3 n CyPath Simpath Mate-ZDD ZDD 11 0.58 0.03 0.32 33830 9.9 10 5 12 5.79 0.07 1.34 121455 9.9 10 6 13 64.30 0.42 8.51 435810 1.1 10 8 14 770.09 0.92 25.40 1.6 10 6 1.3 10 9 15 10049.51 2.74 110.07 5.6 10 6 1.7 10 10 4 n p = 0.5 100 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. 249-252, 1994. 2) 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. 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, 5 c 2011 Information Processing Society of Japan
Paths, and Spanning Trees. Networks, 5, pp. 237-252, 1975. 7) K.Sekine and H.Imai. Counting the Number of Paths in a Graph via BDDs. IEICE TRANS. FUNDAMENTALS, VOL. E80-A(4), pp. 682-688, 1997. 8) T.Uno. CyPath. http://research.nii.ac.jp/uno/code/cypath.html. 6 c 2011 Information Processing Society of Japan