adiar icon indicating copy to clipboard operation
adiar copied to clipboard

Do not count Tainted Arcs in `reduce_pq`

Open SSoelvsten opened this issue 1 year ago • 0 comments

Currently, to get the i-level cut computations to work, we count the number of arcs to the true and the false terminal. Yet, if the arc is tainted, we know it is going to be accounted for at a later level ( see also #512 ). Hence, we should not be accounting for it at the current level.

  • [ ] Design a unit test, where a tainted arc to a terminal is counted twice. (this is probably easiest with ZDDs)
  • [ ] In reduce_pq only count untainted arcs to terminals.

Similarly, we should neither count the tainted internal arcs multiple times.

  • [ ] Include untainted_internal() to be used instead of .size()
  • [ ] Include untainted_terminal(v) to be used instead of terminals(v).

SSoelvsten avatar Jun 16 '23 09:06 SSoelvsten