Zero-suppressed diagrams: share sparse dispatch set families

Last updated: 4 Oct 20269 min read

tutorial

A zero-suppressed decision diagram represents a family of subsets over a fixed ordered universe. At an item test, the low branch omits that item and the high branch includes it. Terminal zero represents no subsets; terminal one represents the family containing the empty subset. If the high branch is zero, the node is removed because no represented set contains that item. Nodes with the same item position and child pair are interned once, so repeated subfamilies share a node. This differs from a reduced ordered Boolean decision diagram: equal low and high branches are not removed by the zero-suppression rule. The teaching builder starts from explicit allowed sets, deduplicates them, and then constructs the graph; it does not generate a large implicit family symbolically.

Operational case

The allowed dispatch combinations are insured alone, cold with insured, fragile with insured, and cold plus fragile with insured. The diagram represents four sets with three internal nodes in the chosen item order. Cold with insured is accepted; cold alone is not. The item oversized never occurs, so its include branch is empty and its test disappears. A query containing an unknown item is rejected. Skipped levels mean those items are absent, not don't-care values. Changing item order can alter sharing and node count even when the represented family is identical.

Working Python program

class DispatchSetFamily:
    """Static zero-suppressed diagram for subsets of an ordered item universe."""

    def __init__(self, ordered_items, allowed_sets):
        self.items = tuple(ordered_items)
        if len(set(self.items)) != len(self.items):
            raise ValueError("duplicate universe item")
        universe = set(self.items)
        family = {frozenset(subset) for subset in allowed_sets}
        if any(not subset <= universe for subset in family):
            raise ValueError("set contains an unknown item")
        self.nodes = {0: None, 1: None}  # Empty family and family containing empty set.
        self.unique = {}

        def build(level, subsets):
            if not subsets:
                return 0
            if level == len(self.items):
                return 1
            item = self.items[level]
            low_sets = frozenset(subset for subset in subsets if item not in subset)
            high_sets = frozenset(subset - {item} for subset in subsets if item in subset)
            low = build(level + 1, low_sets)
            high = build(level + 1, high_sets)
            if high == 0:
                return low
            key = (level, low, high)
            if key not in self.unique:
                node_id = len(self.nodes)
                self.unique[key] = node_id
                self.nodes[node_id] = key
            return self.unique[key]

        self.root = build(0, frozenset(family))

    def contains(self, selected_items):
        selected = set(selected_items)
        if not selected <= set(self.items):
            raise ValueError("set contains an unknown item")
        node = self.root
        previous_level = -1
        while node > 1:
            level, low, high = self.nodes[node]
            if any(self.items[skipped] in selected for skipped in range(previous_level + 1, level)):
                return False
            item = self.items[level]
            if item in selected:
                selected.remove(item)
                node = high
            else:
                node = low
            previous_level = level
        return node == 1 and not selected

    def family_size(self):
        cache = {0: 0, 1: 1}

        def count(node):
            if node not in cache:
                _, low, high = self.nodes[node]
                cache[node] = count(low) + count(high)
            return cache[node]

        return count(self.root)


dispatch_families = DispatchSetFamily(
    ("cold", "fragile", "insured", "oversized"),
    ({"cold", "insured"}, {"fragile", "insured"}, {"insured"}, {"cold", "fragile", "insured"}),
)
print("family size:", dispatch_families.family_size())
print("cold insured:", dispatch_families.contains({"cold", "insured"}))
print("cold alone:", dispatch_families.contains({"cold"}))
print("internal nodes:", len(dispatch_families.nodes) - 2)

Output

family size: 4
cold insured: True
cold alone: False
internal nodes: 3

Time, space, and tradeoff

For F explicit subsets and V ordered items, this direct partitioning builder spends O(FV) work and can retain O(FV) node and temporary-set records in the worst case; memoized node interning may reduce the retained graph. Recursion uses O(V) depth. Membership visits at most V item levels, and family-size counting visits each retained node once with O(M) memo space for M nodes. A giant explicitly listed family still costs time proportional to that input; the compact diagram does not make explicit enumeration free. A Boolean rule diagram models assignments, while a zero-suppressed diagram treats the absence of items as the default for sparse combination families.

Common Mistakes

Do not treat a skipped item as a wildcard that may be included.
Do not replace zero suppression with the equal-children Boolean reduction rule.
Do not confuse terminal one with one particular nonempty subset.
Do not infer that this explicit builder can enumerate an exponential family cheaply.

Connected lessons

Compare this operation boundary with Moveable disjoint sets: transfer one shipment without splitting its old tree, Block-cut indexes: separate articulation depots from cyclic road blocks, Kruskal reconstruction trees: answer route bottlenecks through merge ancestors, then complete the structure audit and decision quiz.

data structures

range-query-structures