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 +}