adiar icon indicating copy to clipboard operation
adiar copied to clipboard

Improve 1-level and 2-level cut computations within Builders

Open SSoelvsten opened this issue 2 years ago • 0 comments

The current over-approximations for 1-level and 2-level cuts within the bdd_builder and zdd_builder (specifically within the destructor of the node_writer) works well when the BDD does not have many far-going arcs. If it does, then we might want to compute the 1-level and 2-level cuts more exactly.

Apply long-reaching arcs early

This is Similar to #512 , we may as well add the far-reaching edges early to the current maximum. This allows a much wider level above to take precedence. This - of course - still leaves some nasty cases open.

Expensive, but definitely working, Solution

If the number of far-going arcs are many, then compute in O(N log N) time the 1-level and 2-level cuts with a new time-forward processing algorithm. This should be possible as a generalization of the count algorithm.

SSoelvsten avatar Sep 08 '22 14:09 SSoelvsten