test/max_matching_test.cc
changeset 2534 edad4c3e926d
parent 2391 14a343be7a5a
child 2553 bfced05fa852
equal deleted inserted replaced
9:14450745a999 10:931573eb8642
    64   g.addEdge(nodes[6], nodes[3]);
    64   g.addEdge(nodes[6], nodes[3]);
    65   g.addEdge(nodes[0], nodes[5]);
    65   g.addEdge(nodes[0], nodes[5]);
    66   g.addEdge(nodes[6], nodes[12]);
    66   g.addEdge(nodes[6], nodes[12]);
    67   
    67   
    68   MaxMatching<Graph> max_matching(g);
    68   MaxMatching<Graph> max_matching(g);
    69   max_matching.runEdmonds(0);
    69   max_matching.init();
       
    70   max_matching.startDense();
    70   
    71   
    71   int s=0;
    72   int s=0;
    72   Graph::NodeMap<Node> mate(g,INVALID);
    73   Graph::NodeMap<Node> mate(g,INVALID);
    73   max_matching.writeNMapNode(mate);
    74   max_matching.mateMap(mate);
    74   for(NodeIt v(g); v!=INVALID; ++v) {
    75   for(NodeIt v(g); v!=INVALID; ++v) {
    75     if ( mate[v]!=INVALID ) ++s;
    76     if ( mate[v]!=INVALID ) ++s;
    76   }
    77   }
    77   int size=int(s/2);  //size will be used as the size of a maxmatching
    78   int size=int(s/2);  //size will be used as the size of a maxmatching
    78 
    79 
    80     max_matching.mate(v);
    81     max_matching.mate(v);
    81   }
    82   }
    82 
    83 
    83   check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" );
    84   check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" );
    84 
    85 
    85   Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos0(g);
    86   Graph::NodeMap<MaxMatching<Graph>::DecompType> pos0(g);
    86   max_matching.writePos(pos0);
    87   max_matching.decomposition(pos0);
    87   
    88   
    88   max_matching.resetMatching();
    89   max_matching.init();
    89   max_matching.runEdmonds(1);
    90   max_matching.startSparse();
    90   s=0;
    91   s=0;
    91   max_matching.writeNMapNode(mate);
    92   max_matching.mateMap(mate);
    92   for(NodeIt v(g); v!=INVALID; ++v) {
    93   for(NodeIt v(g); v!=INVALID; ++v) {
    93     if ( mate[v]!=INVALID ) ++s;
    94     if ( mate[v]!=INVALID ) ++s;
    94   }
    95   }
    95   check ( int(s/2) == size, "The size does not equal!" );
    96   check ( int(s/2) == size, "The size does not equal!" );
    96 
    97 
    97   Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos1(g);
    98   Graph::NodeMap<MaxMatching<Graph>::DecompType> pos1(g);
    98   max_matching.writePos(pos1);
    99   max_matching.decomposition(pos1);
    99 
   100 
   100   max_matching.run();
   101   max_matching.run();
   101   s=0;
   102   s=0;
   102   max_matching.writeNMapNode(mate);
   103   max_matching.mateMap(mate);
   103   for(NodeIt v(g); v!=INVALID; ++v) {
   104   for(NodeIt v(g); v!=INVALID; ++v) {
   104     if ( mate[v]!=INVALID ) ++s;
   105     if ( mate[v]!=INVALID ) ++s;
   105   }
   106   }
   106   check ( int(s/2) == size, "The size does not equal!" ); 
   107   check ( int(s/2) == size, "The size does not equal!" ); 
   107   
   108   
   108   Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos2(g);
   109   Graph::NodeMap<MaxMatching<Graph>::DecompType> pos2(g);
   109   max_matching.writePos(pos2);
   110   max_matching.decomposition(pos2);
   110 
   111 
   111   max_matching.resetMatching();
       
   112   max_matching.run();
   112   max_matching.run();
   113   s=0;
   113   s=0;
   114   max_matching.writeNMapNode(mate);
   114   max_matching.mateMap(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>::DecompType> pos(g);
   121   max_matching.writePos(pos);
   121   max_matching.decomposition(pos);
   122    
   122    
   123   bool ismatching=true;
   123   bool ismatching=true;
   124   for(NodeIt v(g); v!=INVALID; ++v) {
   124   for(NodeIt v(g); v!=INVALID; ++v) {
   125     if ( mate[v]!=INVALID ) {
   125     if ( mate[v]!=INVALID ) {
   126       Node u=mate[v];
   126       Node u=mate[v];
   137   }
   137   }
   138   check ( coincide, "The decompositions do not coincide! " );
   138   check ( coincide, "The decompositions do not coincide! " );
   139 
   139 
   140   bool noedge=true;
   140   bool noedge=true;
   141   for(UEdgeIt e(g); e!=INVALID; ++e) {
   141   for(UEdgeIt e(g); e!=INVALID; ++e) {
   142    if ( (pos[g.target(e)]==max_matching.C && pos[g.source(e)]==max_matching.D) || 
   142    if ( (pos[g.target(e)]==max_matching.C && 
   143 	 (pos[g.target(e)]==max_matching.D && pos[g.source(e)]==max_matching.C) )
   143 	 pos[g.source(e)]==max_matching.D) || 
       
   144 	 (pos[g.target(e)]==max_matching.D && 
       
   145 	  pos[g.source(e)]==max_matching.C) )
   144       noedge=false; 
   146       noedge=false; 
   145   }
   147   }
   146   check ( noedge, "There are edges between D and C!" );
   148   check ( noedge, "There are edges between D and C!" );
   147   
   149   
   148   bool oddcomp=true;
   150   bool oddcomp=true;