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