page_title: Zero-suppressed decision diagram
section_title: Features
hierarchical_section_title: Zero-suppressed decision diagram / Features
caption_attribution_description: English: Bit manipulation and basic operations. Suppression of irrelevant variables
context_page_description: A zero-suppressed decision diagram is a particular kind of binary decision diagram with fixed variable ordering. This data structure provides a canonically compact representation of sets, particularly suitable for certain combinatorial problems. Recall the OBDD reduction strategy i.e. a node is removed from the decision tree if both out-edges point to the same node. In contrast, a node in a ZDD is removed if its positive edge points to the terminal node 0. This provides an alternative strong normal form, with improved compression of sparse sets. It is based on a reduction rule devised by Shin-ichi Minato in 1993.
context_section_description: One feature of ZDDs is that the form does not depend on the number of input variables as long as the combination sets are the same. It is unnecessary to fix the number of input variables before generating graphs. ZDDs automatically suppress the variables for objects which never appear in combination, hence the efficiency for manipulating sparse combinations. 
  Another advantage of ZDDs is that the number of 1-paths in the graph is exactly equal to the number of elements in the combination set. In original BDDs, the node elimination breaks this property. Therefore, ZDDs are better than simple BDDs to represent combination sets. It is, however, better to use the original BDDs when representing ordinary Boolean functions, as shown in Figure 7.
caption: Figure 7: Bit manipulation and basic operations. Figure 8: Suppression of irrelevant variables
exif: {}