Algorithms

library(zddr)

Terminal cases

The first insight into the underlying algorithms is an examination of how each function handles the terminal cases. The terminal cases are:

• Operation of a ZDD to itself
• Operation of a ZDD to the zero-node (and vice-versa)
• Operation of a ZDD to the one-node (and vice-versa)

Union

zdd(4) | zdd(4)
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.001 MB, item count: 2 ( 0.5 KB/item)
#> 2863f659b84a60a3b2077896d5960955 : 1 cutsets, min order: 1 max order: 1 
#> 1-order 
#>       1 
#> {4}
zdd(4) | F
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.001 MB, item count: 3 ( 0.33 KB/item)
#> 2863f659b84a60a3b2077896d5960955 : 1 cutsets, min order: 1 max order: 1 
#> 1-order 
#>       1 
#> {4}
zdd(4) | T
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.001 MB, item count: 4 ( 0.25 KB/item)
#> ffffffffffffffffffffffffffffffff : 1 cutsets, min order: 0 max order: 0 
#> ONE
as_zdd(F) | zdd(4)
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.001 MB, item count: 5 ( 0.2 KB/item)
#> 2863f659b84a60a3b2077896d5960955 : 1 cutsets, min order: 1 max order: 1 
#> 1-order 
#>       1 
#> {4}
as_zdd(T) | zdd(4)
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.002 MB, item count: 6 ( 0.33 KB/item)
#> ffffffffffffffffffffffffffffffff : 1 cutsets, min order: 0 max order: 0 
#> ONE

Difference

zdd(4) - zdd(4)
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.002 MB, item count: 7 ( 0.29 KB/item)
#> 00000000000000000000000000000000 : 0 cutsets, min order: max order: 
#> ZERO
zdd(4) - F
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.002 MB, item count: 8 ( 0.25 KB/item)
#> 2863f659b84a60a3b2077896d5960955 : 1 cutsets, min order: 1 max order: 1 
#> 1-order 
#>       1 
#> {4}
zdd(4) - T
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.002 MB, item count: 9 ( 0.22 KB/item)
#> 00000000000000000000000000000000 : 0 cutsets, min order: max order: 
#> ZERO
as_zdd(F) - zdd(4)
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.002 MB, item count: 10 ( 0.2 KB/item)
#> 00000000000000000000000000000000 : 0 cutsets, min order: max order: 
#> ZERO
as_zdd(T) - zdd(4)
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.002 MB, item count: 11 ( 0.18 KB/item)
#> ffffffffffffffffffffffffffffffff : 1 cutsets, min order: 0 max order: 0 
#> ONE

Intersection

zdd(4) & zdd(4)
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.003 MB, item count: 12 ( 0.25 KB/item)
#> 2863f659b84a60a3b2077896d5960955 : 1 cutsets, min order: 1 max order: 1 
#> 1-order 
#>       1 
#> {4}
zdd(4) & F
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.003 MB, item count: 13 ( 0.23 KB/item)
#> 00000000000000000000000000000000 : 0 cutsets, min order: max order: 
#> ZERO
zdd(4) & T
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.003 MB, item count: 14 ( 0.21 KB/item)
#> 00000000000000000000000000000000 : 0 cutsets, min order: max order: 
#> ZERO
as_zdd(F) & zdd(4)
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.003 MB, item count: 15 ( 0.2 KB/item)
#> 00000000000000000000000000000000 : 0 cutsets, min order: max order: 
#> ZERO
as_zdd(T) & zdd(4)
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.003 MB, item count: 16 ( 0.19 KB/item)
#> 00000000000000000000000000000000 : 0 cutsets, min order: max order: 
#> ZERO

Crossproduct

zdd(4) * zdd(4)
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.003 MB, item count: 17 ( 0.18 KB/item)
#> 2863f659b84a60a3b2077896d5960955 : 1 cutsets, min order: 1 max order: 1 
#> 1-order 
#>       1 
#> {4}
zdd(4) * F
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.004 MB, item count: 18 ( 0.22 KB/item)
#> 00000000000000000000000000000000 : 0 cutsets, min order: max order: 
#> ZERO
zdd(4) * T
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.004 MB, item count: 19 ( 0.21 KB/item)
#> 2863f659b84a60a3b2077896d5960955 : 1 cutsets, min order: 1 max order: 1 
#> 1-order 
#>       1 
#> {4}
as_zdd(F) * zdd(4)
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.004 MB, item count: 20 ( 0.2 KB/item)
#> 00000000000000000000000000000000 : 0 cutsets, min order: max order: 
#> ZERO
as_zdd(T) * zdd(4)
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.004 MB, item count: 21 ( 0.19 KB/item)
#> 2863f659b84a60a3b2077896d5960955 : 1 cutsets, min order: 1 max order: 1 
#> 1-order 
#>       1 
#> {4}

AND-NOT

zdd(4) %% zdd(4)
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.005 MB, item count: 24 ( 0.21 KB/item)
#> 00000000000000000000000000000000 : 0 cutsets, min order: max order: 
#> ZERO
zdd(4) %% F
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.005 MB, item count: 25 ( 0.2 KB/item)
#> 2863f659b84a60a3b2077896d5960955 : 1 cutsets, min order: 1 max order: 1 
#> 1-order 
#>       1 
#> {4}
zdd(4) %% T
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.005 MB, item count: 26 ( 0.19 KB/item)
#> 00000000000000000000000000000000 : 0 cutsets, min order: max order: 
#> ZERO
as_zdd(F) %% zdd(4)
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.005 MB, item count: 27 ( 0.19 KB/item)
#> 00000000000000000000000000000000 : 0 cutsets, min order: max order: 
#> ZERO
as_zdd(T) %% zdd(4)
#> Memory of ZDD Store:     0.003 MB, item count: 3 ( 1 KB/item)
#> Memory of ZDD Functions: 0.005 MB, item count: 28 ( 0.18 KB/item)
#> ffffffffffffffffffffffffffffffff : 1 cutsets, min order: 0 max order: 0 
#> ONE