Fix dependency in fanout view "subsitute node" method

[Nozidoali]

Fix issue #545

The problem was when substituting node 10 using constant 0 (10->0), two other substitutions are triggered, namely, (12->11) and (11->5), which have dependency problems.

The problem is fixed by checking dependency before pushing each substitution into the stack.

BTW, this problem may also occur in the "substitute_node" method of other networks if nodes are not guaranteed to be substituted in a reverse-topological order.

[codecov-commenter]

Codecov Report

Merging #560 (4a11733) into master (826a2f0) will increase coverage by 0.04%. The diff coverage is 100.00%.

@@            Coverage Diff             @@
##           master     #560      +/-   ##
==========================================
+ Coverage   82.77%   82.82%   +0.04%     
==========================================
  Files         148      153       +5     
  Lines       18535    19100     +565     
==========================================
+ Hits        15343    15819     +476     
- Misses       3192     3281      +89     

Impacted Files	Coverage Δ
include/mockturtle/networks/aig.hpp	94.03% <100.00%> (+0.09%)	:arrow_up:
include/mockturtle/views/fanout_view.hpp	100.00% <100.00%> (+1.21%)	:arrow_up:
include/mockturtle/properties/aqfpcost.hpp	87.50% <0.00%> (-12.50%)	:arrow_down:
...ude/mockturtle/algorithms/aqfp/detail/dag_cost.hpp	98.61% <0.00%> (-1.39%)	:arrow_down:
...de/mockturtle/algorithms/aqfp/buffer_insertion.hpp	78.53% <0.00%> (-0.04%)	:arrow_down:
include/mockturtle/algorithms/aqfp/detail/dag.hpp	100.00% <0.00%> (ø)
...ude/mockturtle/algorithms/aqfp/detail/dag_util.hpp	100.00% <0.00%> (ø)
.../mockturtle/algorithms/aqfp/detail/partial_dag.hpp	100.00% <0.00%> (ø)
...ude/mockturtle/algorithms/aqfp/aqfp_node_resyn.hpp	56.84% <0.00%> (ø)
include/mockturtle/algorithms/aqfp/aqfp_db.hpp	97.71% <0.00%> (ø)
... and 6 more

Help us with your feedback. Take ten seconds to tell us how you rate us.

[lee30sonia]

Good catch! Could you also add a unit test catching this case (i.e. would fail without the fix) in the tests of fanout_view?

[lee30sonia]

Makes sense to me, but I still wonder if there is a better solution. As this will affect the fundamental implementation of networks and thus many algorithms, I would like to think a bit more before merging. Also, the same problem should also happen (at least) for xag, mig and xmg, so the fix should be ported there too.

[Nozidoali]

In these commits, I

• added test cases in AIG XAG MIG XMG for dependency and self-substitution issues checking.
• fixed the dependency bug in fanout-view, AIG, XAG, MIG, XMG
• fixed the self-substitution bug in XAG and XMG.