Large-Scale
Knowledge Processing # 13
Using Binary Decision Diagrams(Part 3)

Faculty of Information Scienceand Technology, Hokkaido Univ.
Takashi Horiyama
1

ZDD(Zero-suppressed BDD)◼

◼

ZDD : Variant of BDD
The frontier-based search(Top-down construction of BDD/ZDD)
2

Prev. class：◼
◼

Binary Decision Diagram (BDD)

Variable order : Variables appear according to a total orderTwo rules for reducing (i.e., simplifying) BDDs
◼ Reduction : Repeat until we have no redundant andequivalent nodes

Remove a redundant nodexff

Share equivalent nodes

xxx

f0

f1

f0

f1
3

[ Minato 1993 ]ZDD (Zero-Suppressed BDD)◼
◼

Variable order : Variables appear according to a total orderTwo rules for reducing (i.e., simplifying) ZDDs
◼ Reduction : Repeat until we have no redundant andequivalent nodes

Remove a redundant node

xf0f

Share equivalent nodes

xxxf0

f1

f0

f1
4

ZDD
Ex.)

{ { x 1, x2 }, { x 1, x3 }, { x2, x3 } }5Find the family of sets
represented by a ZDD (Method 1)
Ex.)◼

{ { x 1, x2 }, { x 1, x3 }, { x2, x3 } }Each 1-path corresponds to a set
6

Find the family of sets
represented by a ZDD (Method 1)
Ex.)◼

{ { x 1, x2 }, { x 1, x3 }, { x2, x3 } }Each 1-path corresponds to a set
7

Find the family of sets
represented by a ZDD (Method 1)
Ex.)◼

{ { x 1, x2 }, { x 1, x3 }, { x2, x3 } }Each 1-path corresponds to a set
8

Find the family of sets
represented by a ZDD (Method 2)Ex.){ { x 1, x2 }, { x 1, x3 }, { x2, x3 } }{ { x2, x3 } }= { { x2, x3 } } ∪ { S ∪ { x1 } | S ∊ { { x2 }, { x3 } } }{ { x2 }, { x3 } }= { { x 3 } } ∪ { S ∪ { x2 } | S ∊ { { } } }{ { x3 } } = { } ∪ { S ∪ { x3 } | S ∊ { { } } }
◼

{ }
◼

{{ }}

Each subgraph pointed by the 0-edge
and 1-edge is also a ZDD (In otherwords, each node represents a familyof sets)

F = F0 ∪ { S ∪ { xi } | S ∊ F1 }9Construct a ZDD from a family of setsEx.){ { x 1, x2 }, { x 1, x3 }, { x2, x3 } }{ { x2, x3 } }= { { x2, x3 } } ∪ { { x1, x2 }, { x1, x3 } } }{ { x2 }, { x3 } }{ { x3 } }
◼

{ }
◼

Divide the given family of sets into two- 0-edge : Sets that do not contain xi- 1 –edge : Sets that contain xi{{ }}F = F0 ∪ { S ∪ { xi } | S ∊ F1 }10

practice：ZDD

Find the family of sets represented by the ZDD below
Construct the ZDD representing the family of setsobtained in 1 with variable order e2, e 1, e3, e4, e5e1

1.
2.

e2e3e3e4e50111

practice：

ZDD (cont.){ e1 e3 e5 } { e 1 e 4 }{ e2 e3 e4 } { e2 e5 }

e1e2e3e3e4e50112

practice：

ZDD (cont.){ e1 e3 e5 } { e1 e4 }{ e2 e3 e4 } { e2 e5 }{ e1 e3 e5 }{ e1 e4 }

e1e2{ e3 e4 }{ e5 }

e1e2e3e3e4{ }{ e3 e5 }{ e4 }

e50113

practice：

ZDD (cont.){ e1 e3 e5 } { e1 e4 }{ e2 e3 e4 } { e2 e5 }{ e1 e3 e5 }{ e1 e4 }e1{ e3 e4 }e2{ e5 }

e1e2e30e3e3

e3e4e4e5e510114

Short break◼

Take a deep breath, and relax yourself

15

The frontier-based search(top-down construction of BDD/ZDD)

16

Top-down construction of BDD/ZDD◼

Simpath [ Knuth 2008 ]◼
◼

◼

Enumeration of s-t paths
Construct a ZDD in a top-down manner
like dynamic programming

Frontier-based search [ Kawahara et al. 2014, 2017 ]◼

◼

Generalization of Simpath
Enumeration of spanning trees, forests, cycles,
Hamiltonian cycles, Hamiltonian paths, etc.

※ Similar approaches were attempted to problems
in other fields◼
◼
◼

Jones polynomials (knot theory)
Spanning trees
Network reliability [ Hardy ][ Sekine, Imai 1995 ]17Enumeration of spanning trees◼
◼

Do not contain cycles
All vertices areconnected1e2 e3

1e23e343 e 453421123e5 4e44e23e32e5 4e22e4

Input : a graph3 e 45Output : spanning trees of a given graphe1e1e1121212e3e2e4 e2e43e1

1e1e323 e 451e12e4

3 e 45e418

Enumeration of spanning trees◼
◼

Do not contain cycles
All vertices areconnected

1e2 e34{ e1 e2 e4 }
1e23e32e4

4{ e2 e3 e4 }3 e 4
5{ e1 e2 e5 }
1e2e32e5 4{ e2 e3 e5 }334{ e1 e3 e4 }
1e22e4Input : a graph3 e 45Output : spanning trees of a given graphe1e1e1121212e3e2e4 e2e4
3e1

1e1e3

23 e 45{ e1 e3 e5 }

1e12e43 e 4
5{ e1 e4 e5 }

2e4e5 4{ e2 e4 e5 }3A spanning tree is represented as a set of its edges

19Enumeration of spanning trees :Construction of a ZDD◼
◼

Do not contain cycles
All vertices areconnected

1e1e2 e32e4Input : a graph3 e 45e1 the root node

20Enumeration of spanning trees :Construction of a ZDD◼
◼

Do not contain cycles
do notAll vertices areconnected take e11e2 e32e4

3 e 45e21e2e1e32e43 e 45e1
take e11e2e1e32e4

3 e 45e221

Enumeration of spanning trees :Construction of a ZDD◼
◼

Do not contain cycles
All vertices areconnected
1e2 e32e41e2e32e4

3 e 45e1e2

3 e 45e11e2e1e32e43 e 45e20Vertex 1 is isolated→ pruning (terminate by 0 )22Enumeration of spanning trees :Construction of a ZDD◼
◼

Do not contain cycles
All vertices areconnected
1e2 e32e4e23 e 4512e2 e3 0e411ee11e3e23 e 45e3e3e32e43 e 452e4e1e2

1e2e3e1e32e43 e 453 e 4523

Enumeration of spanning trees :Construction of a ZDD◼
◼

Do not contain cycles
All vertices areconnected

e212e2 e3 0e43 e 451ee11e32e43 e 45e3e3e21e2e1e32e43 e 45e30Contains a cycle→ pruning24Enumeration of spanning: ZDD
The three trees
nodes in theare essentially equivalent
Construction of a ZDD- Vertices 1, 2, and 3 are connected◼
◼

Do not contain cycles
All vertices areconnected- Remaining subproblems on e4, e5
are the same

※ For a large graph, the connectivityof the vertices is more complex
vertices 1, 3, 7 are connected
e1 (e.g.,and vertices 2, 5 are connected ...)

e2e2e30e3e3e4e4e41e2 e32e43 e 451e1e32e43 e 4501e2e12e43 e 4525

Enumeration of spanning: ZDD
The three trees
nodes in theare essentially equivalent
Construction of a ZDD- Vertices 1, 2, and 3 are connected◼
◼

Do not contain cycles
All vertices areconnected- Remaining subproblems on e4, e5
are the same

e1

e20

e2
e3

e3
e4

Equivalent nodes areshared in the ZDD→ high speed, less memory

e3026

Enumeration of spanning: ZDD
The three trees
nodes in theare essentially equivalent
Construction of a ZDD- Vertices 1, 2, and 3 are connected◼
◼

Do not contain cycles
All vertices areconnected

How to checkthese two properties ?
(It is inefficient to keep
a whole graph in each
ZDD node and to checkthe whole graph in each
ZDD node)- Remaining subproblems on e4, e5
are the samee1e2

Equivalent nodes areshared in the ZDD→ high speed, less memory

e2e3e3e4e4e3

e50127

Conditions for pruning(termination by 0 )◼
◼

Do not contain cycles
All vertices areconnected

Pruning if we take an edge whoseboth ends belong to the sameconnected component,

badokHow to checkthese two properties ?

connectedcomponent(It is inefficient to keep
a whole graph in each
ZDD node and to checkthe whole graph in each
ZDD node)

Pruning if it is confirmed thatthe number of connected component
is two or moreconnected
component

Idea：
・ Do not keep a whole graph, but keep
which vertex belongs to which connected component
・ In the initial graph, all vertices are isolated
・ If we take an edge, two connected components
are connected by the edge

28

Enumeration of spanning: ZDD
The three trees
nodes in theare essentially equivalent
Construction of a ZDD- Vertices 1, 2, and 3 are connected- Remaining subproblems on e4, e5
are the same

We can use the information
on which vertex belongs towhich connected component※ For a large graph, the connectivityof the vertices is more complex
vertices 1, 3, 7 are connected
e1 (e.g.,and vertices 2, 5 are connected ...)

e2e2e30e3e3e4e4e41e2 e32e43 e 451e1e32e43 e 4
501e2e12e43 e 4529

The frontier
We can use the information
on which vertex belongs towhich connected component
◼

graph

We’d like to reducethe information
we need to memorize

frontier(The frontier is uniquely
defined for each levelof the ZDD)

Vertices can be classified into three types◼ Vertex that is adjacent only to unexplored edges◼

◼

Vertex that is adjacent to both unexplored edges andexplored edges (We say that this vertex is in the frontier)◼

◼

Always isolated → there is no need to memorize the information(connected component) of this vertex

Memorize the information of this vertex

Vertex that is adjacent only to explored edges

to memorize

We have another vertex that belongs to the same connected component and is in the frontier (Otherwise, the search was already pruned
since the vertex and any vertices in the frontier belong to different
connected component and have no chance of being the same)◼ It’ is sufficient to check only the vertices in the frontier → no needto memorize
We can understand the details on the construction of a ZDD if we recheck the information◼

the slides on the construction with the knowledge of this page

Application of ZDDs：
Analysis of power grid design
Switching controlof power grid

- Example of standard
power distribution
network
468 switches
10 140 combinations
Graph theory constraint+Electrical constraints(e.g., voltage drop)

変電所

s1

OFF変電所

変電所

OFF

s2
s4

OFF

s3

s3

s2

ON

s1

ONONs
OFF 2 ON

s3

s3

s3s4

変電所

⚫ 配電網の各スイッチのＯＮ/OFFを、ＺＤＤの場合分けに対応づけ⚫ 制約を満たすかどうかを終端節点の記号に対応づけ

制約条件を OK満たす

制約条件を NG満たさない

ZDD技法で圧縮して超高速に処理

High-speed, large scale, andhigh reliable analysis methodon power grids, where its
importance increased after theGreat East Japan Earthquake

31Supplementary materials◼

◼
◼

◼

ERATO Minato discrete structure manipulation
system project, S. Minato (ed.), Ultra high-speed
graph enumeration algorithm, Morikita publishing,2015. (in Japanese)
R. E. Bryant, Graph-based algorithms for Boolean function
manipulation. IEEE Trans. Comput. C-35(8), pp. 677–691, 1986.
S. Minato, Zero-suppressed BDDs for set manipulation incombinatorial problems, In Proc. of the 30th International
Design Automation Conference, 1993, pp. 272–277.
J. Kawahara, T. Inoue, H. Iwashita, S. Minato, Frontier-BasedSearch for Enumerating All Constrained Subgraphs with
Compressed Representation, IEICE Transactions, 100-A(9), pp.
1773-1784, 2017.

32

33

34