SSoelvsten / adiar

An I/O-efficient implementation of (Binary) Decision Diagrams
https://ssoelvsten.github.io/adiar/
MIT License
24 stars 13 forks source link

Apply `global_1level_cut` at each level #512

Closed SSoelvsten closed 1 year ago

SSoelvsten commented 1 year ago

Currently, in adiar/internal/algorithms/reduce.h we accumulate all the edges that have been tainted by a node being suppressed (via. Reduction Rule 1). These edges are then added to the maximum at the very end of the algorithm.

Essentially, we over-approximate the cut in the graph by thinking the tainted edges as spanning level -∞ to ∞ next to the untainted DAG. Yet, it is sound and much closer to the DAG's structure if we instead only think the tainted edges from level i as spanning level i to ∞.

SSoelvsten commented 1 year ago

Closed with 5428ca9ce3648721dfe693342d40e39a392a025d