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