test/max_matching_test.cc
changeset 2386 81b47fc5c444
parent 2116 b6a68c15a6a3
child 2391 14a343be7a5a
equal deleted inserted replaced
7:b221319c7f24 8:7d028aa92f2f
    72   Graph::NodeMap<Node> mate(g,INVALID);
    72   Graph::NodeMap<Node> mate(g,INVALID);
    73   max_matching.writeNMapNode(mate);
    73   max_matching.writeNMapNode(mate);
    74   for(NodeIt v(g); v!=INVALID; ++v) {
    74   for(NodeIt v(g); v!=INVALID; ++v) {
    75     if ( mate[v]!=INVALID ) ++s;
    75     if ( mate[v]!=INVALID ) ++s;
    76   }
    76   }
    77   int size=(int)s/2;  //size will be used as the size of a maxmatching
    77   int size=int(s/2);  //size will be used as the size of a maxmatching
    78 
    78 
    79   for(NodeIt v(g); v!=INVALID; ++v) {
    79   for(NodeIt v(g); v!=INVALID; ++v) {
    80     max_matching.mate(v);
    80     max_matching.mate(v);
    81   }
    81   }
    82 
    82 
    90   s=0;
    90   s=0;
    91   max_matching.writeNMapNode(mate);
    91   max_matching.writeNMapNode(mate);
    92   for(NodeIt v(g); v!=INVALID; ++v) {
    92   for(NodeIt v(g); v!=INVALID; ++v) {
    93     if ( mate[v]!=INVALID ) ++s;
    93     if ( mate[v]!=INVALID ) ++s;
    94   }
    94   }
    95   check ( (int)s/2 == size, "The size does not equal!" );
    95   check ( int(s/2) == size, "The size does not equal!" );
    96 
    96 
    97   Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos1(g);
    97   Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos1(g);
    98   max_matching.writePos(pos1);
    98   max_matching.writePos(pos1);
    99 
    99 
   100   max_matching.run();
   100   max_matching.run();
   101   s=0;
   101   s=0;
   102   max_matching.writeNMapNode(mate);
   102   max_matching.writeNMapNode(mate);
   103   for(NodeIt v(g); v!=INVALID; ++v) {
   103   for(NodeIt v(g); v!=INVALID; ++v) {
   104     if ( mate[v]!=INVALID ) ++s;
   104     if ( mate[v]!=INVALID ) ++s;
   105   }
   105   }
   106   check ( (int)s/2 == size, "The size does not equal!" ); 
   106   check ( int(s/2) == size, "The size does not equal!" ); 
   107   
   107   
   108   Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos2(g);
   108   Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos2(g);
   109   max_matching.writePos(pos2);
   109   max_matching.writePos(pos2);
   110 
   110 
   111   max_matching.resetMatching();
   111   max_matching.resetMatching();
   113   s=0;
   113   s=0;
   114   max_matching.writeNMapNode(mate);
   114   max_matching.writeNMapNode(mate);
   115   for(NodeIt v(g); v!=INVALID; ++v) {
   115   for(NodeIt v(g); v!=INVALID; ++v) {
   116     if ( mate[v]!=INVALID ) ++s;
   116     if ( mate[v]!=INVALID ) ++s;
   117   }
   117   }
   118   check ( (int)s/2 == size, "The size does not equal!" ); 
   118   check ( int(s/2) == size, "The size does not equal!" ); 
   119   
   119   
   120   Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos(g);
   120   Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos(g);
   121   max_matching.writePos(pos);
   121   max_matching.writePos(pos);
   122    
   122    
   123   bool ismatching=true;
   123   bool ismatching=true;
   174 
   174 
   175   int barrier=0;
   175   int barrier=0;
   176   for(NodeIt v(g); v!=INVALID; ++v) {
   176   for(NodeIt v(g); v!=INVALID; ++v) {
   177     if ( pos[v]==max_matching.A ) ++barrier;
   177     if ( pos[v]==max_matching.A ) ++barrier;
   178   }
   178   }
   179   int expected_size=(int)( countNodes(g)-num_comp+barrier)/2;
   179   int expected_size=int( countNodes(g)-num_comp+barrier)/2;
   180   check ( size==expected_size, "The size of the matching is wrong." );
   180   check ( size==expected_size, "The size of the matching is wrong." );
   181   
   181   
   182   return 0;
   182   return 0;
   183 }
   183 }