Cut enumeration before and after node substitution in AIG

[nitabukoshi]

The issue is the following:

• The number of cuts is decreasing after node substitution in AIG.
• Node 21 (which has negated fanin 19 and negated fanin 20) is substituted with new node 54 (which has not negated fanin 19 and not negated fanin 20).
• Attached are two pictures, one showing the AIG before substitution and the other after substituting node 21 with node 54. Also the terminal output showing the number of cuts before and after substitution.

Following is the code:

#include <mockturtle/mockturtle.hpp>
using namespace std;
int main(int argc, char *argv[])
{ 
  //AIG from file 
  mockturtle::aig_network aig;
  lorina::read_aiger("file.aig", mockturtle::aiger_reader(aig));

  //Cut enumeration parameters
  mockturtle::cut_enumeration_params cp;
  cp.cut_size = 3u;   //maximum number of leaves
  cp.cut_limit = 100u; //maximum number of computed cuts for a node

  //Cut enumeration algorithm from mockturtle
  auto cuts = mockturtle::cut_enumeration<mockturtle::aig_network, true>(aig, cp);
  cout<<"Number of cuts: "<<cuts.total_cuts()<<"\n"; 

  //Node to be substituted, index 21
  int node_index = 21;

  auto old_node = aig.index_to_node(node_index);
  auto& old_node_storage = aig._storage->nodes[old_node];
  int child0 = aig._storage->nodes[node_index].children[0u].index;
  int child1 = aig._storage->nodes[node_index].children[1u].index;
  auto child0_sig = aig.make_signal(aig.index_to_node(child0));
  auto child1_sig = aig.make_signal(aig.index_to_node(child1));

  //The new node we want instead of the old node
  auto new_node = aig.create_and(child0_sig, child1_sig); 

  aig.substitute_node( old_node, new_node );  

  cout<<"\nNode substituted...\n";
  cleanup_dangling(aig);

  cuts = mockturtle::cut_enumeration<mockturtle::aig_network, true>(aig, cp);
  cout<<"\nNumber of cuts after substitution: "<<cuts.total_cuts()<<"\n";  
}

Thank you in advance for any help!

[hriener]

• I assume that you have manually adapted the maximum number of cuts supported by cut_enumeration because your cut_limit=100 is clearly higher than 26:

  ../include/mockturtle//algorithms/cut_enumeration.hpp:  static constexpr uint32_t max_cut_num = 26;
  ../include/mockturtle//algorithms/cut_enumeration.hpp:  using cut_set_t = cut_set<cut_t, max_cut_num>;
  ../include/mockturtle//algorithms/cut_enumeration.hpp:    assert( ps.cut_limit < cuts.max_cut_num && "cut_limit exceeds the compile-time limit for the maximum number of cuts" );

• To reproduce your issue, it would be practical to attach the AIG file.

[nitabukoshi]

• I had not changed the cut_limit before (static constexpr uint32_t max_cut_num = 26). However, I just tried changing it to: static constexpr uint32_t max_cut_num = 100, and the result was the same as before.
• Attached is the AIG file. file.zip

[hriener]

• Your call to cleanup_dangling does not look right. It should read: aig = cleanup_dangling( aig );. (A [nodiscard] attribute on the return value of the function would make that safer for the end user.)
• You have to adapt the max_cut_num. Otherwise, I believe, you will iterate out of bounds eventually. You should see an assertion violation for this problem if you compile in DEBUG mode. I would, in general, recommend to use the DEBUG mode during development.

[nitabukoshi]

• The cleanup_dangling call seems to have been the issue. I also changed the max_cut_num.

Thank you very much for your help!