Edmonds max_matching.h tester
authorjacint
Thu, 13 Jan 2005 18:46:00 +0000
changeset 1078ce8466be7683
parent 1077 784a8bc07316
child 1079 81addddaf3d3
Edmonds max_matching.h tester
src/test/max_matching_test.cc
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/test/max_matching_test.cc	Thu Jan 13 18:46:00 2005 +0000
     1.3 @@ -0,0 +1,189 @@
     1.4 +/* -*- C++ -*-
     1.5 + * src/test/max_matching_test.cc - Part of LEMON, a generic C++ optimization library
     1.6 + *
     1.7 + * Copyright (C) 2004 Egervary Jeno Kombinatorikus Optimalizalasi Kutatocsoport
     1.8 + * (Egervary Combinatorial Optimization Research Group, EGRES).
     1.9 + *
    1.10 + * Permission to use, modify and distribute this software is granted
    1.11 + * provided that this copyright notice appears in all copies. For
    1.12 + * precise terms see the accompanying LICENSE file.
    1.13 + *
    1.14 + * This software is provided "AS IS" with no warranty of any kind,
    1.15 + * express or implied, and with no claim as to its suitability for any
    1.16 + * purpose.
    1.17 + *
    1.18 + */
    1.19 +
    1.20 +#include <iostream>
    1.21 +#include <queue>
    1.22 +#include <math.h>
    1.23 +#include <cstdlib>
    1.24 +
    1.25 +#include "test_tools.h"
    1.26 +#include <lemon/invalid.h>
    1.27 +#include <lemon/list_graph.h>
    1.28 +#include <graph_gen.h>
    1.29 +#include <max_matching.h>
    1.30 +
    1.31 +using namespace std;
    1.32 +using namespace lemon;
    1.33 +
    1.34 +int main() {
    1.35 +
    1.36 +  typedef UndirListGraph Graph;
    1.37 +
    1.38 +  typedef Graph::Edge Edge;
    1.39 +  typedef Graph::UndirEdgeIt UndirEdgeIt;
    1.40 +  typedef Graph::IncEdgeIt IncEdgeIt;
    1.41 +  typedef Graph::NodeIt NodeIt;
    1.42 +  typedef Graph::Node Node;
    1.43 +   
    1.44 +  Graph G;
    1.45 +
    1.46 +  random_init(); 
    1.47 +  randomGraph(G, random(5000), random(20000) );  
    1.48 +
    1.49 +  MaxMatching<Graph> max_matching(G);
    1.50 +  max_matching.runEdmonds(0);
    1.51 +  
    1.52 +  int s=0;
    1.53 +  Graph::NodeMap<Node> mate(G,INVALID);
    1.54 +  max_matching.writeNMapNode(mate);
    1.55 +  for(NodeIt v(G); v!=INVALID; ++v) {
    1.56 +    if ( mate[v]!=INVALID ) ++s;
    1.57 +  }
    1.58 +  int size=(int)s/2;  //size will be used as the size of a maxmatching
    1.59 +  
    1.60 +  check ( size == max_matching.size(), "mate() returns a different size matching than max_matching.size()" );
    1.61 +
    1.62 +  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos0(G);
    1.63 +  max_matching.writePos(pos0);
    1.64 +  
    1.65 +  max_matching.resetPos();
    1.66 +  max_matching.resetMatching();
    1.67 +  max_matching.runEdmonds(1);
    1.68 +  s=0;
    1.69 +  max_matching.writeNMapNode(mate);
    1.70 +  for(NodeIt v(G); v!=INVALID; ++v) {
    1.71 +    if ( mate[v]!=INVALID ) ++s;
    1.72 +  }
    1.73 +  check ( (int)s/2 == size, "The size does not equal!" );
    1.74 +
    1.75 +  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos1(G);
    1.76 +  max_matching.writePos(pos1);
    1.77 +
    1.78 +  max_matching.resetPos();
    1.79 +  max_matching.run();
    1.80 +  s=0;
    1.81 +  max_matching.writeNMapNode(mate);
    1.82 +  for(NodeIt v(G); v!=INVALID; ++v) {
    1.83 +    if ( mate[v]!=INVALID ) ++s;
    1.84 +  }
    1.85 +  check ( (int)s/2 == size, "The size does not equal!" ); 
    1.86 +  
    1.87 +  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos2(G);
    1.88 +  max_matching.writePos(pos2);
    1.89 +
    1.90 +  max_matching.resetPos();
    1.91 +  max_matching.resetMatching();
    1.92 +  max_matching.run();
    1.93 +  s=0;
    1.94 +  max_matching.writeNMapNode(mate);
    1.95 +  for(NodeIt v(G); v!=INVALID; ++v) {
    1.96 +    if ( mate[v]!=INVALID ) ++s;
    1.97 +  }
    1.98 +  check ( (int)s/2 == size, "The size does not equal!" ); 
    1.99 +  
   1.100 +  Graph::NodeMap<MaxMatching<Graph>::pos_enum> pos(G);
   1.101 +  max_matching.writePos(pos);
   1.102 +   
   1.103 +  bool ismatching=true;
   1.104 +  for(NodeIt v(G); v!=INVALID; ++v) {
   1.105 +    if ( mate[v]!=INVALID ) {
   1.106 +      Node u=mate[v];
   1.107 +      if (mate[u]!=v) ismatching=false; 
   1.108 +    }
   1.109 +  }  
   1.110 +  check ( ismatching, "It is not a matching!" );
   1.111 +
   1.112 +  bool coincide=true;
   1.113 +  for(NodeIt v(G); v!=INVALID; ++v) {
   1.114 +   if ( pos0[v] != pos1[v] || pos1[v]!=pos2[v] || pos2[v]!=pos[v] ) {
   1.115 +     coincide=false;
   1.116 +    }
   1.117 +  }
   1.118 +  check ( coincide, "The decompositions do not coincide! " );
   1.119 +
   1.120 +  bool noedge=true;
   1.121 +  for(UndirEdgeIt e(G); e!=INVALID; ++e) {
   1.122 +   if ( (pos[G.target(e)]==max_matching.C && pos[G.source(e)]==max_matching.D) || 
   1.123 +	 (pos[G.target(e)]==max_matching.D && pos[G.source(e)]==max_matching.C) )
   1.124 +      noedge=false; 
   1.125 +  }
   1.126 +  check ( noedge, "There are edges between D and C!" );
   1.127 +  
   1.128 +  bool oddcomp=true;
   1.129 +  Graph::NodeMap<bool> todo(G,true);
   1.130 +  int num_comp=0;
   1.131 +  for(NodeIt v(G); v!=INVALID; ++v) {
   1.132 +   if ( pos[v]==max_matching.D && todo[v] ) {
   1.133 +      int comp_size=1;
   1.134 +      ++num_comp;
   1.135 +      std::queue<Node> Q;
   1.136 +      Q.push(v);
   1.137 +      todo.set(v,false);
   1.138 +      while (!Q.empty()) {
   1.139 +	Node w=Q.front();	
   1.140 +	Q.pop();
   1.141 +	for(IncEdgeIt e(G,w); e!=INVALID; ++e) {
   1.142 +	  Node u=G.target(e);
   1.143 +	  if ( pos[u]==max_matching.D && todo[u] ) {
   1.144 +	    ++comp_size;
   1.145 +	    Q.push(u);
   1.146 +	    todo.set(u,false);
   1.147 +	  }
   1.148 +	}
   1.149 +      }
   1.150 +      if ( !(comp_size % 2) ) oddcomp=false;  
   1.151 +    }
   1.152 +  }
   1.153 +  check ( oddcomp, "A component of G[D] is not odd." );
   1.154 +
   1.155 +  int barrier=0;
   1.156 +  for(NodeIt v(G); v!=INVALID; ++v) {
   1.157 +    if ( pos[v]==max_matching.A ) ++barrier;
   1.158 +  }
   1.159 +  int expected_size=(int)( countNodes(G)-num_comp+barrier)/2;
   1.160 +  check ( size==expected_size, "The size of the matching is wrong." );
   1.161 +  
   1.162 +  return 0;
   1.163 +}
   1.164 +
   1.165 +
   1.166 +void random_init()
   1.167 +{
   1.168 +  unsigned int seed = getpid();
   1.169 +  seed |= seed << 15;
   1.170 +  seed ^= time(0);
   1.171 +  
   1.172 +  srand(seed);
   1.173 +}
   1.174 +
   1.175 +
   1.176 +int random(int m)
   1.177 +{
   1.178 +  return int( double(m) * rand() / (RAND_MAX + 1.0) );
   1.179 +}
   1.180 +
   1.181 +
   1.182 +/// Generates a random graph with n nodes and m edges.
   1.183 +/// Before generating the random graph, \c g.clear() is called.
   1.184 +template<typename Graph>
   1.185 +void randomGraph(Graph& g, int n, int m) {
   1.186 +  g.clear();
   1.187 +  std::vector<typename Graph::Node> nodes;
   1.188 +  for (int i=0; i<n; ++i)
   1.189 +    nodes.push_back(g.addNode());
   1.190 +  for (int i=0; i<m; ++i) 
   1.191 +    g.addEdge(nodes[random(n)], nodes[random(n)]);
   1.192 +}